그래프 이론의 기초와 너비 우선 탐색(Breadth-First Search) 알고리즘 이해, C# 예제 코드

안녕하세요! 오늘의 기술 면접 지식은 그래프 이론의 기초와 너비 우선 탐색(Breadth-First Search, BFS) 알고리즘에 관한 것입니다. 이 포스팅에서는 그래프의 개념과 종류, 너비 우선 탐색 알고리즘의 원리, C#을 사용한 구현 예시에 대해 알아봅니다.

그래프 이론의 기초

그래프는 객체들 간의 이진 관계를 모델링하는 자료 구조입니다. 그래프는 노드(Node, 정점)와 엣지(Edge, 간선)로 구성되며, 엣지는 노드들 사이의 연결을 나타냅니다. 그래프는 주로 두 가지 종류로 나뉩니다.

 

• 무방향 그래프(Undirected Graph): 엣지에 방향이 없는 그래프입니다. A와 B 사이의 연결은 A -> B 와 B -> A가 모두 성립합니다.
• 방향 그래프(Directed Graph): 엣지에 방향이 있는 그래프입니다. A와 B 사이의 연결은 A -> B 또는 B -> A 중 하나만 성립할 수 있습니다.

너비 우선 탐색 알고리즘 원리

너비 우선 탐색(BFS)은 그래프를 탐색하는 알고리즘 중 하나로, 시작 노드에서 가까운 노드부터 차례대로 방문하는 방식을 사용합니다. BFS는 큐(Queue)를 사용하여 노드를 방문하고 인접한 노드들을 큐에 넣습니다. 큐에서 노드를 꺼내 방문하면서 인접한 노드들을 확인하고 방문하지 않은 노드를 큐에 추가하는 과정을 반복합니다.

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

 

using System;
using System.Collections.Generic;

public class Graph
{
    private int _vertices;
    private List<int>[] _adjacencyList;

    public Graph(int vertices)
    {
        _vertices = vertices;
        _adjacencyList = new List<int>[vertices];

        for (int i = 0; i < vertices; i++)
        {
            _adjacencyList[i] = new List<int>();
        }
    }

    public void AddEdge(int source, int destination)
    {
        _adjacencyList[source].Add(destination);
    }

    public void BFS(int startNode)
    {
        bool[] visited = new bool[_vertices];
        Queue<int> queue = new Queue<int>();

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

        while (queue.Count > 0)
        {
            int currentNode = queue.Dequeue();
            Console.Write(currentNode + " ");

            foreach (int adjacentNode in _adjacencyList[currentNode])
            {
                if (!visited[adjacentNode])
                {
                    visited[adjacentNode] = true;
                    queue.Enqueue(adjacentNode);
                }
            }
        }
    }
}

 

위의 코드는 C#을 사용하여 너비 우선 탐색 알고리즘을 구현한 예시입니다. 그래프 클래스는 노드와 간선을 관리하며, BFS 메서드를 사용하여 너비 우선 탐색을 수행합니다.

너비 우선 탐색 알고리즘을 사용하는 예시:

 

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, 4);
graph.AddEdge(3, 5);
graph.AddEdge(4, 5);

graph.BFS(0); // 출력: 0 1 2 3 4 5

 

이상으로 그래프 이론의 기초와 너비 우선 탐색 알고리즘에 대한 기본적인 이해와 C#을 사용한 구현 예시를 살펴봤습니다. 너비 우선 탐색은 그래프를 탐색하거나 가장 가까운 노드를 찾는 데 유용한 알고리즘입니다. 다음 포스팅에서는 또 다른 기술 면접 관련 지식을 다루겠습니다. 기대해주세요!