[c++] 그래프의 지름 찾기

08 Dec 2023

그래프의 지름은 그래프에서 가장 먼 두 정점 사이의 거리를 나타냅니다. 보다 공식적으로는 그래프에서 모든 정점 쌍 간의 거리 중 최댓값을 의미합니다. 여기서는 그래프의 지름을 찾는 효율적인 방법에 대해 알아보겠습니다.

그래프의 지름 찾는 알고리즘

가장 간단하게는 모든 정점 쌍 간의 거리를 구하고, 그 중에서 최댓값을 찾는 방법이 있지만, 이는 비효율적입니다. 대부분의 상황에서 그래프의 지름을 효율적으로 찾기 위해 BFS(Breadth-First Search)나 DFS(Depth-First Search) 알고리즘을 사용할 수 있습니다. 여기서는 BFS 알고리즘을 사용하여 그래프의 지름을 찾는 과정을 살펴보겠습니다.

BFS 알고리즘을 활용한 그래프의 지름 찾기

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int findFarthestVertex(int start, vector<vector<int>>& graph) {
    queue<int> q;
    vector<bool> visited(graph.size(), false);
    vector<int> dist(graph.size(), 0);
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int curr = q.front();
        q.pop();

        for (int next : graph[curr]) {
            if (!visited[next]) {
                visited[next] = true;
                dist[next] = dist[curr] + 1;
                q.push(next);
            }
        }
    }

    return max_element(dist.begin(), dist.end()) - dist.begin();
}

int findGraphDiameter(vector<vector<int>>& graph) {
    int start = findFarthestVertex(0, graph);
    int end = findFarthestVertex(start, graph);
    return findFarthestVertex(end, graph);
}

int main() {
    int n = 6;
    vector<vector<int>> graph(n);

    graph[0] = {1, 2};
    graph[1] = {0, 3, 4};
    graph[2] = {0, 5};
    graph[3] = {1};
    graph[4] = {1};
    graph[5] = {2};

    int diameter = findGraphDiameter(graph);
    cout << "그래프의 지름: " << diameter << endl;

    return 0;
}

위의 코드는 BFS 알고리즘을 활용하여 그래프의 지름을 찾는 과정을 보여줍니다.

시간 복잡도

BFS 알고리즘을 통해 그래프의 지름을 찾는 시간 복잡도는 O(V + E)입니다. 여기서 V는 정점의 수, E는 간선의 수를 나타냅니다.

결론

그래프의 지름을 찾는 문제는 BFS나 DFS를 활용하여 효율적으로 해결할 수 있습니다. 이러한 알고리즘을 통해 그래프의 구조를 파악하고, 그래프 이론과 네트워크 분석 등 다양한 분야에 응용할 수 있습니다.

참고 문헌:

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms. MIT press.