[알고리즘] 너비 우선 탐색, BFS(Breadth-First Search) 코드 구현

너비 우선 탐색에 대한 개념은 아래 포스팅을 참조하면 된다.

[알고리즘] 너비 우선 탐색 (BFS, Breadth-First Search)

 

너비 우선 탐색은 Queue(큐)를 이용해서 코드로 구현할 수 있다.

 

C# 코드를 통해 BFS를 구현해 보겠다.

그래프 예시

---

큐(Queue)를 이용한 반복 구현

너비 우선 탐색은 Queue를 이용해서 구현할 수 있으며, 한 정점을 방문하면 인접한 정점을 모두 Queue에 담고 Queue에 담긴 정점을 꺼내 Queue에 담긴 모든 노드를 방문할 때 까지 반복하였다.

// 인접 리스트를 이용한 방향성 있는 그래프
class Graph
{
    private int vertex; // 정점
    private List<int>[] adj; // adjacency, 그래프의 인접 목록

    public Graph(int v)
    {
        vertex = v;
        adj = new List<int>[v];
        for (int i = 0; i < v; i++)
            adj[i] = new List<int>();
    }

    // 간선 추가 (v → w)
    public void addEdge(int v, int w)
    {
        adj[v].Add(w);
    }

    // DFS에 사용되는 함수
    public void BFSUtill(int v, bool[] visited)
    {
        // 스택 생성
        Queue<int> queue = new Queue<int>();
        queue.Enqueue(v);

        while(queue.Count > 0)
        {
            int vt = queue.Dequeue();

            // 방문 하고 출력
            visited[vt] = true;
            Console.Write(vt + " ");

            // 인접 노드 담기
            foreach(int neighbor in adj[vt])
            {
                if (!visited[neighbor])
                    queue.Enqueue(neighbor);
            }
        }

    }

    // DFS 탐색
    public void BFS()
    {
        bool[] visited = new bool[vertex];

        // 모든 정점을 하나씩 방문
        for (int i = 0; i < vertex; i++)
        {
            if (!visited[i])
                BFSUtill(i, visited);
        }
    }

    // 시작점v에서 DFS 탐색
    public void BFS(int v)
    {
        // 노드 방문 여부
        bool[] visited = new bool[vertex];

        BFSUtill(v, visited);
    }

}

static void Main(string[] args)
{
    Graph g = new Graph(12);

    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(0, 3);
    g.addEdge(1, 4);
    g.addEdge(1, 5);
    g.addEdge(2, 6);
    g.addEdge(3, 7);
    g.addEdge(3, 8);
    g.addEdge(4, 9);
    g.addEdge(6, 10);
    g.addEdge(8, 11);

    g.BFS(3); // 3 7 8 11
    g.BFS(); // 0 1 2 3 4 5 6 7 8 9 10 11
}

 

---

관련 문제

[C#][프로그래머스] 게임 맵 최단거리

 

 

---

참고 사이트

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html