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

Практическая работа 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; }}