Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.86
naa17
0 / 0 / 0
Регистрация: 23.04.2014
Сообщений: 47
#1

Графы. Реализовать удаление указанной вершины из графа G, удаление ребра соединяющего две заданные вершины - C++

17.05.2014, 08:01. Просмотров 2796. Ответов 0
Метки нет (Все метки)

Доброго вечера)

Имеется программа с графом и реализацией всего двух функций:

AddVertex (v1) – добавление вершины к графу G, в случае существования в составе G указанной вершины должно выдаваться соответствующее уведомление;
AddEdge (v1,v2) – соединение двух вершин ребром, если указанные вершины на момент выполнения указанной операции уже смежны, то пользователь должен быть оповещён о данном факте;

Помогите реализовать другие функции:

1. DelVertex (v1) – удаление указанной вершины из графа G, при этом должны удаляться все инцидентные данной вершине рёбра, в случае отсутствия заданной вершины оператору должно выдаваться соответствующее уведомление;
2. DelEdge (v1,v2) – удаление ребра соединяющего две заданные вершины, в случае отсутствия такого ребра оператору должно выдаваться соответствующее уведомление;
3. LoadGraph() – загружает граф в память программы из файла;
4. SaveGraph() – сохраняет созданный в памяти программы граф в файл;

А также операторы:

1. p(G) – количество вершин в графе G;
2. d(v) – вычисление степени указанной вершины (d-(v) полустепень исхода и d+(v) полустепень захода для орграфов);
3. D(G) – сумма степеней всех вершин графа G;


+ алгоритм

Алгоритм построения остовного дерева графа методом поиска в глубину.
Алгоритм должен возвращать остовное дерево исходного графа.

Собственно, код-донор:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
// Представление неориентированного графа
#include <iostream>
#include <conio.h>
using namespace std;
///////////////////////////////////////////////////////////
struct link   // один элемент списка смежности графа
{
  int data;   // метка вершины
  link* next; // указатель на следующую вершину в списке
} ;
//-----------------------Описание класса список------------------------------------/
 
class linklist // список смежных вершин
{
  private:
    link* first;             // указатель на 1-й элемент списка
  public:
    bool e;                  // признак существования или отсутствия списка
    linklist ( )            // конструктор без параметров
      { first = NULL; e=false; }     // списка пока не существует
    void additem ( int d ); // добавление элемента
    void display ( );       // вывод списка
    bool exist(int x);     // проверка вхождения элемента в список
    void makenull ( );   // опустошение списка;
};
///////////////////////////////////////////////////////////
void linklist::additem ( int d ) // добавление элемента
{
  link* newlink = new link;      // выделяем память
  newlink->data = d;             // запоминаем данные
  newlink->next = first;         // запоминаем значение first
  first = newlink;               // first теперь указывает на новый элемент
}
///////////////////////////////////////////////////////////
void linklist::display ( )
{
  link* current = first;           // начинаем с первого элемента
  if (!current) cout<<"\nlist is clear";
  while( current )                 // пока есть данные
  {
    cout << current->data<<' '; // печатаем данные
    current = current->next;       // двигаемся к следующему элементу
  }
}
///////////////////////////////////////////////////////////
void linklist::makenull ( )
{
link* current = first;           // начинаем с первого элемента
link* deleted;
  while( current )                 // пока не достигнут последний элемент
  {   deleted=current;           //запоминаем указатель на очередной элемент
      current = current->next;      // двигаемся к следующему элементу
      delete deleted;               // удаляем  тот, который запомнили 
  }
    first = NULL  ;
    cout<<"Список опустошен";
}
 
bool linklist::exist (int x)       // функция проверки наличия элемента в списке
  {
   link* current = first;           // начинаем с первого элемента
  if (!current) return 0;
  while( current )                 // пока есть данные
  {
    if (current->data==x)
      {
       return 1;
       break;
      }
    current = current->next;       // двигаемся к следующему элементу
   if (current ==NULL)
   return 0;
  }
  } 
  //-----------------------Описание класса Граф ------------------------------------/
 
class Graph
{
  private:
   linklist adj[100];   // 100 - ограничение максимального числа вершин
  public:
    Graph ( )            // конструктор без параметров
      {  }     // 
    void addedge ( int x, int y ); // добавление ребра в граф
    void addvertex (int x );       // добавление вершины в граф
    void display ( );          // вывод списка смежности графа
};
 
void Graph::addvertex (int x)
 {
  if (adj[x].e==false)
  adj[x].e=true;
  else
  cout<<"Такая вершина уже есть !!!"<<endl;
 }
void Graph::addedge (int x, int y)
 {
  if (adj[x].e==true&&adj[y].e==true&&adj[x].exist(y)==false&&adj[y].exist(x)==false&&(x!=y))
  {
   adj[x].additem(y);
   adj[y].additem(x);
  }
  else cout<<"Ошибка добавления вершины"<<endl;
 }
void Graph::display ()
{
 for (int i=1; i<100; i++)
 {
 if (adj[i].e==true)
  {
  cout<<i<<" - ";
  adj[i].display();
  cout<<endl;
 
 }
}
}
int main ( )
{
int x,y,n;
char sw='y';
  Graph G;       // создаем переменную-список
  cout<<"Введите количество вершин графа "<<endl;
  cin>>n;
 
  while (n>0)
  {
     cout<<"Введите метку очередной  вершины - ";
     cin>>x;
     G.addvertex(x) ; // добавляем туда несколько чисел
     n--;
  }
 
 
  while (sw!='n')
  {
     cout<<"Введите соединяемые вершины - (x,y)"<<endl;
     cin>>x;
     cin>>y;
     G.addedge(x,y) ; // добавляем туда несколько чисел
    cout<<"Хотите ли добавить ещё вершины (y/n)? "<<endl;
    sw=getch();
  }
  G.display ( );    // показываем список
 
   getch();
  return 0;
}
Добавлено через 10 часов 33 минуты
помогите
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.05.2014, 08:01
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Графы. Реализовать удаление указанной вершины из графа G, удаление ребра соединяющего две заданные вершины (C++):

Удаление вершины графа - C++
Добрый вечер. Нужна помощь в удалении вершины графа. Вот код: struct arc; struct node { int id; ...

Задача на графы. Удалить ребра так, чтобы степень любой вершины была равна 3 или 0 - C++
Здравствуйте. Условие задачи, собственно, в названии темы. Возникли проблемы с алгоритмом, не говоря уже про код. Ограничений на входной...

Найти все вершины графа, к которым от заданной вершины можно добраться по пути не длиннее А - C++
Найти все вершины графа, к которым от заданной вершины можно добраться по пути не длиннее А. Никаких наработок нет, к сожалению, вообще...

Найти все вершины неориентированного графа, к которым существует путь заданной длины от выделенной его вершины - C++
Здравствуйте.Помогите пожалуйста решить задачу. Найти все вершины неориентированного графа, к которым существует путь заданной длины от...

Найти все вершины неориентированного графа, к которым существует путь заданной длины от выделенной его вершины - C++
Здравствуйте! Помогите пожалуйста решить задачу. Найти все вершины неориентированного графа, к которым существует путь заданной...

Найти все вершины графа, к которым существует путь заданной длины от вершины, номер которой вводится с клавиатуры. - C++
Помоги написать программу по графам плиз Найти все вершины графа, к которым существует путь заданной длины (не обязательно кратчайший)...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.05.2014, 08:01
Привет! Вот еще темы с ответами:

Удаление вершины дерева поиска - C++
Здравствуйте. Не получается написать удаление вершины из дерева поиска, что бы после удаления, дерево оставалось деревом поиска. ...

Удаление вершины бинарного дерева - C++
Как удалять вершины бинарного дерева вместе с потомками?

Графы,исключение из пути определённых вершины - C++
Ребят!Есть программа:программа находит кратчайший путь в графе из точки а в точку б. Так вот как будет выглядеть функция которая будет...

Задача на графы. Удалить ребро, соединяющее вершины a и b - C++
Дан граф, состоящий из N вершин и заданный списком смежности. Удалить ребро, соединяющее вершины a и b.


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru