Практическая работа 11. Обходы графов

 

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 *); void W_S (svqz *, TipElement); void YDALENIE (svqz *, TipElement *); public: Spisok() {//Инициализация списка заголовочных узлов.         Head = Tail = new (Leader); } Lref GetHead() { return Head; } Lref GetTail() { return Tail; } void MakeGraph (); void PrintGraph (); void Depth_First_Search (Lref); void Depth_First_Search_1 (Lref);}; 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"; t = A.GetHead(); while (t!=A.GetTail()) { (*t).Flag = TRUE; t = (*t).Next;} A.Depth_First_Search_1 (A.GetHead()); cout<<endl;} 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::W_S (svqz *stk, TipElement el)//Помещение элемента el в стек stk.{ svqz q=new (St); (*q).Element = el; (*q).Sled = *stk; *stk = q;} void Spisok::YDALENIE (svqz *stk, TipElement *klad)//Удаление звена из стека, заданного указателем *stk. //Значение информационного поля удаляемого звена сохраня- //ется в параметре klad.{ svqz q; if (*stk==NULL) cout<<"Попытка выбора из пустого стека!\n"; else { *klad = (**stk).Element; q = *stk; *stk = (**stk).Sled; delete q; }} 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::Depth_First_Search_1 (Lref r)//Нерекурсивный обход графа в глубину.//r - указатель на структуру Вирта.{ Tref t; svqz Stack = NULL; //Стек пуст. //Посетим первую непосещенную вершину графа и   //поместим ее указатель на ее список смежности   //в первоначально пустой стек. cout<<(*r).Key; (*r).Flag = FALSE; W_S (&Stack,(*r).Trail); while (Stack!=NULL) { //Рассмотрим "верхушку" стека. t = (*Stack).Element;     if ((*(*t).Id).Trail!=NULL)       { //У рассматриваемой вершины есть смежные вершины.   if ((*(*t).Id).Flag)         //У рассматриваемой вершины есть         // непосещенные смежные вершины.   {     //Посетим рассматриваемую вершину           // и поместим указатель на ее список смежности в стек.     cout<< (*(*t).Id).Key; (*(*t).Id).Flag = FALSE;           W_S (&Stack,(*(*t).Id).Trail);         }         //У рассматриваемой вершины нет         //непосещенных смежных вершин.         else {           t = (*Stack).Element;           if ((*t).Next!=NULL)              //Заменяем верхушку стека              //указателем на следующий элемент списка смежности.              { YDALENIE (&Stack,&t); W_S (&Stack,(*t).Next); }           //Удаляем верхушку стека.           else YDALENIE (&Stack,&t);   }      }      //У рассматриваемой вершины нет смежных вершин. else {             if ((*(*t).Id).Flag) //Посетим рассматриваемую вершину.        { cout<<(*(*t).Id).Key; (*(*t).Id).Flag = FALSE; }             t = (*Stack).Element;             if ((*t).Next!=NULL)             //Заменяем верхушку стека указателем на следующий       // элемент списка смежности.        { YDALENIE (&Stack,&t); W_S (&Stack,(*t).Next); }             //Удаляем верхушку стека.       else YDALENIE (&Stack,&t);      } }}

Результат работы приложения приведен на рисунке 1:

Рис.1. Результат работы приложения

Замечание  Методика обхода в глубину очевидным образом переносится на ориентированные графы. Нетрудно проверить, что в случае ориентированного графа результатом вызова функций Depth_First_Search() и Depth_First_Search_1() будет посещение всех вершин u, таких что существует путь из v в u. В самом деле, при обходе в глубину ориентированного графа мы можем попасть в вершину y из вершины x только в том случае, если в графе есть дуга (x,y), т.е. мы должны двигаться вперед в направлении ориентации дуг, а возвращаться против ориентации (конечно же, в неориентированном графе таких ограничений нет)!

 

3. Откомпилируйте предложенную программу выполнения обхода графа в ширину.

 

#include <iostream.h>#define TRUE 1#define FALSE 0typedef int Boolean;typedef struct Leader *Lref; // Тип: указатель на заголовочный узел.typedef struct Trailer *Tref; // Тип: указатель на дуговой узел. //Описание типа заголовочного узла.typedef struct Leader {   int Key; //Имя заголовочного узла. int Count; //Количество предшественников. Boolean Flag; //Флаг посещения узла при обходе. Tref Trail; //Указатель на список смежности. Lref Next; //Указатель на следующий узел в списке заголовочных узлов.}; //Описание типа дугового узла.typedef struct Trailer{ Lref Id; Tref Next;}; //Описание типа узла очереди.typedef Lref TipElement; //Указатель на звено заголовочного списка.typedef struct Zveno *svqz;typedef struct Zveno{ TipElement Element; //Указатель на список смежности. svqz Sled;}; class Spisok{ private:   Lref Head; //Указатель на голову списка заголовочных узлов.   Lref Tail; //Указатель на фиктивный элемент                                 // в конце списка заголовочных узлов.   void Udalenie_A (svqz *, svqz *, TipElement *);   void Dobavlenie (svqz *, svqz *, TipElement);   void SearchGraph (int, Lref *); public:   Spisok() {//Инициализация списка заголовочных узлов.                          Head = Tail = new (Leader); }   Lref GetHead() { return Head; }   Lref GetTail() { return Tail; }   void MakeGraph ();   void PrintGraph ();   void Breadth_First_Search (Lref);}; 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.Breadth_First_Search (A.GetHead()); cout<<endl;} 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::Dobavlenie (svqz *L, svqz *R, TipElement elem)//Добавление элемента elem в очередь, заданную указателями L и R.{ svqz K = new (Zveno); K->Element = elem; K->Sled = NULL; if (*L==NULL)   { (*L) = K; (*R) = K; } else { (*R)->Sled = K; (*R) = K; }} void Spisok::Udalenie_A (svqz *L, svqz *R, TipElement *A)//Удаление элемента из очереди, заданной указателями L и R и//помещение удаленного элемента в переменную A.{ svqz q; if ((*L)!=NULL)   if ((*L)->Sled!=NULL)   {          (*A) = (*L)->Element; q = (*L);          (*L) = (*L)->Sled; delete q;   }   else {                  (*A) = (*L)->Element; delete *L;                  (*L) = (*R) = NULL;          }} void Spisok::Breadth_First_Search (Lref H)//Обход графа в ширину, начиная с вершины, заданной указателем H//(нерекурсивный обход).{ svqz L; //Указатель на начало очереди. svqz R; //Указатель на конец очереди. Lref p; //Рабочий указатель. Tref t; //Рабочий указатель. L = R = NULL; //Создание пустой очереди. Dobavlenie (&L,&R,H); H->Flag = FALSE; while (L!=NULL)   //Пока очередь не пуста...   {   Udalenie_A (&L,&R,&p);   cout << p->Key << " "; //Посещение вершины.   t = p->Trail;   while (t!=NULL)   {          if (t->Id->Flag)          {                  Dobavlenie (&L,&R,t->Id);                  t->Id->Flag = FALSE;          }          t = t->Next;   }   }}

 

Замечания.

1. Как и в случае обхода графа в глубину, функцию Breadth_First_Search() можно использовать без всяких модификаций и тогда, когда мы работаем с ориентированным графом. Очевидно, что тогда посещаются только те вершины, до которых существует путь от вершины, с которой мы начинаем обход.
2. Способ обхода дерева в ширину, называемый иногда обходом в гоpизонтальном поpядке, основан на посещении вершин деpева слева напpаво, уpовень за уpовнем вниз от коpня. Пpиведенный ниже нерекурсивный алгоpитм позволяет совершить обход деpева в шиpину, используя две очеpеди O1 и O2:

Взять пустые очеpеди O1 и O2. Поместить коpень в очеpедь O1. while (Одна из очеpедей O1 и O2 не пуста)       if (O1 не является пустой)   {             Пусть p - узел, находящийся в голове очеpеди O1.              Посетить веpшину p и удалить ее из O1.              Поместить всех сыновей веpшины p в очеpедь O2, начиная              со стаpшего сына.   } else В качестве O1 взять непустую очеpедь O2,          а в качестве O2 взять пустую очеpедь O1.