C# BFS (너비 우선 탐색) 알고리즘 예시 간단 구현

BFS 알고리즘

BFS는 그래프나 트리의 탐색 방법 중 하나로, 루트(또는 시작) 노드에서 시작하여 레벨 단위로 탐색합니다.
먼저 루트 노드와 연결된 모든 노드를 탐색한 후, 해당 노드들과 연결된 다음 레벨의 노드를 탐색합니다.
큐(Queue) 자료구조를 사용하여 구현하며, 선입선출(FIFO) 방식으로 노드를 탐색합니다.
BFS는 최단 경로 문제, 최소 스패닝 트리, 네트워크 최적화 등 다양한 문제에 사용됩니다.

 

• 코드 작성

using System;
using System.Collections.Generic;

class Graph
{
    private int V; // 그래프의 노드(정점) 수
    private List<int>[] adjacencyList; // 그래프의 인접 리스트

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

    // 그래프에 간선을 추가합니다.
    public void AddEdge(int v, int w)
    {
        adjacencyList[v].Add(w);
    }

    // BFS로 그래프를 탐색하고 결과를 출력합니다.
    public void BFS(int startNode)
    {
        // 방문한 노드를 추적하기 위한 배열
        bool[] visited = new bool[V];

        // 큐를 사용하여 BFS 탐색
        Queue<int> queue = new Queue<int>();
        visited[startNode] = true;
        queue.Enqueue(startNode);

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

            foreach (int node in adjacencyList[startNode])
            {
                if (!visited[node])
                {
                    visited[node] = true;
                    queue.Enqueue(node);
                }
            }
        }
    }
}

class Program
{
    static void Main()
    {
        Graph graph = new Graph(6);
        graph.AddEdge(0, 1);
        graph.AddEdge(0, 2);
        graph.AddEdge(1, 3);
        graph.AddEdge(1, 4);
        graph.AddEdge(2, 4);
        graph.AddEdge(3, 5);

        Console.WriteLine("DFS 탐색 결과 (시작 노드: 0):");
        graph.BFS(0);
    }
}