그래프의 고급 탐색 - 강한 연결 요소 (Strongly Connected Components, SCC)

그래프 이론에서 강한 연결 요소(Strongly Connected Component, SCC)는 유향 그래프에서 특정 조건을 만족하는 노드 집합을 의미합니다. 이번 글에서는 SCC가 무엇인지 설명하고, 이를 찾기 위한 고급 알고리즘 두 가지 - Kosaraju 알고리즘과 Tarjan 알고리즘 - 을 Java와 C 예제로 구현해 보겠습니다.

강한 연결 요소란?

강한 연결 요소란 그래프의 모든 정점들이 서로 도달 가능한 부분 그래프를 의미합니다. 즉, 어떤 두 정점 (u, v)가 있다면, (u \rightarrow v)와 (v \rightarrow u) 경로가 모두 존재할 때 (u)와 (v)는 같은 SCC에 속한다고 말합니다.

강한 연결 요소는 그래프의 구조를 이해하는 데 중요한 정보를 제공하며, 사이클 검출 및 경로 분석과 같은 여러 그래프 관련 문제에서 유용하게 사용됩니다.

Kosaraju 알고리즘

Kosaraju 알고리즘은 두 번의 DFS(깊이 우선 탐색)를 통해 SCC를 찾는 알고리즘입니다. 다음과 같은 단계로 동작합니다:

1. 그래프의 모든 노드를 DFS로 탐색하여 완료된 순서를 기록합니다.
2. 그래프의 모든 간선을 뒤집어 전치 그래프(transpose graph)를 생성합니다.
3. 전치 그래프를 완료된 순서의 역순으로 DFS를 수행하면서 강한 연결 요소를 추출합니다.

아래는 Kosaraju 알고리즘을 Java와 C로 구현한 코드입니다.

Java로 구현한 Kosaraju 알고리즘

import java.util.*;

public class Kosaraju {
    private int V;
    private List<Integer>[] graph;
    private List<Integer>[] transposeGraph;
    private boolean[] visited;

    public Kosaraju(int vertices) {
        V = vertices;
        graph = new ArrayList[V];
        transposeGraph = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            graph[i] = new ArrayList<>();
            transposeGraph[i] = new ArrayList<>();
        }
    }

    public void addEdge(int src, int dest) {
        graph[src].add(dest);
    }

    private void dfs(int v, Stack<Integer> stack) {
        visited[v] = true;
        for (int neighbor : graph[v]) {
            if (!visited[neighbor]) {
                dfs(neighbor, stack);
            }
        }
        stack.push(v);
    }

    private void transpose() {
        for (int i = 0; i < V; i++) {
            for (int neighbor : graph[i]) {
                transposeGraph[neighbor].add(i);
            }
        }
    }

    private void dfsTranspose(int v) {
        visited[v] = true;
        System.out.print(v + " ");
        for (int neighbor : transposeGraph[v]) {
            if (!visited[neighbor]) {
                dfsTranspose(neighbor);
            }
        }
    }

    public void findSCCs() {
        Stack<Integer> stack = new Stack<>();
        visited = new boolean[V];

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

        transpose();
        visited = new boolean[V];

        while (!stack.isEmpty()) {
            int v = stack.pop();
            if (!visited[v]) {
                dfsTranspose(v);
                System.out.println();
            }
        }
    }

    public static void main(String[] args) {
        Kosaraju graph = new Kosaraju(5);
        graph.addEdge(0, 2);
        graph.addEdge(2, 1);
        graph.addEdge(1, 0);
        graph.addEdge(0, 3);
        graph.addEdge(3, 4);

        System.out.println("Strongly Connected Components:");
        graph.findSCCs();
    }
}

C로 구현한 Kosaraju 알고리즘

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX 10000

int graph[MAX][MAX], transposeGraph[MAX][MAX];
bool visited[MAX];
int V;

void addEdge(int src, int dest) {
    graph[src][dest] = 1;
}

void dfs(int v, int *stack, int *top) {
    visited[v] = true;
    for (int i = 0; i < V; i++) {
        if (graph[v][i] && !visited[i]) {
            dfs(i, stack, top);
        }
    }
    stack[(*top)++] = v;
}

void transpose() {
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            transposeGraph[i][j] = graph[j][i];
        }
    }
}

void dfsTranspose(int v) {
    visited[v] = true;
    printf("%d ", v);
    for (int i = 0; i < V; i++) {
        if (transposeGraph[v][i] && !visited[i]) {
            dfsTranspose(i);
        }
    }
}

void findSCCs() {
    int stack[MAX], top = 0;

    for (int i = 0; i < V; i++) {
        visited[i] = false;
    }
    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            dfs(i, stack, &top);
        }
    }

    transpose();

    for (int i = 0; i < V; i++) {
        visited[i] = false;
    }

    while (top > 0) {
        int v = stack[--top];
        if (!visited[v]) {
            dfsTranspose(v);
            printf("\n");
        }
    }
}

int main() {
    V = 5;
    addEdge(0, 2);
    addEdge(2, 1);
    addEdge(1, 0);
    addEdge(0, 3);
    addEdge(3, 4);

    printf("Strongly Connected Components:\n");
    findSCCs();

    return 0;
}

Tarjan 알고리즘

Tarjan 알고리즘은 단일 DFS 탐색만으로 SCC를 찾는 효율적인 방법입니다. 각 정점에 대해 DFS 탐색 시간과 최소 도달 시간을 기록하며, DFS 스택을 이용해 SCC를 추출합니다. 이 알고리즘의 시간 복잡도는 (O(V + E))로 Kosaraju 알고리즘보다 더 효율적일 수 있습니다.

Tarjan 알고리즘 구현 (Java)

import java.util.*;

class TarjanSCC {
    private int time = 0;
    private final List<List<Integer>> graph;
    private final int[] ids, low;
    private final boolean[] onStack;
    private final Deque<Integer> stack;
    private final List<List<Integer>> sccs;

    public TarjanSCC(int n) {
        graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        ids = new int[n];
        Arrays.fill(ids, -1);
        low = new int[n];
        onStack = new boolean[n];
        stack = new ArrayDeque<>();
        sccs = new ArrayList<>();
    }

    public void addEdge(int u, int v) {
        graph.get(u).add(v);
    }

    public List<List<Integer>> findSCCs() {
        for (int i = 0; i < graph.size(); i++) {
            if (ids[i] == -1) {
                dfs(i);
            }
        }
        return sccs;
    }

    private void dfs(int at) {
        stack.push(at);
        onStack[at] = true;
        ids[at] = low[at] = time++;

        for (int to : graph.get(at)) {
            if (ids[to] == -1) {
                dfs(to);
                low[at] = Math.min(low[at], low[to]);
            } else if (onStack[to]) {
                low[at] = Math.min(low[at], ids[to]);
            }
        }

        if (ids[at] == low[at]) {
            List<Integer> scc = new ArrayList<>();
            while (true) {
                int node = stack.pop();
                onStack[node] = false;
                scc.add(node);
                if (node == at) break;
            }
            sccs.add(scc);
        }
    }

    public static void main(String[] args) {
        TarjanSCC graph = new TarjanSCC(5);
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(1, 3);
        graph.addEdge(3, 4);

        List<List<Integer>> sccs = graph.findSCCs();
        System.out.println("SCCs: " + sccs);
    }
}

Tarjan 알고리즘 구현 (C)

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>

#define MAX 100

typedef struct {
    int top;
    int data[MAX];
    bool onStack[MAX];
} Stack;

void push(Stack *stack, int v) {
    stack->data[++stack->top] = v;
    stack->onStack[v] = true;
}

int pop(Stack *stack) {
    int v = stack->data[stack->top--];
    stack->onStack[v] = false;
    return v;
}

typedef struct {
    int *edges[MAX];
    int size[MAX];
} Graph;

Graph* createGraph(int n) {
    Graph *g = (Graph*)malloc(sizeof(Graph));
    for (int i = 0; i < n; i++) {
        g->edges[i] = (int*)malloc(sizeof(int) * n);
        g->size[i] = 0;
    }
    return g;
}

void addEdge(Graph *g, int u, int v) {
    g->edges[u][g->size[u]++] = v;
}

void dfs(Graph *g, int v, int *ids, int *low, Stack *stack, int *time, int n) {
    static int sccCount = 0;
    push(stack, v);
    ids[v] = low[v] = (*time)++;

    for (int i = 0; i < g->size[v]; i++) {
        int to = g->edges[v][i];
        if (ids[to] == -1) {
            dfs(g, to, ids, low, stack, time, n);
            low[v] = (low[v] < low[to]) ? low[v] : low[to];
        } else if (stack->onStack[to]) {
            low[v] = (low[v] < ids[to]) ? low[v] : ids[to];
        }
    }

    if (ids[v] == low[v]) {
        printf("SCC %d: ", ++sccCount);
        while (1) {
            int node = pop(stack);
            printf("%d ", node);
            if (node == v) break;
        }
        printf("\n");
    }
}

void findSCCs(Graph *g, int n) {
    int ids[MAX], low[MAX], time = 0;
    Stack stack = { .top = -1 };

    for (int i = 0; i < n; i++) {
        ids[i] = -1;
        stack.onStack[i] = false;
    }

    for (int i = 0; i < n; i++) {
        if (ids[i] == -1) {
            dfs(g, i, ids, low, &stack, &time, n);
        }
    }
}

int main() {
    int n = 5;
    Graph *g = createGraph(n);
    addEdge(g, 0, 1);
    addEdge(g, 1, 2);
    addEdge(g, 2, 0);
    addEdge(g, 1, 3);
    addEdge(g, 3, 4);

    printf("Strongly Connected Components:\n");
    findSCCs(g, n);

    return 0;
}

결론

이번 글에서는 Kosaraju 알고리즘을 사용하여 유향 그래프에서 강한 연결 요소를 찾는 방법에 대해 알아보았습니다. 강한 연결 요소는 그래프의 여러 문제를 해결하는 데 중요한 정보를 제공하며, 특히 사이클 검출 및 경로 분석에서 유용합니다. Kosaraju 알고리즘은 두 번의 DFS를 통해 강한 연결 요소를 효율적으로 찾아낼 수 있는 방법입니다.

강한 연결 요소에 대한 이해를 바탕으로 더 깊이 있는 그래프 탐색을 할 수 있기를 바랍니다.