[c++] 그래프 알고리즘의 시간 복잡도 분석

08 Dec 2023

그래프 알고리즘은 다양한 응용 분야에서 사용되며, 그래프 구조를 다루기 위한 효율적인 알고리즘이 필요합니다. 그러나 그래프의 크기와 복잡성이 증가함에 따라 알고리즘의 성능과 시간 복잡도는 매우 중요해집니다. 그래프 알고리즘의 시간 복잡도를 분석하는 것은 알고리즘의 효율성을 이해하고 개선하는 데 도움이 됩니다.

그래프 알고리즘의 종류

그래프 알고리즘은 크게 두 가지 유형으로 나눌 수 있습니다: 탐색 알고리즘과 최단 경로 알고리즘.

탐색 알고리즘: 그래프 내에서 특정 노드를 탐색하거나 연결된 모든 노드를 방문하는 알고리즘입니다. 대표적인 탐색 알고리즘으로는 깊이 우선 탐색 (DFS)과 너비 우선 탐색 (BFS)이 있습니다.
최단 경로 알고리즘: 주어진 두 노드 사이의 최단 경로를 찾는 알고리즘으로, 다익스트라 알고리즘과 벨만-포드 알고리즘 등이 있습니다.

시간 복잡도 분석

깊이 우선 탐색 (DFS)

깊이 우선 탐색 알고리즘의 시간 복잡도는 O(V+E)입니다. 이는 그래프의 노드 수를 나타내는 V와 간선 수를 나타내는 E에 비례합니다.

int V; // 노드 수
int E; // 간선 수

void DFS(int v, vector<int> graph[], bool visited[]) {
    visited[v] = true;
    for (int i = 0; i < graph[v].size(); i++) {
        if (!visited[graph[v][i]]) {
            DFS(graph[v][i], graph, visited);
        }
    }
}

너비 우선 탐색 (BFS)

너비 우선 탐색 알고리즘의 시간 복잡도 또한 O(V+E)입니다.

다익스트라 알고리즘

다익스트라 알고리즘의 시간 복잡도는 O((V+E)logV)로, V는 노드 수, E는 간선 수를 나타냅니다.

#define INF 0x3f3f3f3f

int V; // 노드 수
vector<pair<int, int>> graph[V]; // 간선 정보 (도착 노드, 가중치)

void dijkstra(int src) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    vector<int> dist(V, INF);
    dist[src] = 0;
    pq.push({0, src});

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        for (pair<int, int> edge : graph[u]) {
            int v = edge.first;
            int weight = edge.second;
            if (dist[v] > dist[u] + weight) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
}

결론

그래프 알고리즘의 시간 복잡도는 알고리즘의 효율성을 이해하고 알고리즘을 선택할 때 중요한 요소입니다. 각 알고리즘의 특성에 따라 시간 복잡도가 달라지므로, 실제 문제에 적합한 알고리즘을 선택하는 것이 중요합니다.

참고 문헌

GeeksforGeeks - Time Complexity of Algorithms
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press.