using System;


namespace Graph
{


    class Program
    {


// псевдокод
        //     Visit(v);
        //     Mark(v);
        // for каждого ребра vw графа G do
        //  if вершина w неактивирована
        //      DepthFirstTraversal(G,w);
        //   end if;
        //end for;





        ////    Обход в глубину (называемый иногда стандартным обходом), есть обход графа по следующим правилам:

        ////находясь в вершине x, нужно двигаться в любую другую, ранее не посещенную вершину (если таковая найдется), одновременно запоминая дугу,
        //            по которой мы впервые попали в данную вершину;
        ////если из вершины x мы не можем попасть в ранее не посещенную вершину или таковой вообще нет, то мы возвращаемся в вершину z,
        //            из которой впервые попали в x, и продолжаем обход в глубину из вершины z.
        ////    При выполнении обхода графа по этим правилам мы стремимся проникнуть "вглубь" графа так далеко, как это возможно,
        //            затем отступаем на шаг назад и снова стремимся пройти вперед и так далее.

        ////    На этом шаге мы приведем рекурсивную функцию обхода графа в глубину. Граф представлен в памяти структурой Вирта.


        // В приведенной ниже формулировке нерекурсивного алгоритма поиска в глубину на графе [1,с.125-126] предполагается:
        //во-первых, что зафиксирован некоторый линейный порядок на множестве всех вершин графа, и, во-вторых, что множество вершин,
        //смежных со всякой вершиной графа, также линейно упорядочено.

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


        public class StackX
        {
            private readonly int SIZE = 20;
            private int[] st;
            private int top;
            public StackX() // constructor
            {
                st = new int[SIZE];
                top = -1;
            }
            public virtual void push(int j)
            {
                st[++top] = j;
            }
            public virtual int pop()
            {
                return st[top--];
            }
            public virtual int peek()
            {
                return st[top];
            }
            public virtual bool Empty
            {
                get
                {
                    return (top == -1);
                }
            }
        }

        public class Vertex
        {
            public char label; // label (e.g. 'A')
            public bool wasAktiv;
            // ------------------
            public Vertex(char lab)
            {
                label = lab;
                wasAktiv = false;
            }
            // ------------------
        }


        public class Graph
        {
            private readonly int MAX_VERTS = 20;
            private Vertex[] vertexList; // list of vertices
            private int[][] adjMat; // adjacency matrix
            private int nVerts; // current number of vertices
            private StackX theStack;
            // ------------------
            public Graph() // constructor
            {
                vertexList = new Vertex[MAX_VERTS];
              adjMat = RectangularArrays.ReturnRectangularIntArray(MAX_VERTS, MAX_VERTS);
                nVerts = 0;
                for (int j = 0; j < MAX_VERTS; j++) // set adjacency
                {
                    for (int k = 0; k < MAX_VERTS; k++) // matrix to 0
                    {
                        adjMat[j][k] = 0;
                    }
                }
                theStack = new StackX();
            } // end constructor
            // ------------------
            public virtual void addVertex(char lab)
            {
                vertexList[nVerts++] = new Vertex(lab);
            }
            // ------------------
            public virtual void addEdge(int start, int end)
            {
                adjMat[start][end] = 1;
                adjMat[end][start] = 1;
            }
            // ------------------
            public virtual void displayVertex(int v)
            {
                Console.Write(vertexList[v].label);
            }
            // ------------------
            public virtual void dfs() // depth-first search
            {
                vertexList[0].wasAktiv = true;
                displayVertex(0); // display it
                theStack.push(0); // push it
                while (!theStack.Empty) // until stack empty,
                {

                    int v = getAdjUnvisitedVertex(theStack.peek());
                    if (v == -1) // if no such vertex,
                    {
                        theStack.pop();
                    }
                    else
                    {
                        vertexList[v].wasAktiv = true; // mark it
                        displayVertex(v); // display it
                        theStack.push(v); // push it
                    }
                } // end while
                // stack is empty, so we're done
                for (int j = 0; j < nVerts; j++) // reset flags
                {
                    vertexList[j].wasAktiv = false;
                }
            } // end dfs

            public virtual int getAdjUnvisitedVertex(int v)
            {
                for (int j = 0; j < nVerts; j++)
                {
                    if (adjMat[v][j] == 1 && vertexList[j].wasAktiv == false)
                    {
                        return j;
                    }
                }
                return -1;
            } // end getAdjUnvisitedVert()
            // ------------------

        } // end class Graph
        ////////////////////////////////////////////////////////////////




        internal static partial class RectangularArrays
        {
            internal static int[][] ReturnRectangularIntArray(int Size1, int Size2)
            {
                int[][] Array = new int[Size1][];
                for (int Array1 = 0; Array1 < Size1; Array1++)
                {
                    Array[Array1] = new int[Size2];
                }
                return Array;
            }
        }

        public static void Main(string[] args)
        {
            Graph theGraph = new Graph();
            theGraph.addVertex('1'); // 0 (start for dfs)
            theGraph.addVertex('2'); // 1
            theGraph.addVertex('3'); // 2
            theGraph.addVertex('4'); // 3
            theGraph.addVertex('5'); // 4
            theGraph.addEdge(0, 1); // 1-2
            theGraph.addEdge(1, 4); // 2-5
            theGraph.addEdge(4, 2); // 5-3
            theGraph.addEdge(2, 3); // 3-4
            Console.Write("Visits: ");
            theGraph.dfs(); // depth-first search
            Console.WriteLine();
            Console.ReadKey();
        } // end main()

    }
}