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

namespace BFS
{
    class Program
    {
        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 BreadthFirstSearch
        {
            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 BFS()
            {
                Queue<int> queue = new Queue<int>();
                bool[] visited = new bool[vexs.Length];
                queue.Enqueue(0);
                visited[0] = true;
                while (queue.Count > 0)
                {
                    int index = queue.Dequeue();
                    Console.Write("[" + vexs[index].data + "]");
                    for (int i = 0; i < vexs.Length; i++)
                    {
                        if (matrix[index, i] == 1 && visited[i] == false)
                        {
                            visited[i] = true;
                            queue.Enqueue(i);
                        }
                    }
                }
            }
            static void Main(string[] args)
            {
                BreadthFirstSearch bfs = new BreadthFirstSearch();
                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 };

                bfs.Matrix(vexs, edges);
                bfs.BFS();

                Console.ReadLine();
            }
        }
    }
}