program.cs

Demo s algorithm BFS

using System;
using System.Collections.Generic;
using System.Text;
using System.IO;

namespace BFS_Demo
{
    class Program
    {
        private struct DOTHI
        {
            public int[,] a;
            public int n;
            public int[] DinhTruoc;
        }
        private static DOTHI dt;        //Do thi
        private static int[] Q;         //Queue: Hang Doi
        private static int nQ;          //So phan tu cua hang doi
        private static int[] DanhDau;   //Mang danh dau

        static void Main(string[] args)
        {
            if (!DocFile("DoThi.txt")) return;
            XuatMaTran();
            int start,end;
            Console.Write("Nhap diem dau:");
            start = int.Parse(Console.ReadLine());
            Console.Write("Nhap diem ket thuc:");
            end = int.Parse(Console.ReadLine());
            BFS(start,end);
            XuatDuongDi(start,end);
        }

        public static bool DocFile(string tenFile)
        {
            //Kiem tra ton tai file
            if (!File.Exists(tenFile))
            {
                Console.WriteLine("Khong Ton Tai File");
                return false;
            }

            //Mo va doc du lieu
            FileStream f = new FileStream(tenFile, FileMode.Open, FileAccess.Read);
            StreamReader rd = new StreamReader(f);
            string str = rd.ReadToEnd();
            
            //Tien hanh cat chuoi
            string[] token = new string[] {" ", "\t", "\r\n"};
            string[] mangChuoi = str.Split(token,StringSplitOptions.None);
            
            dt.n = int.Parse(mangChuoi[0]);     //so dinh
            int count = 1;                      
            
            dt.a = new int[dt.n, dt.n];         //cap phat bo nho            
            dt.DinhTruoc = new int[dt.n];
            DanhDau = new int[dt.n];
            
            for (int i = 0; i < dt.n; i++)
                for (int j = 0; j < dt.n; j++ )
                {
                    dt.a[i, j] = int.Parse(mangChuoi[count]);
                    count++;
                }            
            //Dong file lai    
            rd.Close();
            f.Close();
            return true;
        }        

        //Hien thi ma tran
        public static void XuatMaTran()
        {
            for (int i = 0; i < dt.n; i++ )
            {
                for (int j = 0; j < dt.n; j++ )
                {
                    Console.Write(dt.a[i, j].ToString() + " ");
                }
                Console.Write("\n");
            }
        }
        //Day mot phan tu vao hang doi
        public static void PushQ(int k)
        {
            Q[nQ] = k;
            nQ++;
        }

        //Lay mot phan tu ra khoi hang doi
        public static int PopQ()
        {
            //Neu hang doi rong thi tra ve -1
            if (nQ == 0) return -1;

            int result = Q[0];        //lay phan tu o dau hang doi
            //Tien hanh do^`n
            for (int i = 0; i < nQ-1; i++ )
            {
                Q[i] = Q[i + 1];
            }
            nQ--;
            return result;
        }

        //Duyet theo chieu rong BFS
        //Tra ve -1 neu khong tim thay 
        //Tra ve 1 neu tim thay 
        public static int BFS(int start, int end)
        {
            if (start == end) return 1;
            //Khoi tao dinh truoc la -1 => chua co, danh dau la 0
            for (int i = 0; i<dt.n; i++)           
            {
                dt.DinhTruoc[i] = -1;            
                DanhDau[i] = 0;         
            }
            //Khoi tao hang doi va day phan tu dau vao hang doi
            Q = new int[dt.n];
            PushQ(start);

            //lay phan tu dau tien ra xet
            int x = PopQ();
            DanhDau[x] = 1;
            while (x!= -1)
            {
                for (int i = 0; i < dt.n; i++ )
                {
                    //Thoa man chua xet va co canh noi
                    if (DanhDau[i] == 0 && dt.a[x,i] == 1)
                    {
                        PushQ(i);
                        dt.DinhTruoc[i] = x;
                        DanhDau[i] = 1;
                        if (i == end) return 1;     //da tim thay
                    }
                }
                //Lay phan tu ra xet tiep
                x = PopQ();                
            }
            return 1;
        }

        //Xuat ra duong di
        public static void XuatDuongDi(int start,int end)
        {
            if (start == end)
            {
                Console.Write(start.ToString());
                return;
            }
            for (int j = 0; j < dt.n;j++ )
            {
                Console.Write(dt.DinhTruoc[j].ToString()+" ");
            }
            Console.Write("\n");
            int[] DuongDi = new int[dt.n];      //mang luu lai duong di (luu nguoc)
            int nDuongDi;
            int x = end;
            DuongDi[0] = x;
            nDuongDi = 1;            
            while (x != start)
            {
                x = dt.DinhTruoc[x];
                DuongDi[nDuongDi] = x;
                nDuongDi ++;
            }

            //In ra duong di
            for (int i = nDuongDi-1; i >= 0; i-- )
            {
                Console.Write(DuongDi[i].ToString() + " -->");
            }
        }
    }
}