Tarjan算法

ゝ一世哀愁。 2023-06-01 06:11 7阅读 0赞

*  Tarjan算法
    
     *  预备知识
     *  算法思路
     *  代码

# Tarjan算法 #

## 预备知识 ##

**有向图**：由有向边的构成的图。需要注意的是这是Tarjan算法的前提和条件。

**强连通**：如果两个顶点可以相互通达，则称两个顶点 强连通(strongly connected)。如果有向图G的每两个顶点都 强连通，称G是一个强连通图。非 强连通图有向图的极大强连通子图，称为强连通分量(strongly connected components)。  
![1430224-20180711103209561-1762811023.jpg][]  
在这个有向图中1、2、3、4四个点可以互相到达，就称这四个点组成的子图为强连通分量。且这四个点两两强连通。

然后就可以开始学习神奇的Tarjan算法了！

Tarjan算法是用来求强连通分量的，它是一种基于DFS（深度优先搜索）的算法，每个强连通分量为搜索树中的一棵子树。并且运用了数据结构栈。

在介绍详细原理前，先引入两个非常重要的数组：dfn\[ \] 与 low\[ \]

**dfn\[ \]**：就是一个时间戳（被搜到的次序），一旦某个点被DFS到后，这个时间戳就不再改变（且每个点只有唯一的时间戳）。所以常根据dfn的值来判断是否需要进行进一步的深搜。

**low\[ \]**：该子树中，且仍在栈中的最小时间戳，像是确立了一个关系，low\[ \]相等的点在同一强连通分量中。

注意初始化时 dfn\[ \] = low\[ \] = ++cnt.

## 算法思路 ##

首先这个图不一定是一个连通图，所以跑Tarjan时要枚举每个点，若dfn\[ \] == 0，进行深搜。

然后对于搜到的点寻找与其有边相连的点，判断这些点是否已经被搜索过，若没有，则进行搜索。若该点已经入栈，说明形成了环，则更新low.

在不断深搜的过程中如果没有路可走了（出边遍历完了），那么就进行回溯，回溯时不断比较low\[ \]，去最小的low值。如果dfn\[x\]==low\[x\]则x可以看作是某一强连通分量子树的根，也说明找到了一个强连通分量，然后对栈进行弹出操作，直到x被弹出。

## 代码 ##

#include <cstdio> #include <algorithm> #include <string.h> #include <vector> #include <iostream> #include <stack> #define N 75005 using namespace std; vector<int> eg[N];//邻接表存边 stack<int> sk;//栈 int idx = 0; int dfn[N], low[N], ins[N], cnt = 0; void tarjan(int u) { dfn[u] = low[u] = ++idx; sk.push(u); ins[u] = 1; for (int v : eg[u]) { if (!dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]);//回溯时更新low[ ]，取最小值 } else if (ins[v]) { low[u] = min(low[u], dfn[v]);//一旦遇到已入栈的点，就将该点作为连通量的根 　　　　　　　　　　　　　　　　　　　　　　　　//这里用dfn[e[i].v]更新的原因是：这个点可能 　　　　　　　　　　　　　　　　　　　　　　　　//已经在另一个强连通分量中了但暂时尚未出栈，所 　　　　　　　　　　　　　　　　　　　　　　　　//以now不一定能到达low[e[i].v]但一定能到达 　　　　　　　　　　　　　　　　　　　　　　　　//dfn[e[i].v]. } } int tem; if (dfn[u] == low[u]) { cnt++;//联通分量个数加 1 do { tem = sk.top(); sk.pop(); ins[tem] = 0; } while (tem != u);//出栈 } } int main() { int n, m, x, y; while (scanf("%d%d", &n, &m) && n) { idx = 0; cnt = 0; memset(ins, 0, sizeof(ins)); memset(low, 0, sizeof(low)); memset(dfn, 0, sizeof(dfn)); for (int i = 0; i < m; i++) { cin >> x >> y; eg[x].push_back(y); } for(int i=1;i<= n;i++)//防止有根本就不连通的点 if(!dfn[i]) tarjan(i); cout << cnt << endl; for (int i = 1; i <= n; i++) { eg[i].clear(); } } }

转载于:https://www.cnblogs.com/tttfu/p/11274010.html

[1430224-20180711103209561-1762811023.jpg]: /images/20230601/d3c1812ab6c740d6b5208380ada5defc.png