using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DFS
{
    class Vertex
    {
        public int data;
        public Vertex(int data)
        {
            this.data = data;
        }
    }
    class Edge
    {
        public int tail;
        public int head;
        public Edge(int tail,int head)
        {
            this.tail = tail;
            this.head = head;
        }
    }
    class DepthFirstSearc
    {
        int[,] matrix;
        Vertex[] vexs;
        Edge[] edges;
        public void Matrix(Vertex[] vexs,Edge[] edges)
        {
            matrix = new int[vexs.Length, vexs.Length];
            this.vexs = vexs;
            this.edges = edges;

            for (int i = 0; i < edges.Length; i++)
            {
                int tail = edges[i].tail;
                int head = edges[i].head;
                matrix[tail, head] = 1;
                matrix[head, tail] = 1;
            }
            Console.Write("    ");
            for (int i = 0; i < vexs.Length; i++)
            {
                Console.Write(vexs[i].data + "    ");
            }
            Console.WriteLine("\n");
            for (int i = 0; i < vexs.Length; i++)
            {
                Console.Write(vexs[i].data + "  ");
                for (int j = 0; j < vexs.Length; j++)
                {
                    Console.Write("[" + matrix[i, j] + "]  ");
                }
                Console.WriteLine("\n");
            }
        }
        public void DFS()
        {
            Stack<int> stack = new Stack<int>();
            bool[] visited = new bool[vexs.Length];
            int visitedCount = 1;
            int index = 0;

            Console.Write("[" + vexs[0].data + "]");
            visited[index] = true;

            while (true)
            {
                for (int i = 0; i < vexs.Length; i++)
                {
                    if(matrix[index,i] == 1 && visited[i] == false)
                    {
                        Console.Write("[" + vexs[i].data + "]");
                        stack.Push(index);
                        visited[i] = true;
                        visitedCount++;
                        index = i;
                        break;
                    }
                    if (i >= vexs.Length - 1 && stack.Count > 0)
                    {
                        index = stack.Pop();
                        i = -1;
                    }
                }
                if (visitedCount == vexs.Length)
                {
                    break;
                }
            }
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            DepthFirstSearc dfs = new DepthFirstSearc();
            Vertex vex0 = new Vertex(0);
            Vertex vex1 = new Vertex(1);
            Vertex vex2 = new Vertex(2);
            Vertex vex3 = new Vertex(3);
            Vertex vex4 = new Vertex(4);
            Edge edge0 = new Edge(0, 1);
            Edge edge1 = new Edge(0, 2);
            Edge edge2 = new Edge(1, 4);
            Edge edge3 = new Edge(2, 4);
            Edge edge4 = new Edge(3, 4);
            Vertex[] vexs = new Vertex[] { vex0, vex1, vex2, vex3, vex4 };
            Edge[] edges = new Edge[] { edge0, edge1, edge2, edge3, edge4 };

            dfs.Matrix(vexs, edges);
            dfs.DFS();

            Console.ReadLine();
        }
    }
}