너비 우선 탐색 BFS

 

BFS(너비 우선 탐색) 이란?

 

BFS(너비 우선 탐색)는 그래프 탐색 알고리즘 중 하나로, 시작 정점으로부터 인접한 모든 정점을 먼저 탐색하는 방법입니다. 이 알고리즘은 그래프 내의 모든 정점을 방문하고, 최단 경로를 찾거나 특정 조건을 만족하는 노드를 찾을 때 유용하게 사용됩니다.

 

BFS는 큐(Queue) 자료구조를 사용하여 구현됩니다. 탐색이 시작되면 시작 노드를 큐에 넣고 방문했다는 표시를 합니다. 그 후 큐에서 노드를 하나씩 꺼내어 해당 노드의 인접 노드를 큐에 넣고 방문했다는 표시를 합니다. 이 과정을 큐가 비어있을 때까지 반복합니다. 이러한 방식으로 탐색하면 시작 노드에서부터 거리가 가까운 노드부터 순차적으로 방문하게 됩니다.

 

BFS 코드 예시 (C#)

 

아래 코드는 그래프를 구성하고 BFS 알고리즘을 통해 그래프를 탐색하는 간단한 예시입니다. 그래프의 정점 수와 연결된 간선을 입력하여 BFS를 실행하고, 결과를 출력합니다.

 

using System;
using System.Collections.Generic;

class Graph
{
    private int V; // 정점의 개수
    private List<int>[] adj; // 인접 리스트

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

    // 노드와 연결된 간선 추가
    public void AddEdge(int v, int w)
    {
        adj[v].Add(w);
    }

    // BFS 탐색
    public void BFS(int s)
    {
        bool[] visited = new bool[V];
        Queue<int> queue = new Queue<int>();

        visited[s] = true;
        queue.Enqueue(s);

        while (queue.Count != 0)
        {
            s = queue.Dequeue();
            Console.Write(s + " ");

            foreach (int i in adj[s])
            {
                if (!visited[i])
                {
                    visited[i] = true;
                    queue.Enqueue(i);
                }
            }
        }
    }
}

class Program
{
    static void Main(string[] args)
    {
        Graph g = new Graph(4);

        g.AddEdge(0, 1);
        g.AddEdge(0, 2);
        g.AddEdge(1, 2);
        g.AddEdge(2, 0);
        g.AddEdge(2, 3);
        g.AddEdge(3, 3);

        Console.WriteLine("BFS 탐색 결과:");
        g.BFS(2);
    }
}

 

위 코드를 실행한 결과는 다음과 같습니다.

 

BFS 탐색 결과:
2 0 3 1

 

 

 

BFS 장단점

 

- 장점

• 최단 경로를 찾을 때 유용합니다.
• 모든 인접한 노드를 방문한 후에 다음 레벨의 노드를 방문하기 때문에, 레벨 단위로 탐색할 때 효과적입니다.

- 단점

• 깊이가 무한한 그래프에서는 탐색이 끝나지 않을 수 있습니다.
• 큐를 사용하기 때문에 공간 복잡도가 높을 수 있습니다.

 

BFS 사용 사례

 

• 네트워크 트래픽 분석
• 최단 경로 탐색
  
• 그래프에서의 연결 여부 확인

 

BFS 알고리즘은 네트워크 및 경로 탐색과 같은 여러 문제에 사용될 수 있으며, 그래프의 구조를 탐색하는 데 있어 강력한 도구입니다. 위의 코드 및 설명을 통해 BFS의 개념과 구현 방법에 대한 이해를 높일 수 있습니다.