C++에서 그래프가 강하게 연결되었는지 확인하는 방법 – DFS 기반 Kosaraju 알고리즘 (Set 1)

그래프가 강하게 연결(strongly connected)되어 있는지 판별해야 하는 상황이 자주 있습니다. 임의의 두 정점을 골랐을 때 서로에게 도달하는 경로가 항상 존재한다면, 그 그래프는 강하게 연결된 그래프라고 합니다. 무방향 그래프에서는 단순히 연결만 되어 있으면 곧 강하게 연결된 것과 같습니다. 하지만 방향성이 있는 유향 그래프(directed graph)에서는 모든 정점 쌍이 양방향으로 도달 가능해야 한다는 조건이 필요합니다.

즉, 일부 유향 그래프는 연결은 되어 있더라도 강하게 연결되지 않을 수 있습니다. 아래는 강하게 연결된 그래프의 예시입니다.

다음은 연결은 되어 있지만 강하게 연결되지는 않은 그래프의 예시입니다.

Kosaraju 알고리즘의 동작 원리

여기서는 Kosaraju 알고리즘을 활용해 그래프가 강하게 연결되었는지 확인하는 방법을 살펴보겠습니다. 이 방법의 핵심 아이디어는 간단합니다. 어떤 정점에서 출발한 DFS 탐색이 모든 노드를 방문할 수 있다면 순방향으로 도달 가능하다는 뜻이고, 모든 간선의 방향을 뒤집은 뒤에도 같은 정점에서 모든 노드를 방문할 수 있다면 역방향으로도 도달 가능하다는 의미입니다. 두 조건이 모두 충족될 때만 그래프는 강하게 연결된 것입니다.

알고리즘 단계

• 모든 노드를 '방문하지 않음' 상태로 표시합니다.

• 임의의 정점 u에서 DFS 탐색을 시작합니다. 이때 DFS가 모든 노드를 방문하지 못한다면 false를 반환합니다.

• 그래프의 모든 간선 방향을 반대로 뒤집습니다.

• 모든 정점을 다시 '방문하지 않음' 상태로 초기화합니다.

• 같은 정점 u에서 다시 DFS 탐색을 수행합니다. 모든 노드를 방문하지 못하면 false를 반환하고, 성공적으로 모든 노드를 방문했다면 true를 반환합니다.

C++ 구현 예제

#include <iostream>
#include <list>
#include <stack>
using namespace std;
class Graph {
    int V;
    list<int> *adj;
    void dfs(int v, bool visited[]);
    public:
    Graph(int V) {
        this->V = V;
        adj = new list<int>[V];
    }
    ~Graph() {
        delete [] adj;
    }
    void addEdge(int v, int w);
    bool isStronglyConnected();
    Graph reverseArc();
};
void Graph::dfs(int v, bool visited[]) {
    visited[v] = true;
    list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
    if (!visited[*i])
        dfs(*i, visited);
}
Graph Graph::reverseArc() {
    Graph graph(V);
    for (int v = 0; v < V; v++) {
        list<int>::iterator i;
        for(i = adj[v].begin(); i != adj[v].end(); ++i)
        graph.adj[*i].push_back(v);
    }
    return graph;
}
void Graph::addEdge(int u, int v) {
    adj[u].push_back(v);
}
bool Graph::isStronglyConnected() {
    bool visited[V];
    for (int i = 0; i < V; i++)
    visited[i] = false;
    dfs(0, visited);
    for (int i = 0; i < V; i++)
    if (visited[i] == false)
        return false;
    Graph graph = reverseArc();
    for(int i = 0; i < V; i++)
    visited[i] = false;
    graph.dfs(0, visited);
    for (int i = 0; i < V; i++)
    if (visited[i] == false)
        return false;
    return true;
}
int main() {
    Graph graph(5);
    graph.addEdge(0, 1);
    graph.addEdge(1, 2);
    graph.addEdge(2, 3);
    graph.addEdge(3, 0);
    graph.addEdge(2, 4);
    graph.addEdge(4, 2);
    graph.isStronglyConnected()? cout << "This is strongly connected" : cout << "This is not strongly connected";
}

실행 결과

This is strongly connected

위 예제 코드는 5개의 정점을 가진 그래프를 생성하고, 정점 0에서 시작하는 두 번의 DFS 탐색(원본 그래프와 간선이 뒤집힌 그래프)을 통해 해당 그래프가 강하게 연결되어 있음을 확인합니다. 이 알고리즘의 시간 복잡도는 O(V+E)로, 정점과 간선의 수에 비례하여 효율적으로 동작합니다.