using System;

​

public class Node

{

    private int key;

    public int Key

    {

        get

        {

            return key;

        }

    }

​

    public Node Next

    {

        get;

        set;

    }

​

    public Node(int key)

    {

        this.key = key;

    }

}

​

public class Queue

{

    private Node front;

    private Node rear;

    public Queue()

    {

        front = rear = null;

    }

​

    public bool IsEmpty()

    {

        return (front == null);

    }

​

    public void EnQueue(int key)

    {

        Node node = new Node(key);

        if (node != null)

        {

            if (this.IsEmpty())

                front = rear = node;

            else

            {

                rear.Next = node;

                rear = node;

                rear.Next = null;

            }

        }

    }

​

    public int DeQueue()

    {

        if (this.IsEmpty())

            return Int32.MinValue;

        int key = front.Key;

        if (front == rear)

        {

            front.Dispose();

            front = rear = null;

        }

        else

        {

            Node next = front.Next;

            front.Dispose();

            front = next;

        }

​

        return key;

    }

​

    public int Front()

    {

        if (this.IsEmpty())

            return Int32.MinValue;

        return front.Key;

    }

​

    public void RemoveQueue()

    {

        while (!this.IsEmpty())

            DeQueue();

    }

}

​

public class main

{

    public static void Main()

    {

    }

​

    static void BFS(int[, ] edge, int n, int x, int y)

    {

        bool[] visited = new bool[n];

        Queue queue = new Queue();

        int[] previous = new int[n];

        for (int i = 0; i < n; i++)

            visited[i] = false;

        visited[x] = true;

        previous[x] = -1;

        queue.EnQueue(x);

        do

        {

            int i = queue.DeQueue();

            for (int j = 0; j < n; j++)

            {

                if (i != j && edge[i, j] != Int32.MaxValue && !visited[j])

                {

                    visited[j] = true;

                    previous[j] = i;

                    if (j == y)

                    {

                        queue.RemoveQueue();

                        break;

                    }

                    else

                    {

                        queue.EnQueue(j);

                    }

                }

            }

        }

        while (!queue.IsEmpty());

        if (!visited[y])

            MessageBox.Show("Không tìm thấy");

        else

            DrawPath(previous, y);

    }

​

    static void DrawPath(int[] previous, int x)

    {

        while (previous[x] != -1)

        {

            DrawLine(previous[x], x);

            x = previous[x];

        }

    }

    static void DrawLine(int x,int y)

    {

    }

}