코사라주 알고리즘(Kosaraju's Algorithm)

코사라주 알고리즘(Kosaraju's Algorithm)

• 그래프에서 강한 연결 요소를 찾는 가장 쉽고 널리 사용되는 방법
• DFS를 2번 수행하는 형태로 동작함.
  • ① 입력 그래프 자체에 DFS를 수행함.
  • ② 입력 그래프를 전치하여 DFS를 수행함.
• 코사라주 알고리즘은 일반적으로 DFS 방식 의 순회를 사용하지만, BFS 도 사용할 수 있음.
  • DFS 방식이 전통적인 방식
• 복잡할 수 있는 문제를 직관적으로 단순화하는 측면에서 매우 효과적이며, 구현하기도 쉬운 편임.
• 입력 그래프가 인접 리스트 로 표현되어 있을 경우, O(V + E) 형태의 선형 점근적 시간 복잡도 를 갖기 떄문에 매우 효율적임.
  • 코사라주 알고리즘에서 인접 행렬 을 사용하는 것은 권장되지 않음.
    • 그래프 순회에서 각 정점의 이웃을 찾기 위해 상당한 양의 반복문이 필요하기 때문

 

동작 방식

① 입력 그래프 자체에 DFS 수행

• 모든 정점 중에서 아직 방문한 적이 없는 정점에 대해 차례대로 DFS 순회를 수행함.
• 각 정점에 대해 DFS를 수행할 때
  • 먼저 해당 정점에 대해 방문 기록을 저장함.
  • 이후 이 정점과 인접한 정점 중에서 아직 방문하지 않은 정점을 재귀적으로 탐색함.
• 인접한 정점을 모두 탐색한 후에는 현재 정점을 스택(Stack) 에 추가한 후, DFS를 종료함.

② 입력 그래프를 전치하여 DFS 수행

• 원본 그래프에 대해 DFS 순회가 끝나면, 이번에는 같은 작업을 전치 그래프 에 대해 수행함.
• 앞서 구축한 스택s에서 정점을 하나씩 꺼내고, 이 정점을 아직 방문하지 않아다면 이 정점을 시작으로 DFS를 수행함.
  • 이때 각각의 DFS에서 만나는 정점들이 강한 연결 요소를 구성함.

 

코드

• 입력 그래프

 

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

void FillStack(int node, vector<bool>& visited, vector<vector<int>>& adj, stack<int>& stack) {
    visited[node] = true;

    for (auto next : adj[node]) {
        if (!visited[next]) {
            FillStack(next, visited, adj, stack);
        }
    }

    stack.push(node);
}

vector<vector<int>> Transpose(int V, vector<vector<int>> adj) {
    vector<vector<int>> transpose(V);

    for (int i = 0; i < V; i++) {
        for (auto next : adj[i]) {
            transpose[next].push_back(i);
        }
    }

    return transpose;
}

void CollectConnectedComponents(int node, vector<bool>& visited, vector<vector<int>>& adj, vector<int>& component) {
    visited[node] = true;
    component.push_back(node);

    for (auto next : adj[node]) {
        if (!visited[next]) {
            CollectConnectedComponents(next, visited, adj, component);
        }
    }
}

vector<vector<int>> Kosaraju(int V, vector<vector<int>> adj) {
    vector<bool> visited(V, false);
    stack<int> stack;

    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            FillStack(i, visited, adj, stack);
        }
    }

    vector<vector<int>> transpose = Transpose(V, adj);

    fill(visited.begin(), visited.end(), false);

    vector<vector<int>> connectedComponents;

    while (!stack.empty()) {
        int node = stack.top();
        stack.pop();

        if (!visited[node]) {
            vector<int> component;

            CollectConnectedComponents(node, visited, transpose, component);
            connectedComponents.push_back(component);
        }
    }

    return connectedComponents;
}

int main() {
    int  V = 9;
    vector<vector<int>> adj = {
        {1, 3},
        {2, 4},
        {3, 5},
        {7},
        {2},
        {4, 6},
        {7, 2},
        {8},
        {3}
    };

    vector<vector<int>> connectedComponents = Kosaraju(V, adj);

    cout << "강한 연결 요소 개수: " << connectedComponents.size() << endl;

    for (int i = 0; i < connectedComponents.size(); i++) {
        cout << "[" << i + 1 << "] ";
        for (auto node : connectedComponents[i]) {
            cout << node << " ";
        }
        cout << endl;
    }

    return 0;
}

 

결과

강한 연결 요소 개수: 4
[1] 0
[2] 1
[3] 2 4 5 6
[4] 3 8 7