t = Head;
while (t!=Tail)
  {(*t).Flag = TRUE; t = (*t).Next;}

void Depth_First_Search (Lref 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; }
}

while (Имеется хотя бы одна непосещенная вершина)
{
  Пусть p - первая из непосещенных вершин.
  Посетить вершину p и поместить ее в пустой стек S;
  while ( Стек S непуст )
  {
    Пусть p - вершина, находящаяся на верхушке стека S;
    if (У вершины p есть непосещенные смежные вершины)
      { Пусть q - первая непосещенная вершина из вершин, смежных 
        вершине p. Пройти по ребру (p,q), посетить вершину q и 
        поместить ее в стек S } 
    else Удалить вершину p из стека S
  }
}

t = Head;
while (t!=Tail)
  { (*t).Flag = TRUE; t = (*t).Next; }

void Depth_First_Search_1 (Lref r)
{
  Tref t;
  svqz Stack;

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

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

   (DEFUN TESTDF (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))
      (DEPTHFIRST 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 DEPTHFIRST (LAMBDA (GRAPH ROOT)
   ; Обход графа в глубину:
   ; GRAPH - граф, представленный структурой смежности в
   ;         виде ассоциативного списка,
   ; ROOT  - вершина, с которой начинается обход графа,
   ; Результат: список вершин графа в порядке посещения в глубину
      (COND ( (NULL GRAPH) NIL )
            (  T  (DEFI GRAPH (LIST ROOT) (LIST ROOT)) )
      )
   ))
   ; --------------------------------------
   (DEFUN DEFI (LAMBDA (GRAPH VISITED PATH)
   ; GRAPH   - граф, представленный структурой смежности в
   ;           виде ассоциативного списка,
   ; VISITED - список уже посещенных вершин,
   ; PATH    - список вершин, определяющий путь посещения
      (COND
         ( (NULL PATH) (REVERSE VISITED) )
         ( T  (COND ( (NULL (EXPND GRAPH VISITED (CAR PATH)))
                            (DEFI GRAPH VISITED (CDR PATH)) )
                    (  T  (DEFI GRAPH
                                  (CONS (EXPND GRAPH VISITED
                                               (CAR PATH))
                                         VISITED)
                                  (CONS (EXPND GRAPH VISITED
                                               (CAR PATH))
                                         PATH)) )) )
      )
   ))
   ; -----------------------------------------
   (DEFUN EXPND (LAMBDA (GRAPH VISITED VERTEX)
   ; Выбор в графе GRAPH следующей еще не просмотренной
   ;        вершины, смежной с вершиной VERTEX
      (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)) )
      )
   ))

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