强连通分量¶

概述¶

强连通分量（Strongly Connected Component, SCC）是有向图中的极大强连通子图。在强连通分量内，任意两个顶点之间都存在双向路径。

定义¶

有向图G中，若顶点u和v互相可达（u→v且v→u），则称u和v强连通。强连通分量是极大的强连通顶点集合。

强连通分量特点

分量内任意两点互相可达
不同分量间不存在双向路径
一个顶点恰好属于一个强连通分量
所有强连通分量构成图的划分

Kosaraju算法¶

算法步骤¶

对原图G进行DFS，记录顶点完成时间
构造反图G^T（所有边反向）
按完成时间降序对反图进行DFS
每次DFS访问的顶点构成一个强连通分量

实现¶

C
#define MAX_V 1000

typedef struct {
    int adj[MAX_V][MAX_V];
    int vertexCount;
    int visited[MAX_V];
    int finished[MAX_V];
    int finishTime;
    int sccId[MAX_V];
    int sccCount;
} Graph;

void initGraph(Graph *g, int n) {
    g->vertexCount = n;
    g->finishTime = 0;
    g->sccCount = 0;
    
    for (int i = 0; i < n; i++) {
        g->visited[i] = 0;
        g->sccId[i] = -1;
        for (int j = 0; j < n; j++) {
            g->adj[i][j] = 0;
        }
    }
}

void dfs1(Graph *g, int u) {
    g->visited[u] = 1;
    
    for (int v = 0; v < g->vertexCount; v++) {
        if (g->adj[u][v] && !g->visited[v]) {
            dfs1(g, v);
        }
    }
    
    g->finished[g->finishTime++] = u;
}

void dfs2(Graph *g, int u, int sccId) {
    g->sccId[u] = sccId;
    
    for (int v = 0; v < g->vertexCount; v++) {
        if (g->adj[v][u] && g->sccId[v] == -1) {
            dfs2(g, v, sccId);
        }
    }
}

void kosaraju(Graph *g) {
    for (int i = 0; i < g->vertexCount; i++) {
        g->visited[i] = 0;
    }
    
    for (int i = 0; i < g->vertexCount; i++) {
        if (!g->visited[i]) {
            dfs1(g, i);
        }
    }
    
    for (int i = 0; i < g->vertexCount; i++) {
        g->sccId[i] = -1;
    }
    
    int sccCount = 0;
    for (int i = g->finishTime - 1; i >= 0; i--) {
        int u = g->finished[i];
        if (g->sccId[u] == -1) {
            dfs2(g, u, sccCount++);
        }
    }
    
    g->sccCount = sccCount;
}

Tarjan算法¶

算法思想¶

使用DFS维护两个值： - dfn[u]：顶点u的DFS序号 - low[u]：u或其子树能回溯到的最小dfn

当dfn[u] == low[u]时，u是强连通分量的根。

实现¶

C
#define MAX_V 1000

typedef struct {
    int adj[MAX_V][MAX_V];
    int vertexCount;
    int dfn[MAX_V];
    int low[MAX_V];
    int visited[MAX_V];
    int inStack[MAX_V];
    int stack[MAX_V];
    int stackTop;
    int dfnCount;
    int sccId[MAX_V];
    int sccCount;
} TarjanGraph;

void initTarjan(TarjanGraph *g, int n) {
    g->vertexCount = n;
    g->stackTop = 0;
    g->dfnCount = 0;
    g->sccCount = 0;
    
    for (int i = 0; i < n; i++) {
        g->dfn[i] = -1;
        g->low[i] = 0;
        g->visited[i] = 0;
        g->inStack[i] = 0;
        g->sccId[i] = -1;
        for (int j = 0; j < n; j++) {
            g->adj[i][j] = 0;
        }
    }
}

int min(int a, int b) {
    return a < b ? a : b;
}

void tarjanDFS(TarjanGraph *g, int u) {
    g->dfn[u] = g->low[u] = g->dfnCount++;
    g->stack[g->stackTop++] = u;
    g->inStack[u] = 1;
    
    for (int v = 0; v < g->vertexCount; v++) {
        if (g->adj[u][v]) {
            if (g->dfn[v] == -1) {
                tarjanDFS(g, v);
                g->low[u] = min(g->low[u], g->low[v]);
            } else if (g->inStack[v]) {
                g->low[u] = min(g->low[u], g->dfn[v]);
            }
        }
    }
    
    if (g->dfn[u] == g->low[u]) {
        int v;
        do {
            v = g->stack[--g->stackTop];
            g->inStack[v] = 0;
            g->sccId[v] = g->sccCount;
        } while (v != u);
        g->sccCount++;
    }
}

void tarjan(TarjanGraph *g) {
    for (int i = 0; i < g->vertexCount; i++) {
        if (g->dfn[i] == -1) {
            tarjanDFS(g, i);
        }
    }
}

Gabow算法¶

Gabow算法是Tarjan算法的简化版本，使用两个栈代替dfn和low数组。

实现¶

C
typedef struct {
    int adj[MAX_V][MAX_V];
    int vertexCount;
    int visited[MAX_V];
    int stack1[MAX_V], top1;
    int stack2[MAX_V], top2;
    int sccId[MAX_V];
    int sccCount;
    int dfnCount;
} GabowGraph;

void initGabow(GabowGraph *g, int n) {
    g->vertexCount = n;
    g->top1 = g->top2 = 0;
    g->sccCount = 0;
    g->dfnCount = 0;
    
    for (int i = 0; i < n; i++) {
        g->visited[i] = 0;
        g->sccId[i] = -1;
        for (int j = 0; j < n; j++) {
            g->adj[i][j] = 0;
        }
    }
}

void gabowDFS(GabowGraph *g, int u) {
    g->visited[u] = g->dfnCount++;
    g->stack1[g->top1++] = u;
    g->stack2[g->top2++] = u;
    
    for (int v = 0; v < g->vertexCount; v++) {
        if (g->adj[u][v]) {
            if (g->visited[v] == -1) {
                gabowDFS(g, v);
            } else if (g->sccId[v] == -1) {
                while (g->visited[g->stack2[g->top2 - 1]] > g->visited[v]) {
                    g->top2--;
                }
            }
        }
    }
    
    if (u == g->stack2[g->top2 - 1]) {
        g->top2--;
        int v;
        do {
            v = g->stack1[--g->top1];
            g->sccId[v] = g->sccCount;
        } while (v != u);
        g->sccCount++;
    }
}

void gabow(GabowGraph *g) {
    for (int i = 0; i < g->vertexCount; i++) {
        g->visited[i] = -1;
    }
    
    for (int i = 0; i < g->vertexCount; i++) {
        if (g->visited[i] == -1) {
            gabowDFS(g, i);
        }
    }
}

C++ 实现（Tarjan）¶

C++
class SCC {
private:
    vector<vector<int>> adj;
    int n;
    vector<int> dfn, low, sccId;
    vector<bool> inStack;
    stack<int> stk;
    int dfnCount, sccCount;
    
    void tarjan(int u) {
        dfn[u] = low[u] = dfnCount++;
        stk.push(u);
        inStack[u] = true;
        
        for (int v : adj[u]) {
            if (dfn[v] == -1) {
                tarjan(v);
                low[u] = min(low[u], low[v]);
            } else if (inStack[v]) {
                low[u] = min(low[u], dfn[v]);
            }
        }
        
        if (dfn[u] == low[u]) {
            int v;
            do {
                v = stk.top();
                stk.pop();
                inStack[v] = false;
                sccId[v] = sccCount;
            } while (v != u);
            sccCount++;
        }
    }
    
public:
    SCC(int n) : n(n), adj(n), dfn(n, -1), low(n), sccId(n), inStack(n, false), 
                dfnCount(0), sccCount(0) {}
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }
    
    vector<vector<int>> findSCC() {
        for (int i = 0; i < n; i++) {
            if (dfn[i] == -1) {
                tarjan(i);
            }
        }
        
        vector<vector<int>> components(sccCount);
        for (int i = 0; i < n; i++) {
            components[sccId[i]].push_back(i);
        }
        
        return components;
    }
    
    int getSCCCount() const { return sccCount; }
    int getSCCId(int v) const { return sccId[v]; }
};

缩点（DAG构造）¶

将每个强连通分量缩为一个点，得到有向无环图（DAG）：

C
void buildDAG(Graph *g, int sccCount, int dag[MAX_V][MAX_V]) {
    for (int i = 0; i < sccCount; i++) {
        for (int j = 0; j < sccCount; j++) {
            dag[i][j] = 0;
        }
    }
    
    for (int u = 0; u < g->vertexCount; u++) {
        for (int v = 0; v < g->vertexCount; v++) {
            if (g->adj[u][v] && g->sccId[u] != g->sccId[v]) {
                dag[g->sccId[u]][g->sccId[v]] = 1;
            }
        }
    }
}

时间复杂度分析¶

算法	时间复杂度	空间复杂度	特点
Kosaraju	O(V + E)	O(V + E)	需要两次DFS，构造反图
Tarjan	O(V + E)	O(V)	单次DFS，一次遍历
Gabow	O(V + E)	O(V)	使用两个栈，实现简洁

空间复杂度¶

Kosaraju：O(V + E)（需要存储反图）
Tarjan：O(V)（栈和数组）
Gabow：O(V)（两个栈）

应用场景¶

2-SAT问题：判断布尔公式是否有解
程序分析：检测循环依赖
社交网络：发现紧密联系的群体
网页排名：分析网站链接结构
编译器：分析函数调用关系

2-SAT问题¶

C
int twoSAT(int n, int clauses[][2], int clauseCount) {
    SCC scc(2 * n);
    
    for (int i = 0; i < clauseCount; i++) {
        int x = clauses[i][0];
        int y = clauses[i][1];
        
        int nx = (x > 0) ? (x - 1 + n) : (-x - 1);
        int ny = (y > 0) ? (y - 1 + n) : (-y - 1);
        int px = (x > 0) ? (x - 1) : (-x - 1 + n);
        int py = (y > 0) ? (y - 1) : (-y - 1 + n);
        
        scc.addEdge(nx, py);
        scc.addEdge(ny, px);
    }
    
    scc.findSCC();
    
    for (int i = 0; i < n; i++) {
        if (scc.getSCCId(i) == scc.getSCCId(i + n)) {
            return 0;
        }
    }
    
    return 1;
}

算法比较¶

特性	Kosaraju	Tarjan	Gabow
实现难度	中等	较难	中等
需要反图	是	否	否
递归深度	O(V)	O(V)	O(V)
实际效率	较快	最快	较快
代码量	中等	较多	较少

参考资料¶

《算法导论》第22章
Tarjan's SCC Algorithm
强连通分量详解