그래프 탐색 (BFS)

문제

코드 구현

using System;
using System.Collections.Generic;


namespace BFS
{
    internal class Program
    {
        static int N = 7;
        static int[,] map = new int[N, N];
        static string[] cities = { "서울", "대전", "대구", "부산", "광주", "천안", "공주", };
        static int[] visited = new int[N];

        static void Main(string[] args)
        {
            int[,] edges =
            {
                {0,1},
                {0,2},
                {1,3},
                {1,4},
                {2,5},
                {2,6},
            };

            for (int i = 0; i < N - 1; i++)
            {
                int v1 = edges[i, 0];
                int v2 = edges[i, 1];

                map[v1, v2] = 1;
                map[v2, v1] = 1;
            }

            for (int X = 0; X < N; X++)
            {
                for (int Y = 0; Y < N; Y++)
                {
                    Console.Write(map[X, Y]);
                }
                Console.WriteLine();
            }

            for (int i = 0; i < N; i++)
            {
                if (visited[i] == 0) // visited[0] == 0
                {
                    BFS(i);
                }

            }
        }
        static void BFS(int X)
        {
            Queue<int> q = new Queue<int>();
            q.Enqueue(X); //서울 넣어주고 (0)
            visited[X] = 1; // 서울 방문
            Console.WriteLine("\n{0} : 정점으로 방문함 ", cities[X]); //서울출력
            while (q.Count > 0)  // q.Count == 1
            {
                X = q.Dequeue();  // 서울 빼서 (0)

                for (int Y = 0; Y < N; Y++) //7번 순회한다
                {
                    if (map[X, Y] == 1 && visited[Y] == 0) // 서울의 인덱스 요소중 간선이 있고 방문한 곳이 아니라면
                    {                                      // map[0,1] == 1 , visitied[1] == 0  => 해당 도시 출력
                        Console.Write("{0} : 간선으로 방문함 ", cities[Y]);

                        visited[Y] = 1; // 방문했으니 해당 인덱스 1
                    }
                }
                Console.WriteLine();
            }
        }
    }
}

결과창