(C#) BFS

📌BFS 너비 우선 탐색

시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다

특징

Queue를 이용해 방문할 노드를 예약(Enqueue) 후 선입선출(LIFO) 원칙으로 탐색한다.
예약한 노드는 반드시 방문 여부를 검사 해야한다.
- 하지 않았을 때 무한 루프에 빠질 수 있다.

구현 코드

class Graph
{
    private int _nodeCount;
    private List<int>[] _adj;

    public Graph(int nodeCount)
    {
        _nodeCount = nodeCount;
        _adj = new List<int>[nodeCount];
        for (int i = 0; i < nodeCount; i++)
            _adj[i] = new List<int>();
    }

    public void AddEdge(int v, int edge)
    {
        _adj[v].Add(edge);
    }

    public void BFS(int startNode)
    {
        bool[] visited = new bool[_nodeCount];
        visited[startNode] = true;

        Queue<int> queue = new Queue<int>();
        queue.Enqueue(startNode);

        while (queue.Count > 0)
        {
            int now = queue.Dequeue();                
            Console.WriteLine(now);

            foreach (int n in _adj[now])
            {
                if (visited[n])
                    continue;

                visited[n] = true;
                queue.Enqueue(n);
            }
        }
    }
}

위 그림과 같은 구조를 가지는 그래프에서 BFS를 구현하면 다음과 같이 된다.

static void Main()
{
    Graph graph = new Graph(6);

    graph.AddEdge(0, 1);
    graph.AddEdge(0, 3);
    graph.AddEdge(1, 0);
    graph.AddEdge(1, 2);
    graph.AddEdge(1, 3);
    graph.AddEdge(2, 1);
    graph.AddEdge(2, 4);
    graph.AddEdge(3, 0);
    graph.AddEdge(3, 1);
    graph.AddEdge(3, 5);
    graph.AddEdge(4, 2);
    graph.AddEdge(5, 3);
}

그리고 BFS 시작을 0번 정점부터 한다고 하면