[C++로 배우는 알고리즘과 자료구조 심화] Day 11: 강한 연결 요소 (Kosaraju, Tarjan 알고리즘)

강한 연결 요소 (Strongly Connected Components, SCC)

강한 연결 요소(SCC)는 방향 그래프에서 각 정점이 서로 도달 가능한 최대 부분 그래프입니다. 즉, SCC의 모든 정점 u, v에 대해 u에서 v로 가는 경로와 v에서 u로 가는 경로가 모두 존재합니다.

Kosaraju's Algorithm

Kosaraju's Algorithm은 그래프를 두 번의 DFS로 탐색하여 SCC를 찾는 알고리즘입니다.

Kosaraju's Algorithm의 단계:

1. DFS: 원본 그래프에서 DFS를 수행하여 정점을 완료된 순서대로 스택에 저장합니다.
2. 전치 그래프 생성: 모든 간선의 방향을 반전시킨 그래프를 만듭니다.
3. DFS: 스택에서 정점을 꺼내어 전치 그래프에서 DFS를 수행합니다.

Kosaraju's Algorithm의 시간 복잡도:

• (O(V + E)), 여기서 (V)는 정점의 수, (E)는 간선의 수입니다.

Kosaraju's Algorithm 구현

#include <iostream>
#include <vector>
#include <stack>

class Graph {
public:
    Graph(int vertices);
    void addEdge(int u, int v);
    void kosaraju();

private:
    int vertices;
    std::vector<std::vector<int>> adjList;
    std::vector<std::vector<int>> transpose;

    void fillOrder(int v, std::vector<bool>& visited, std::stack<int>& Stack);
    void DFSUtil(int v, std::vector<bool>& visited);
    void getTranspose();
};

Graph::Graph(int vertices) {
    this->vertices = vertices;
    adjList.resize(vertices);
    transpose.resize(vertices);
}

void Graph::addEdge(int u, int v) {
    adjList[u].push_back(v);
}

void Graph::DFSUtil(int v, std::vector<bool>& visited) {
    visited[v] = true;
    std::cout << v << " ";
    for (int i : adjList[v]) {
        if (!visited[i]) {
            DFSUtil(i, visited);
        }
    }
}

void Graph::fillOrder(int v, std::vector<bool>& visited, std::stack<int>& Stack) {
    visited[v] = true;
    for (int i : adjList[v]) {
        if (!visited[i]) {
            fillOrder(i, visited, Stack);
        }
    }
    Stack.push(v);
}

void Graph::getTranspose() {
    for (int v = 0; v < vertices; ++v) {
        for (int i : adjList[v]) {
            transpose[i].push_back(v);
        }
    }
}

void Graph::kosaraju() {
    std::stack<int> Stack;
    std::vector<bool> visited(vertices, false);

    for (int i = 0; i < vertices; ++i) {
        if (!visited[i]) {
            fillOrder(i, visited, Stack);
        }
    }

    getTranspose();
    visited.assign(vertices, false);

    while (!Stack.empty()) {
        int v = Stack.top();
        Stack.pop();

        if (!visited[v]) {
            DFSUtil(v, visited);
            std::cout << std::endl;
        }
    }
}

int main() {
    Graph g(5);
    g.addEdge(1, 0);
    g.addEdge(0, 2);
    g.addEdge(2, 1);
    g.addEdge(0, 3);
    g.addEdge(3, 4);

    std::cout << "강한 연결 요소 (SCC)들은 다음과 같습니다:\n";
    g.kosaraju();

    return 0;
}

 

Tarjan's Algorithm

Tarjan's Algorithm은 하나의 DFS로 SCC를 찾는 알고리즘입니다. DFS의 방문 순서를 이용하여 각 정점의 DFS 번호와 저위 링크 값을 계산합니다.

Tarjan's Algorithm의 단계:

1. DFS: 그래프를 DFS로 탐색하며 각 정점의 DFS 번호와 저위 링크 값을 계산합니다.
2. SCC 추출: DFS 트리에서 SCC를 추출합니다.

Tarjan's Algorithm의 시간 복잡도:

• (O(V + E)), 여기서 (V)는 정점의 수, (E)는 간선의 수입니다.

Tarjan's Algorithm 구현

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

class Graph {
public:
    Graph(int vertices);
    void addEdge(int u, int v);
    void tarjansSCC();

private:
    int vertices;
    std::vector<std::vector<int>> adjList;

    void SCCUtil(int u, std::vector<int>& disc, std::vector<int>& low, std::stack<int>& stk, std::vector<bool>& inStack);

    int time;
};

Graph::Graph(int vertices) {
    this->vertices = vertices;
    adjList.resize(vertices);
}

void Graph::addEdge(int u, int v) {
    adjList[u].push_back(v);
}

void Graph::SCCUtil(int u, std::vector<int>& disc, std::vector<int>& low, std::stack<int>& stk, std::vector<bool>& inStack) {
    static int time = 0;
    disc[u] = low[u] = ++time;
    stk.push(u);
    inStack[u] = true;

    for (int v : adjList[u]) {
        if (disc[v] == -1) {
            SCCUtil(v, disc, low, stk, inStack);
            low[u] = std::min(low[u], low[v]);
        } else if (inStack[v]) {
            low[u] = std::min(low[u], disc[v]);
        }
    }

    int w = 0;
    if (low[u] == disc[u]) {
        while (stk.top() != u) {
            w = stk.top();
            std::cout << w << " ";
            inStack[w] = false;
            stk.pop();
        }
        w = stk.top();
        std::cout << w << " ";
        inStack[w] = false;
        stk.pop();
        std::cout << std::endl;
    }
}

void Graph::tarjansSCC() {
    std::vector<int> disc(vertices, -1);
    std::vector<int> low(vertices, -1);
    std::vector<bool> inStack(vertices, false);
    std::stack<int> stk;

    for (int i = 0; i < vertices; ++i) {
        if (disc[i] == -1) {
            SCCUtil(i, disc, low, stk, inStack);
        }
    }
}

int main() {
    Graph g(5);
    g.addEdge(1, 0);
    g.addEdge(0, 2);
    g.addEdge(2, 1);
    g.addEdge(0, 3);
    g.addEdge(3, 4);

    std::cout << "강한 연결 요소 (SCC)들은 다음과 같습니다:\n";
    g.tarjansSCC();

    return 0;
}

 

설명

1. Kosaraju's Algorithm:
   • 원본 그래프에서 DFS를 수행하여 각 정점을 스택에 저장합니다.
   • 전치 그래프를 생성하여, 저장된 순서대로 전치 그래프에서 DFS를 수행합니다.
   • DFS를 수행하며 SCC를 찾습니다.
2. Tarjan's Algorithm:
   • DFS를 수행하며 각 정점의 방문 순서와 저위 링크 값을 계산합니다.
   • 스택을 사용하여 SCC를 추출합니다.
   • 저위 링크 값이 DFS 번호와 같은 정점을 찾으면 SCC를 출력합니다.

강한 연결 요소(SCC)를 찾는 Kosaraju와 Tarjan 알고리즘의 개념과 구현 방법을 이해했습니다. 질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 12: 네트워크 흐름 알고리즘 (Ford-Fulkerson, Edmonds-Karp)"에 대해 학습하겠습니다.