그래프 알고리즘

 

그래프 알고리즘 이해하기

그래프 알고리즘은 그래프 데이터 구조를 기반으로 최단 경로, 연결성 탐색, 순회 등의 문제를 해결하는 방법을 제공합니다. 그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 데이터 구조로, 여러 문제 해결에서 매우 유용하게 쓰입니다.
이번 포스팅에서는 그래프의 기본 개념과 대표적인 그래프 알고리즘들을 소개하고, 각각의 특징과 사용 사례를 살펴보겠습니다.

---

1. 그래프(Graph) 기본 개념

1.1. 그래프 정의

그래프는 정점(Vertex)과 간선(Edge)으로 구성되며, 정점은 데이터를 표현하고 간선은 정점 간의 관계를 나타냅니다.
그래프는 방향성이 있는 유향 그래프(Directed Graph)와 방향성이 없는 무향 그래프(Undirected Graph)로 나눌 수 있습니다.

• 유향 그래프: 간선에 방향이 있으며, 정점 간의 관계가 일방적입니다.
• 무향 그래프: 간선에 방향이 없고, 정점 간의 관계가 쌍방적입니다.

1.2. 그래프 표현 방식

그래프는 주로 두 가지 방식으로 표현됩니다:

• 인접 리스트(Adjacency List): 각 정점에 연결된 정점들의 리스트로 표현하는 방식입니다. 메모리 사용량이 적으며, 연결된 정점을 탐색하는 데 유용합니다.
• 인접 행렬(Adjacency Matrix): 그래프를 2차원 배열로 표현하여, 정점 간의 연결 여부를 행렬로 나타냅니다. 모든 정점 간의 연결을 O(1)에 확인할 수 있으나, 메모리 사용량이 많습니다.

---

2. 깊이 우선 탐색(DFS: Depth First Search)

2.1. 개념

깊이 우선 탐색(DFS)은 그래프 탐색에서 가능한 한 깊이로 내려간 후 더 이상 갈 수 없을 때 이전 정점으로 돌아와 다시 탐색을 이어가는 방식입니다. DFS는 스택(Stack)이나 재귀 함수를 사용하여 구현됩니다.

2.2. 특징

• 시간 복잡도: O(V + E), V는 정점 수, E는 간선 수
• 사용 사례: 경로 탐색, 연결 요소 구하기, 순환 여부 확인

2.3. 예시

void DFS(int node, bool[] visited, List<int>[] graph)
{
    visited[node] = true;
    Console.WriteLine(node);

    foreach (var neighbor in graph[node])
    {
        if (!visited[neighbor])
        {
            DFS(neighbor, visited, graph);  // 재귀 호출을 통해 탐색
        }
    }
}

---

3. 너비 우선 탐색(BFS: Breadth First Search)

3.1. 개념

너비 우선 탐색(BFS)은 깊이보다 너비를 우선 탐색하는 방식으로, 가까운 정점부터 차례로 탐색해 나갑니다.
큐(Queue) 자료구조를 사용하여 구현됩니다. BFS는 주로 최단 경로 탐색에 사용됩니다.

3.2. 특징

• 시간 복잡도: O(V + E)
• 사용 사례: 최단 경로 탐색, 레벨별 탐색

3.3. 예시

void BFS(int start, List<int>[] graph)
{
    bool[] visited = new bool[graph.Length];
    Queue<int> queue = new Queue<int>();
    queue.Enqueue(start);
    visited[start] = true;

    while (queue.Count > 0)
    {
        int node = queue.Dequeue();
        Console.WriteLine(node);

        foreach (var neighbor in graph[node])
        {
            if (!visited[neighbor])
            {
                visited[neighbor] = true;
                queue.Enqueue(neighbor);
            }
        }
    }
}

 

---

4. 다익스트라 알고리즘 (Dijkstra's Algorithm)

4.1. 개념

다익스트라 알고리즘은 가중치 그래프에서 특정 정점으로부터 최단 경로를 찾는 알고리즘입니다.
이 알고리즘은 음의 가중치가 없는 그래프에서만 동작하며, 우선순위 큐(Priority Queue)를 사용하여 최단 경로를 점진적으로 갱신해 나가는 방식으로 구현됩니다.

4.2. 특징

• 시간 복잡도: O(E log V)
• 사용 사례: 네트워크 경로 탐색, 길 찾기

4.3. 예시

int[] Dijkstra(int start, List<(int, int)>[] graph)
{
    int[] dist = Enumerable.Repeat(int.MaxValue, graph.Length).ToArray();
    dist[start] = 0;
    PriorityQueue<int, int> queue = new PriorityQueue<int, int>();
    queue.Enqueue(start, 0);

    while (queue.Count > 0)
    {
        var (currentNode, currentDist) = queue.Dequeue();

        if (currentDist > dist[currentNode]) continue;

        foreach (var (nextNode, weight) in graph[currentNode])
        {
            int newDist = currentDist + weight;
            if (newDist < dist[nextNode])
            {
                dist[nextNode] = newDist;
                queue.Enqueue(nextNode, newDist);
            }
        }
    }

    return dist;
}

 

---

5. 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)

5.1. 개념

플로이드-워셜 알고리즘은 모든 정점 쌍 간의 최단 경로를 구하는 알고리즘입니다. 이 알고리즘은 동적 계획법(Dynamic Programming)을 이용하여 그래프의 모든 정점 간 최단 경로를 계산합니다. 음의 가중치가 있는 그래프에서도 사용할 수 있지만, 음의 사이클이 있는 경우에는 사용할 수 없습니다.

5.2. 특징

• 시간 복잡도: O(V³)
• 사용 사례: 모든 정점 간의 최단 경로 계산

5.3. 예시

int[,] FloydWarshall(int[,] graph)
{
    int V = graph.GetLength(0);
    int[,] dist = (int[,])graph.Clone();

    for (int k = 0; k < V; k++)
    {
        for (int i = 0; i < V; i++)
        {
            for (int j = 0; j < V; j++)
            {
                if (dist[i, k] + dist[k, j] < dist[i, j])
                {
                    dist[i, j] = dist[i, k] + dist[k, j];
                }
            }
        }
    }

    return dist;
}

 

---

6. 최소 신장 트리(MST: Minimum Spanning Tree)

6.1. 개념

최소 신장 트리(MST)는 가중치가 있는 그래프에서 모든 정점을 연결하는 간선들의 부분 집합으로, 그 가중치의 합이 최소가 되는 트리를 말합니다. 대표적인 알고리즘으로 크루스칼 알고리즘(Kruskal’s Algorithm)과 프림 알고리즘(Prim’s Algorithm)이 있습니다.

• 크루스칼 알고리즘: 간선을 오름차순으로 정렬하여 최소 가중치를 가지는 간선을 하나씩 추가해 가는 방식.
• 프림 알고리즘: 하나의 정점에서부터 시작하여, 인접한 정점들을 연결하는 방식.

6.2. 특징

• 시간 복잡도: O(E log E) (크루스칼), O(V²) (프림)
• 사용 사례: 네트워크 설계, 도로망 설계

---

그래프 알고리즘은 문제의 성격과 데이터 구조에 따라 다양한 방식으로 활용됩니다.
깊이 우선 탐색과 너비 우선 탐색은 주로 그래프 탐색에 사용되며, 다익스트라 알고리즘과 플로이드-워셜 알고리즘은 최단 경로 문제를 해결합니다. 또한 최소 신장 트리는 그래프에서 효율적으로 연결성을 유지하는 방법을 제공합니다. 각 알고리즘의 시간 복잡도와 특징을 고려하여 문제에 맞는 적절한 알고리즘을 선택하는 것이 중요합니다.