C语言强连通分量详解（Tarjan算法从入门到实战）

Tarjan 算法简介

Tarjan 算法 是由 Robert Tarjan 提出的一种基于深度优先搜索（DFS）的高效算法，用于找出有向图中的所有强连通分量。它的时间复杂度为 O(V + E)，其中 V 是顶点数，E 是边数。

该算法的核心思想是：在 DFS 过程中，为每个节点维护两个值：

• dfn[u]：节点 u 被访问的时间戳（DFS 序号）
• low[u]：u 或 u 的子树能追溯到的最早栈中节点的时间戳

当 dfn[u] == low[u] 时，说明 u 是一个强连通分量的根节点，此时可以从栈中弹出该分量的所有节点。

C语言实现步骤

下面我们用 C语言 实现 Tarjan 算法。我们将使用邻接表存储图，并借助栈来辅助处理。

1. 数据结构定义

// 邻接表节点struct Edge {    int to;    struct Edge* next;};// 图结构struct Graph {    int n; // 顶点数量    struct Edge** head; // 邻接表头指针数组};// 全局变量int* dfn;      // 时间戳int* low;      // 最早可达时间戳int* inStack;  // 是否在栈中int* stack;    // 模拟栈int top;       // 栈顶指针int timestamp; // 全局时间戳  

2. 添加边

void addEdge(struct Graph* g, int from, int to) {    struct Edge* e = (struct Edge*)malloc(sizeof(struct Edge));    e->to = to;    e->next = g->head[from];    g->head[from] = e;}  

3. Tarjan 核心函数

void tarjan(int u, struct Graph* g) {    dfn[u] = low[u] = ++timestamp;    stack[++top] = u;    inStack[u] = 1;    // 遍历所有邻接点    for (struct Edge* e = g->head[u]; e != NULL; e = e->next) {        int v = e->to;        if (!dfn[v]) {            tarjan(v, g);            low[u] = (low[u] < low[v]) ? low[u] : low[v];        } else if (inStack[v]) {            low[u] = (low[u] < dfn[v]) ? low[u] : dfn[v];        }    }    // 找到一个强连通分量的根    if (dfn[u] == low[u]) {        printf("SCC: ");        int node;        do {            node = stack[top--];            inStack[node] = 0;            printf("%d ", node);        } while (node != u);        printf("\n");    }}  

4. 主函数调用

int main() {    int n = 5; // 顶点数    struct Graph g;    g.n = n;    g.head = (struct Edge**)calloc(n, sizeof(struct Edge*));    // 初始化全局数组    dfn = (int*)calloc(n, sizeof(int));    low = (int*)calloc(n, sizeof(int));    inStack = (int*)calloc(n, sizeof(int));    stack = (int*)malloc(n * sizeof(int));    top = -1;    timestamp = 0;    // 构建图（示例）    addEdge(&g, 0, 1);    addEdge(&g, 1, 2);    addEdge(&g, 2, 0);    addEdge(&g, 1, 3);    addEdge(&g, 3, 4);    // 对每个未访问节点运行 Tarjan    for (int i = 0; i < n; i++) {        if (!dfn[i]) {            tarjan(i, &g);        }    }    // 释放内存（略）    return 0;}  

关键点总结

通过上述代码，你可以清晰地看到 强连通分量实现 的全过程。记住以下几点：

• 必须使用 DFS 遍历
• 栈用于临时存储当前路径上的节点
• 只有当 dfn[u] == low[u] 时才构成一个完整的 SCC
• 注意内存管理（C语言需手动释放）

应用场景

图论算法 中的强连通分量常用于：

• 编译器优化（控制流分析）
• 社交网络中的社区发现
• 任务调度依赖检测
• 判断有向图是否可简化为 DAG（有向无环图）

结语

现在你已经掌握了如何用 C 语言实现 Tarjan算法 来求解强连通分量！多练习几遍代码，尝试修改图的结构，观察输出结果的变化。坚持练习，你一定能熟练运用这一经典 图论算法！

关键词回顾：C语言强连通分量、Tarjan算法、图论算法、强连通分量实现。