콘텐츠로 이동

코사라주 알고리즘

강한 연결 요소

강한 연결요소는 부분 집합에 대하여 다른 집합으로 정보를 보낼수는 있지만, 받을수는 없는 구조를 말합니다. 아래의 그림을 토대로 이해하면 편할 것입니다.

강한 연결 요소
강한연결요소

코사라주 알고리즘이란

코사라주 알고리즘은 강한 연결 요소들을 판별해내는 알고리즘입니다. 알고리즘의 메커니즘은 우선 DFS(깊이 우선 탐색)한 후 그래프의 방향을 기존에 가르치던 방향의 반대 바라보도록 만듭니다. 그 후 해당 그래프를 DFS를 하게 된다면, 강한 연결요소들이 구별될 것입니다.
책에 나온 그래프로 예시를 보여드리겠습니다. 시작 정점은 0번 정점이라 가정하고, 정점의 번호가 적은 것을 선택한다 가정하겠습니다.

그래프
image

방문 정점

0 1 2 3 7 8 5 4 6

종료 순서 스택

6 4 5 8 7 3 2 1 0

스택은 선입 후출 구조이므로 0번 정점부터 DFS를 실시 하겠습니다.

전치 그래프
image

강한 연결 요소

0                
1                
2 4 5 6          
3 7 8            

코사라주 알고리즘의 구현

#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;
    }
}
그래프
image

방향 그래프가 지시하는 것

0번 정점 1번 정점 2번 정점 3번 정점 4번 정점 5번 정점 6번 정점 7번 정점 8번 정점
1 2 3 7 2 4 7 8 3
3 4 5 6 2

실행 결과
image