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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.86
naa17
0 / 0 / 0
Регистрация: 23.04.2014
Сообщений: 47
17.05.2014, 08:01     Графы. Реализовать удаление указанной вершины из графа G, удаление ребра соединяющего две заданные вершины #1
Доброго вечера)

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

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 минуты
помогите
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.05.2014, 08:01     Графы. Реализовать удаление указанной вершины из графа G, удаление ребра соединяющего две заданные вершины
Посмотрите здесь:

C++ Задача на графы. Удалить ребра так, чтобы степень любой вершины была равна 3 или 0
C++ Удаление вершины дерева поиска
Удаление вершины бинарного дерева C++
C++ Графы,исключение из пути определённых вершины
Найти все вершины графа, к которым существует путь заданной длины от вершины, номер которой вводится с клавиатуры. C++
C++ Задача на графы. Удалить ребро, соединяющее вершины a и b
Определить, какие вершины достижимы из заданной вершины S C++
Найти все вершины графа, к которым от заданной вершины можно добраться по пути не длиннее А C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 18:09. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru