#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 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;
	  }
	}
}

   (DEFUN TESTBF (LAMBDA NIL
      (PRINT "Построение графа.")
      (SETQ GRAPH NIL)   ;Инициализация
      (PRINT "Введите список вершин графа:") (SETQ NODE (READ))
      (PRINT "Введите список списков смежных вершин:")
      (SETQ NODELIST (READ))
      (PRINT (SETQ GRAPH (PAIRLIS NODE NODELIST GRAPH)))
      (PRINT "Приступим к обходу графа в ширину...")
      (PRINT "Введите вершину графа, с которой начнется обход:")
      (SETQ ROOT (READ))
      (BREADTHFIRST GRAPH ROOT)
   ))
   ; ------------------------------------
   (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 BREADTHFIRST (LAMBDA (GRAPH ROOT)
   ; Обход графа GRAPH в ширину, начиная с вершины ROOT
   ; GRAPH - граф, представленный структурой смежности в
   ;         виде ассоциативного списка,
   ; ROOT  - вершина графа, с которой начинается обход,
   ; Результат: список вершин графа в порядке посещения
      (BRFI
         GRAPH
         (LIST ROOT)              ; Вершина ROOT уже просмотрена
         (NEIGHBOUR3 ROOT GRAPH)  ; Ожидают просмотра вершины, смежные
                                  ; вершине ROOT
      )
   ))
   ; ---------------------------------------
   (DEFUN BRFI (LAMBDA (GRAPH VISITED QUEUE)
   ; GRAPH   - граф, представленный структурой смежности в
   ;           виде ассоциативного списка,
   ; VISITED - список уже просмотренных вершин
   ; QUEUE   - очередь вершин, ожидающих просмотра
      (COND ( (NULL QUEUE) (REVERSE VISITED) )
            ( T (COND ( (MEMBER (CAR QUEUE) VISITED)
                        ; Первая вершина в списке вершин, ожидающих
                        ; просмотра уже посещалась
                           (BRFI GRAPH VISITED (CDR QUEUE)) )
                      (  T  (BRFI
                               GRAPH
                               ; Вершина (CAR QUEUE) посещена
                               (CONS (CAR QUEUE) VISITED)
                               ; В очередь вершин, ожидающих просмотра,
                               ; помещаются вершины, смежные посещенной
                               (APPEND
                                  QUEUE
                                  (NEIGHBOUR3 (CAR QUEUE) GRAPH)))
                      )
                )
            )
      )
   ))
   ; ---------------------------------
   (DEFUN NEIGHBOUR3 (LAMBDA (X GRAPH)
   ; Функция возвращает список вершин графа GRAPH, смежных с
   ;                 вершиной X
      (COND ( (NULL (ASSOC X GRAPH)) NIL )
            (  T  (CDR (ASSOC X GRAPH)) )
      )
   ))

   1) $ (TESTBF)
      Построение графа.
      Введите список вершин графа:
      (1 2 3 4 5)
      Введите список списков смежных вершин:
      ((2 3 4) (1 3) (1 2 4) (1 3 5) (4))
      Приступим к обходу графа в ширину...
      Введите вершину графа, с которой начнется обход:
      4
      (4 1 3 5 2)
   2) $ (TESTBF)
      Построение графа.
      Введите список вершин графа:
      (1 2 3 4)
      Введите список списков смежных вершин:
      ((2 3 4) (3) (4) ())
      Приступим к обходу графа в ширину...
      Введите вершину графа, с которой начнется обход:
      2
      (2 3 4)
   3) $ (TESTBF)
      Построение графа.
      Введите список вершин графа:
      (1 2 3 4 5 6 7)
      Введите список списков смежных вершин:
      ((2 3) (4 5) (6 7) () () () ())
      Приступим к обходу графа в ширину...
      Введите вершину графа, с которой начнется обход:
      1
      (1 2 3 4 5 6 7)

    (APPEND QUEUE (NEIGHBOUR3 (CAR QUEUE) GRAPH))),

    (CONS (CAR QUEUE) VISITED),