Шаг 98.
Путь между фиксированными вершинами

    На этом шаге мы рассмотрим алгоритм нахождения пути между вершинами.

    Оба вида обхода графа - в глубину и в ширину могут быть использованы для нахождения пути (цепи) между фиксированными вершинами u и v [1, с.92]. Достаточно начать обход графа с вершины v и вести его до момента посещения вершины u.

    Преимуществом обхода графа в глубину является тот факт, что в момент посещения вершины u стек содержит последовательность вершин, определяющую путь (цепь) из v в u. Это становится очевидным, если отметить, что каждая вершина, помещаемая в стек, является смежной вершиной верхнего элемента стека.

    Однако недостатком использования алгоритма обхода графа в глубину для поиска пути между данными вершинами является то, что полученный таким образом путь в общем случае не будет кратчайшим путем (кратчайшей цепью).


    Пример 1. Поиск пути между двумя заданными вершинами в графе с использованием обхода графа в глубину. Граф представлен структурой Вирта.
#include <iostream.h>
#define TRUE 1
#define FALSE 0
typedef 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 Path_Depth_First_Search (int, int);
};

void main ()
{
  Spisok A;
  int B,E;
  Lref t; //Рабочий указатель для перемещения 
          // по списку заголовочных звеньев.
  //Построение графа и вывод его структуры Вирта.
  A.MakeGraph ();
  A.PrintGraph (); cout<<endl;
  //Определение пути между двумя заданными вершинами графа.
  t = A.GetHead();
  while (t!=A.GetTail())
    { (*t).Flag = TRUE; t = (*t).Next; }
  cout << "Введите начальную вершину пути: "; cin >> B;
  cout << "Введите конечную вершину пути : "; cin >> E;
  cout << "Искомый путь: ";
  A.Path_Depth_First_Search (B,E); 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::Path_Depth_First_Search (int B, int E)
//Путь между вершинами B и E в графе, заданном указателем Head.
{
  Lref s,r;
  Tref t;
  svqz UkZv; //Рабочий указатель для перемещения по стеку.                

  svqz Stack = NULL; //Стек пуст.
  //Определим указатель на вершину B
  s = Head;
  while  (s!=Tail)
  {
    if  (s->Key==B)  r = s;
    s = s->Next;
  }
  //Посетим первую непосещенную вершину графа и 
  //поместим ее в первоначально пустой стек.
  if (r->Key==E) goto Metka;
  r->Flag = FALSE; W_S (&Stack,r->Trail);
  while (Stack!=NULL)
  {
    //Рассмотрим "верхушку" стека.
    t = Stack->Element;
    if  (t->Id->Trail!=NULL)
    //У рассматриваемой вершины есть смежные вершины.
    {
      if (t->Id->Flag)
      //У рассматриваемой вершины есть
      //непосещенные смежные вершины.
      {
        //Посетим рассматриваемую вершину
        //и поместим указатель на ее список смежности в стек.
        if (t->Id->Key==E) goto Metka;
        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)
      //Посетим рассматриваемую вершину.
      {
         if  (t->Id->Key==E) goto Metka;
         t->Id->Flag = FALSE;
      }
      t = Stack->Element;
      if  (t->Next!=NULL)
      //Заменяем верхушку стека указателем 
      //на следующий элемент списка смежности...
      {
            YDALENIE (&Stack,&t);
            W_S (&Stack,t->Next);
      }
      //или удаляем верхушку стека.
      else  YDALENIE (&Stack,&t);
    }
  }
Metka:
  UkZv = Stack;
  while ( UkZv!=NULL )
  {
    cout << UkZv->Element->Id->Key << " ";
    UkZv = UkZv->Sled;
  }
  cout << B << endl;
}
Текст этой программы можно взять здесь.

    Для ориентированного графа, представленного на рисунке 1:


Рис.1. Пример графа

результат работы программы изображен на рисунке 2. Обратите внимание, что найден не оптимальный путь!


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

    Использование алгоритма обхода графа в ширину позволяет получить кратчайший путь между двумя фиксированными вершинами [1, с.93].


    Пример 2. Поиск пути между двумя заданными вершинами в графе с использованием обхода графа в ширину (нерекурсивный алгоритм). Граф представлен структурой Вирта.
#include <iostream.h>
#define TRUE 1
#define FALSE 0
typedef 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 Path_Breadth_First_Search (Lref, int, int);
};

void main ()
{
  Spisok A;
  int B,E;
  Lref t; //Рабочий указатель для перемещения
          // по списку заголовочных звеньев.

  //Построение графа и вывод его структуры Вирта.
  A.MakeGraph ();
  A.PrintGraph (); cout<<endl;
  //Определение пути между двумя заданными вершинами графа.
  t = A.GetHead();
  while (t!=A.GetTail())
    { (*t).Flag = TRUE; t = (*t).Next; }
  cout << "Введите начальную вершину пути: "; cin >> B;
  cout << "Введите конечную вершину пути : "; cin >> E;
  cout << "Искомый путь: ";
  A.Path_Breadth_First_Search(A.GetHead(),B,E); 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::Path_Breadth_First_Search (Lref H, int B, int E)
//Путь в графе, заданном указателем H, между вершинами B и E.
{
  svqz L; //Указатель на начало очеpеди.
  svqz R; //Указатель на конец  очеpеди.
  Lref p; //Рабочий указатель.
  Tref t; //Рабочий указатель.
  int  Pred[30]; //Элемент Pred[i] содержит вершину графа,
                 //"предшествующую" данной.
  int i;
   
  L = R = NULL; // Построение пустой очеpеди.
  //Определим указатель на вершину B и поместим его в очередь.
  p = H;
  while ( p!=Tail )
  {
    if ( p->Key==B )
    {
       Dobavlenie (&L,&R,p);
       p->Flag = FALSE;
    }
    p = p->Next;
  }
  //Пока очеpедь не пуста...
  while  (L!=NULL)
  {
     Udalenie_A (&L,&R,&p);
     t = p->Trail;
     while  (t!=NULL)
     {
       if (t->Id->Flag)
       {
         Dobavlenie (&L,&R,t->Id);
         t->Id->Flag = FALSE;
         Pred [t->Id->Key] = p->Key;
       }
       t = t->Next;
     }
  }
  i = E;
  cout << E << ' ';
  while (i!=B) 
  { cout << Pred[i] <<' '; i = Pred[i]; }
  cout << endl;
}
Текст этой программы можно взять здесь.

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


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

    Вернемся теперь к функциональному программированию.

    Мы уже упоминали о том, что параметр PATH функции DEFI (смотри шаг 96) описывает путь из начальной вершины в просматриваемую. Поэтому алгоритм обхода графа в глубину можно легко модифицировать в алгоритм поиска пути между заданными вершинами (например, вершинами ROOT и END).


    Пример 3.
   (DEFUN TESTWAY (LAMBDA NIL
      (PRINT "Построение графа.")
      (SETQ GRAPH NIL)   ;Инициализация
      (PRINT "Введите список вершин графа:") (SETQ NODE (READ))
      (PRINT "Введите список списков смежных вершин:")
      (SETQ NODELIST (READ))
      (PRINT (SETQ GRAPH (PAIRLIS NODE NODELIST GRAPH)))
      (PRINT "Приступим к поиску пути между заданными вершинами")
      (PRINT "    с использованием обхода графа в глубину...   ")
      (PRINT "Введите начальную вершину пути:") (SETQ ROOT (READ))
      (PRINT "Введите конечную вершину пути:")  (SETQ END  (READ))
      (WAY GRAPH ROOT END)
   ))
   ; ------------------------------------
   (DEFUN PAIRLIS (LAMBDA (KEY ADJ GRAPH)
   ; Построение графа из списка вершин KEY и списка списков
   ; смежных  вершин  ADJ  путем добавления к существующему
   ;                   графу GRAPH
      (COND ( (NULL KEY) GRAPH )
            ( (NULL ADJ) GRAPH )
            (  T  (CONS (CONS (CAR KEY) (CAR ADJ))
                        (PAIRLIS (CDR KEY) (CDR ADJ) GRAPH)) )
      )
   ))
   ; ---------------------------------
   (DEFUN WAY (LAMBDA (GRAPH ROOT END)
   ; Построение пути в графе GRAPH между вершинами ROOT и END
      (COND ( (NULL GRAPH) NIL )
            (  T  (DEFI GRAPH (LIST ROOT) (LIST ROOT) END) )
      )
   ))
   ; ------------------------------------------
   (DEFUN DEFI (LAMBDA (GRAPH VISITED PATH END)
   ; GRAPH   - граф, представленный структурой смежности в
   ;           виде ассоциативного списка,
   ; VISITED - список уже посещенных вершин,
   ; PATH    - список вершин, определяющий путь посещения
   ; END     - конечная вершина пути
      (COND ( (NULL PATH) (REVERSE VISITED) )
            ( T  (COND ( (NULL (EXPND GRAPH VISITED (CAR PATH)))
                            (DEFI GRAPH VISITED (CDR PATH) END)
                       )
                       ( (EQ (EXPND GRAPH VISITED (CAR PATH)) END)
                                (REVERSE (CONS END PATH)) )
                       (  T  (DEFI GRAPH
                                   (CONS (EXPND GRAPH VISITED
                                                (CAR PATH))
                                         VISITED)
                                   (CONS (EXPND GRAPH VISITED
                                                (CAR PATH))
                                         PATH)
                                   END) )) )
      )
   ))
   ; -----------------------------------------
   (DEFUN EXPND (LAMBDA (GRAPH VISITED VERTEX)
   ; Выбор в графе GRAPH следующей еще не просмотренной
   ;        вершины, смежной с вершиной  2VERTEX
      (COND ( (NULL (NEIGHBOUR3 VERTEX GRAPH)) NIL )
            (  T  (FIRSTNOTVISITED
                             VISITED
                             (NEIGHBOUR3 VERTEX GRAPH))
            )
      )
   ))
   ; --------------------------------------------
   (DEFUN FIRSTNOTVISITED (LAMBDA (VISITED VLIST)
   ; Поиск первой непосещенной вершины в списке VLIST
   ; VISITED - список уже посещенных вершин
      (COND ( (NULL VLIST) NIL )
            (  T  (COND ( (NULL (MEMBER (CAR VLIST) VISITED))
                             (CAR VLIST)
                        )
                        (  T  (FIRSTNOTVISITED
                                           VISITED
                                           (CDR VLIST))
                        )
                  )
            )
      )
   ))
   ; ---------------------------------
   (DEFUN NEIGHBOUR3 (LAMBDA (X GRAPH)
   ; Функция возвращает список вершин графа GRAPH, смежных с
   ;                 вершиной X
      (COND ( (NULL (ASSOC X GRAPH)) NIL )
            (  T  (CDR (ASSOC X GRAPH)) )
      )
   ))
Текст этой библиотеки можно взять здесь.

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


Рис.4. Пример графа

   

   1) $ (TESTWAY)
      Построение графа.
      Введите список вершин графа:
      (1 2 3 4 5 7 8)
      Введите список списков смежных вершин:
      ((2) (3 4) () (5) (2 7 8) () ())
      ((1 2) (2 3 4) (3) (4 5) (5 2 7 8) (7) (8))
      Приступим к поиску пути между заданными вершинами
          с использованием обхода графа в глубину...
      Введите начальную вершину пути:
      1
      Введите конечную вершину пути:
      5
      (1 2 4 5)
   2) $ (TESTWAY)
      Построение графа.
      Введите список вершин графа:
      (1 2 3 4 5 7 8)
      Введите список списков смежных вершин:
      ((2) (3 4) () (5) (2 7 8) () ())
      ((1 2) (2 3 4) (3) (4 5) (5 2 7 8) (7) (8))
      Приступим к поиску пути между заданными вершинами
          с использованием обхода графа в глубину...
      Введите начальную вершину пути:
      1
      Введите конечную вершину пути:
      1
      (1 2 3 4 5 7 8)

    Обратите внимание на тот факт, что если пути из вершины ROOT в вершину END не существует, то функция (WAY GRAPH ROOT END) возвращает результат обхода графа в глубину.

   


(1) Липский В. Комбинаторика для программистов. - М.: Мир, 1988. - 213 с.

    На следующем шаге мы познакомимся с Эйлеровыми путями и циклами.




Предыдущий шаг Содержание Следующий шаг