欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Tarjan学习笔记

程序员文章站 2022-07-28 16:58:26
从头开始学习OI之Tarjan. 今天重新学习了Tarjan算法..来这里写一下学习笔记...但是我太菜了..还是讲不好怎么办... ......

从头开始学习oi之tarjan. 今天重新学习了tarjan算法..来这里写一下学习笔记...

用处

tarjan算法,是一个关于图的联通性的神奇算法.基于dfs(深度优先搜索).是对于有向图的算法是.根据树,栈,打标记等方法来完成剖析一个图的工作.


我们先来学习一下tarjan算法需要知道的定义:
强连通,强连通图,强连通分量

强连通(strongly connected):

在一个有向图 g 里,有两个点 a,b ,由a有一条路可以走到b,由b又有一条路可以走到a,我们就叫这两个顶点 (a,b) 强连通.

强连通图(strongly connected graph):

如果在一个有向图 g 中,每两个点都强连通,我们就叫这个图 强连通图

强连通分量(strongly connected components):

在一个有向图 g 中,有一个子图,这个子图每2个点都满足强连通,我们就叫这个子图叫做 强连通分量 (如图中的 1,2,3 组成的分量就叫强连通分量)
Tarjan学习笔记


tarjan算法:

tarjan所做的事情很简单...就是找到每一个强连通分量(单独一个点也算是强连通分量..) 在实现算法之前...我们先定义几个数组:
dfn[i] 表示第 i 个节点的时间戳..也就是在dfs这张图的时候这个点被遍历到的时刻..
low[i] 表示第 i 个节点所在的强连通分量的根节点(按理说强连通分量无所谓根节点..这里的根节点是指在那一棵dfs树中这个强连通分量的根节点)

很明显如果 dfn[i] == low[i] 那么就代表这一个点是一个强连通分量的根
先看一下算法流程

void tarjan(int u) {
    dfn[u] = low[u] = ++index; //将dfn和low都初始化为时间戳,也就是dfs到的时刻
    stack[++top] = u; //将该点压入dfs栈中
    vis[u] = 1; //标记点在栈中
    for(int i = head[u]; i; i = edge[i].next) { //dfs过程
        if(!dfn[edge[i].to]) { //如果该点没有被搜索到过
            tarjan(edge[i].to); //对于该点进行算法(即dfs的过程)
            low[u] = min(low[u],low[edge[i].to]); //搜索完成返回时更新一下这个强连通分量里的所有点的在dfs树中的根节点
        } else if(vis[edge[i].to]) { //如果该点已经在搜索栈中,那么代表当前栈中在这个点后的点在一个强连通分量里,那么这个搜索到的点就是这个强连通分量的根节点..
            low[u] = min(low[u],dfn[edge[i].to]); //将当前点所在强连通分量的根节点修改为搜索到的这个节点,也就是根节点..
        }
    }
    if(dfn[u] == low[u]) { //按照上面的定义我们知道这是判断是否是一个强连通分量的根节点
        while(stack[top] != u) { //按照上面所说的将该点在栈后的所有节点都弹出(在一个强连通分量里..也就是我们要求的了..可以染色存储起来备用或者缩成一个点(缩点算法))
            printf("%d ",stack[top]);
            vis[stack[top--]] = 0;
        }
        printf("%d\n",stack[top]); //弹出当前的这个根
        vis[stack[top--]] = 0;
    }
}

首先来一张有向图 \(g\).我们一点一点来模拟整个算法.
Tarjan学习笔记




首先是一点一点的入栈..也就是上面dfs遍历的时候的顺序..叫做dfs序或者入栈序..即:


step1: 1号点入栈 dfn[1] = low[1] = ++index (1)
此时栈为: 1
step2: 2号点入栈 dfn[2] = low[2] = ++index (2)
此时栈为: 1 2
step3: 3号点入栈 dfn[3] = low[3] = ++index (3)
此时栈为: 1 2 3
step4: 6号点入栈 dfn[6] = low[6] = ++index (4)
此时栈为: 1 2 3 6
Tarjan学习笔记

左边这张树的图就是当前操作完成后的dfs树...
走到这里之后我们看到右边图中六号节点没有了出边...也就是上面说的第一步或者说是第一个判断结束了...
我们就要开始返回了,明显 low[6] == dfn[6] 所以6就是一个强连通分量的根节点;
栈要一直弹出直到弹出6号节点 此时栈为: 1 2 3
然后返回到三号..三号再无出边..
也一直弹出直到将其弹出 存为一个强连通分量的根 此时栈为: 1 2


发现2号节点还有可以继续遍历下去的边..于是将五号节点压入栈中即:
dfn[5] = dfn[5] = ++index(5) 此时栈为: 1 2 5
再遍历发现一个6号..已经遍历过就不在管他了..
再遍历发现一个1号节点..1号在栈中..于是进入第二个if语句,修改
low[5] = min(low,low) 所以 low[5] 也就是五号节点所在的强连通分量的根就是1
五号没有出边了..返回上一层..修改 low[2] = min(low,low),low[2] = 1
二号没有出边了..返回上一层..修改 low[1] = min(low,low),low[1] = 1 low[1]依然等于1
一号还有出边..遍历到四号 dfn[4] = low[4] = ++index(6) 此时栈为 1 2 5 4
四号遍历到五号..五号在栈中所以更新一下 low[4] = min(low,low),low[4] = 1;
再返回 low[1] = min(low,low) ,low[1] = 1;
然后1号也没有出边了..这时栈一直弹出直到将1号弹出 栈空

最后的dfs树是这样的
Tarjan学习笔记

按照我们找到的根节点拆成一个个的强连通分量
Tarjan学习笔记

这样就完成了

我们把以一号为开始的连通图都遍历一遍了...为了防止图有多个(不连通) 我们要在调用tarjan的时候这样写

for(int i = 1; i <= n; ++i) 
  if(!dfn[i]) tarjan(i); //如果没有时间戳,那就代表没有遍历到,从此点开始tarjan

这样就可以把所有的图都给遍历一遍了...




来一道裸代码。
输入:
一个图有向图。
输出:
它每个强连通分量。

这个图就是刚才讲的那个图。一模一样。

input:
6 8
1 3
1 2
2 4
3 4
3 5
4 6
4 1
5 6
output:
6
5
3 4 2 1


代码:

#include <cstdio>
#include <algorithm>

using namespace std;

struct node {
    int to,next;
} edge[1001];

int cnt,index,top;
int dfn[1001],low[1001];
int stack[1001],head[1001],visit[1001];

void add(int x,int y) {
    edge[++cnt].next = head[x];
    edge[cnt].to = y;
    head[x] = cnt;
}
void tarjan(int x) { //代表第几个点在处理。递归的是点。
    dfn[x] = low[x] = ++index; // 新进点的初始化。
    stack[++top] = x; //进栈 
    visit[x] = 1; //表示在栈里
    for(int i = head[x]; i; i = edge[i].next) {
        if(!dfn[edge[i].to]) { //如果没访问过
            tarjan(edge[i].to); //往下进行延伸,开始递归
            low[x] = min(low[x],low[edge[i].to]);//递归出来,比较谁是谁的儿子/父亲,就是树的对应关系,涉及到强连通分量子树最小根的事情。
        } else if(visit[edge[i].to]) { //如果访问过,并且还在栈里。
            low[x] = min(low[x],dfn[edge[i].to]);//比较谁是谁的儿子/父亲。就是链接对应关系
        }
    }
    if(low[x] == dfn[x]) { //发现是整个强连通分量子树里的最小根。
        do {
            printf("%d ",stack[top]);
            visit[stack[top]] = 0;
            top--;
        } while(x != stack[top+1]);//出栈,并且输出。
        printf("\n");
    }
    return ;
}
int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    int x,y;
    for(int i = 1; i <= m; i++) {
        scanf("%d%d",&x,&y);
        add(x,y);
    }
    for(int i = 1; i <= n; i++)
        if(!dfn[i]) tarjan(i);//当这个点没有访问过,就从此点开始。防止图没走完
    return 0;
}