Практическая работа 13. Вычисление компонент связности

Определение.

Рассмотрим некоторое семейство подграфов графа G.

Граф H_max из этого семейства называется максимальным, если он не содержится ни в каком другом графе из рассматриваемого семейства.

 Максимальный связный подграф графа G называется связной компонентой G (компонентой связности G). В связном графе имеется единственная связная компонента, совпадающая с самим графом.

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

1.Запустите IDE Borland C++ 5.02. Подготовьте запуск исполнимых файлов в консольном режиме.

2. Откомпилируйте предложенную программу, которая  использует обход графа в глубину для нахождения всех его связных компонент. Граф представлен структурой Вирта.

#include <iostream.h>#define TRUE 1#define FALSE 0typedef int Boolean;typedef struct L *Lref; // Тип: указатель на заголовочный узел.typedef struct T *Tref; // Тип: указатель на дуговой узел. //Описание типа заголовочного узла.typedef struct L {   int Key; //Имя заголовочного узла. int Count; //Количество предшественников. Boolean Flag; //Флаг посещения узла при обходе. Tref Trail; //Указатель на список смежности. Lref Next; //Указатель на следующий узел в списке заголовочных узлов.} Leader; //Описание типа дугового узла.typedef struct T {   Lref Id;   Tref Next; } Trailer; //Описание типа узла стека.typedef Tref TipElement;typedef struct Zveno *svqz;typedef struct Zveno {   TipElement Element; //Указатель на список смежности. svqz Sled; } St; class Spisok{ private: Lref Head; //Указатель на голову списка заголовочных узлов. Lref Tail; //Указатель на фиктивный элемент                // в конце списка заголовочных узлов. void SearchGraph (int, Lref *); public: Spisok() {//Инициализация списка заголовочных узлов.         Head = Tail = new (Leader); } Lref GetHead() { return Head; } Lref GetTail() { return Tail; } void MakeGraph (); void PrintGraph (); void Depth_First_Search (Lref); void LinkComp();}; void main (){ Spisok A; Lref t; //Рабочий указатель для перемещения           // по списку заголовочных звеньев. //Построение графа и вывод его структуры Вирта. A.MakeGraph (); A.PrintGraph (); cout<<endl; //Рекурсивный обход графа в глубину. cout<<"Результат рекурсивного обхода...\n"; t = A.GetHead(); while (t!=A.GetTail()) { (*t).Flag = TRUE; t = (*t).Next; }  A.Depth_First_Search (A.GetHead()); cout<<endl; //Вывод компонент связности. cout<<"Компоненты связности:\n"; A.LinkComp();} void Spisok::SearchGraph (int w, Lref *h)//Функция возвращает указатель на заголовочный узел //с ключом w в графе, заданном структурой Вирта с указателем Head. { *h = Head; (*Tail).Key = w; while ((**h).Key!=w) *h = (**h).Next; if (*h==Tail) //В списке заголовочных узлов нет узла с ключом w. //Поместим его в конец списка Head. { Tail = new (Leader); (**h).Count = 0;     (**h).Trail = NULL; (**h).Next = Tail; }} void Spisok::MakeGraph ()//Функция возвращает указатель Head на структуру //Вирта, соответствующую ориентированному графу.{ int x,y; Lref p,q; //Рабочие указатели. Tref t,r; //Рабочие указатели. Boolean Res; //Флаг наличия дуги. cout<<"Вводите начальную вершину дуги: "; cin>>x; while (x!=0) { cout<<"Вводите конечную вершину дуги: "; cin>>y; //Определим, существует ли в графе дуга (x,y)? SearchGraph (x, &p); SearchGraph (y,&q); r = (*p).Trail; Res = FALSE;      while ((r!=NULL)&&(!Res))        if ((*r).Id==q) Res = TRUE;        else r = (*r).Next;      if (!Res) //Если дуга отсутствует, то поместим её в граф. { t = new (Trailer); (*t).Id = q;         (*t).Next = (*p).Trail; (*p).Trail = t; (*q).Count++; }      cout<<"Вводите начальную вершину дуги: "; cin>>x; }} void Spisok::PrintGraph ()//Вывод структуры Вирта, заданной указателем //Head и соответствующей ориентированному графу.{ Lref p; //Рабочий указатель. Tref q; //Рабочий указатель. p = Head; while (p!=Tail) { cout<<"("<<(*p).Key; q = (*p).Trail;      while (q!=NULL)       { cout<<(*(*q).Id).Key; q = (*q).Next; }      cout<<")"; p = (*p).Next; cout<<" "; }} void Spisok::Depth_First_Search (Lref r)//Рекурсивный обход графа в глубину. r - указатель //на структуру Вирта.{ Tref t; t = (*r).Trail; cout<<(*r).Key; (*r).Flag = FALSE; while (t!=NULL) { if ((*(*t).Id).Flag) Depth_First_Search ((*t).Id); t = (*t).Next; }} void Spisok::LinkComp()//Определение компонент связности в графе, заданном//структурой Вирта с указателем Head.{ Lref t = Head; while (t!=Tail) { t->Flag = TRUE; t = t->Next; } t = Head; while (t!=Tail) { if (t->Flag) { Depth_First_Search (t); cout << endl; } t = t->Next; }}