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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Обработка текстовых данных http://www.cyberforum.ru/cpp-beginners/thread1178286.html
Уважаемы форумчане, помогите с решением задачи. Сначала нужно ввести n кол-во строк в файл, потом открыть его, считать из него эти строки и сохранить в другой файл. Вот только с одним условием, если в строке больше 6 символов, то нужно вставить только чётные символы. Именно с обработкой строк у меня возникли проблемы. Не знаю как это реализовать... #include "stdafx.h" #include <fstream>...
C++ Количество цифр в вещественном (!) числе Всем привет! Пытаюсь решить такую задачу, но для дробных чисел ничего не получается :( С целыми числами всё норм. Нужно посчитать к-во цифр в данном числе (тип double). Если число дробное, десятичную зяпятую не считать. Если число неотрицательное, знак не считать. template<class T> int getLendth(T num) { using namespace std; T full; // целая часть T fract = modf(num, &full); // дробная... http://www.cyberforum.ru/cpp-beginners/thread1178271.html
Найти общую стоимость товаров, которые дороже 1000 рублей C++
Заданы, функцией rand(), стоимости товаров в группе. Найти общую стоимость товаров, которые дороже 1000 рублей (количество товаров не известно). Добавлено через 32 минуты help
C++ Создайте класс HugeInteger, который использует массив из 40 элементов для хранения целых чисел до 40 цифр
Создайте класс HugeInteger, который использует массив из 40 элементов для хранения целых чисел, содержащих до 40 цифр. Создайте функции элементы inputHugeInteger, outputHugeInteger, addHugeIntegers и substractHugeIntegers для ввода, вывода, сложения и вычитания этих больших целых. Для сравнения объектов HugeInteger создайте функции isEqualTo (равно), isNotEqualTo (неравно), isGreaterThan...
C++ Что будет находится в переменных a и b после выполнения следующего фрагмента http://www.cyberforum.ru/cpp-beginners/thread1178265.html
Что будет находится в переменных a и b после выполнения следующего фрагмента программы: int a=5, b=2; a*=a-b++;
C++ Вывести строку, обратную заданной Собственно программа для того что бы вывести строку обратную данной. Я не могу догнать как она работает. Понятно до того момента как , " for (int j = 0; j <len / 2; j++) " , зачем мы количество символов в строке делим на 2 , и почему это является завершением для цикла ? #include <iostream> using namespace std; void main() { char str = "misha"; подробнее

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

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

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 минуты
помогите
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 23:56. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru