[자료구조] 그래프 BFS(너비우선탐색)

그래프의 탐색

-길이우선탐색(DFS) : 자식까지 탐색 후 다른 형제 노드를 탐색
-너비우선탐색(BFS) : 자식 전에 모든 현재 노드를 탐색_Tree Node의 label 탐색과 같음
방문테이블과 Queue를 사용하여 탐색

C#

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

namespace BFSpractice
{
    class Program
    {
        static int[,] map =
        {
            { 0, 1, 1, 0, 0, 0, 0 },
            { 1, 0, 0, 1, 1, 0, 0 },
            { 1, 0, 0, 0, 0, 1, 1 },
            { 0, 1, 0, 0, 0, 0, 0 },
            { 0, 1, 0, 0, 0, 0, 0 },
            { 0, 0, 1, 0, 0, 0, 0 },
            { 0, 0, 1, 0, 0, 0, 0 }
        };
        /*
        0: 서울 
        1: 대전
        2: 대구 
        3: 부산 
        4: 광주 
        5: 천안 
        6: 공주 
         */
        static int[] visited = new int[7];    //방문리스트
        static string[] label = { "서울", "대전", "대구", "부산", "광주", "천안", "공주" };
        static StringBuilder sb = new StringBuilder();

        static void Main()
        {
            for(int i = 0; i < 7; i++)
            {
                BFS(i);
            }
            Console.WriteLine();
            Console.WriteLine(sb);
        }
        static void BFS(int x)
        {
            Queue<int> q = new Queue<int>();
            q.Enqueue(x);

            while (q.Count > 0)
            {
                var v = q.Dequeue();
                if (visited[v] == 0)
                {
                    sb.Append(label[v]);
                    if(v<6)
                        sb.Append("->");
                    Console.Write("{0} ",v);
                    visited[v] = 1;

                }

                for(int y = 0; y < 7; y++)
                {
                    if (map[x, y] == 1 && visited[y] == 0)
                    {
                        q.Enqueue(y);
                    }
                }
            }
        }
    }
}