그래프 이론 기초 및 너비 우선 탐색(Breadth-First Search) 알고리즘 C# 구현

안녕하세요! 오늘의 기술 면접 지식은 그래프 이론과 너비 우선 탐색(Breadth-First Search, BFS) 알고리즘에 관한 것입니다. 이 포스팅에서는 그래프 이론의 기본 개념과 너비 우선 탐색 알고리즘의 C# 예제 코드를 살펴봅니다.

그래프 이론 개요

그래프는 객체들 간의 상호 관계를 표현하는 자료구조입니다. 객체들은 정점(Vertex)이라고 불리며, 정점들 간의 관계는 간선(Edge)으로 나타냅니다. 그래프는 다양한 알고리즘에 사용되며, 그 중 하나가 너비 우선 탐색(BFS)입니다.

너비 우선 탐색 (Breadth-First Search)

너비 우선 탐색은 그래프에서 시작 정점으로부터 인접한 정점들을 먼저 방문하고, 더 이상 방문할 인접 정점이 없을 때 다음 레벨의 정점들을 순차적으로 방문하는 알고리즘입니다. BFS는 주로 최단 경로 문제를 해결하는 데 사용됩니다.

C#을 사용한 너비 우선 탐색 구현

아래 예제 코드는 너비 우선 탐색 알고리즘을 C#으로 구현한 것입니다.

 

public static List<int> BFS(Dictionary<int, List<int>> graph, int start)
{
    Queue<int> queue = new Queue<int>();
    HashSet<int> visited = new HashSet<int>();

    queue.Enqueue(start);
    visited.Add(start);

    List<int> result = new List<int>();

    while (queue.Count > 0)
    {
        int current = queue.Dequeue();
        result.Add(current);

        foreach (int neighbor in graph[current])
        {
            if (!visited.Contains(neighbor))
            {
                queue.Enqueue(neighbor);
                visited.Add(neighbor);
            }
        }
    }

    return result;
}

 

이 코드는 그래프를 인접 리스트(Adjacent List)로 표현하고, 시작 정점에서부터 BFS로 탐색한 결과를 반환합니다.

 

너비 우선 탐색(BFS) 알고리즘은 그래프에서 최단 경로를 찾거나, 그래프의 연결 요소를 찾는 데 사용되는 중요한 알고리즘입니다. 기술 면접에서 그래프 이론과 너비 우선 탐색에 대한 질문이 나올 경우, 이러한 원리와 구현 예시를 활용하여 답변할 수 있습니다. 다음 포스팅에서 또 다른 주제로 찾아뵙겠습니다!