图的连通1(缩点)

这几天开始学图的连通了（因为发现这是个大坑，好像很基础，但我不会）。于是就神神奇奇地开始写缩点了，但貌似调了一个晚上。所以觉得还是写一下总结总结比较不错。

先说一下什么是连通吧：

如果点A可以通过某条神奇的小道到达B，而B也可以一阵乱走走到A，那么A、B是连通的。无向肯定不用说，毕竟可以原路返回，所以两点一定连通。

连通图的定义：如果该图中任意两点都连通，则这个图是个连通图。（如果这是个有向图，还可以叫强连通图。反正有“强”的就是针对有向图的。）

（强）连通分量是什么呢？就是一个图中的尽量多的互相连通的一些点构成的一个子图呗。

如下图中橘黄色圈出来的是两个强连通分量：

![pic](http://imglf1.ph.126.net/-iWjuFaHCvj3yqhAcqeMlg==/6631389922610764924.jpg)

（单个的1算不算？可以不用纠结，没人会考你这个。）

**好了，来讲下最常用的缩点吧！**

有两种缩点的方法：

1、一种是kozaraju提出的。（别问我怎么念）

2、tarjan提出。（~~跟我念塔儿尖~~）

#kozaraju

(不知道他当初是怎么脑洞大开想到的)
图中橘黄色圈出的为强连通分量，蓝色是标号，红色是连通分量之间的边。

![pic](http://imglf1.ph.126.net/OFniRVH5rb9FZzdZ6IWGGg==/6631294265099169181.jpg)

图中橘黄色圈出的为强连通分量，蓝色是标号，红色是连通分量之间的边。

![pic](http://imglf2.ph.126.net/-l517x1xTqT1OwRM_dm_6w==/6631367932378233689.jpg)

如果我们在一个连通分量里一阵DFS乱搜，肯定能把该连通分量内的所有点搜出来，但是肯定会混杂一些其他的点。但如果我们有顺序地搜，比如从3中任意一个点开搜，肯定会刚好把3这个连通分量的所有点搜出来，记录以及标记；然后是2，1，5，4；

是不是有点拓扑顺序的感觉？

对的就是这样，所以他采用的DFS版的拓扑序。但是这个图毕竟有环，连通分量自己内部的情况太复杂——

比如这样

![](http://imglf1.ph.126.net/cAKyd5RUlbZZwsh77JDh8Q==/6631252483657314001.jpg)

如果从1开始搜，你会很愉快地先把3加入拓扑序列。

拓扑序乱了怎么办呢？没有关系，看之前在DFS版拓扑中说的——**现在正在访问的点永远会比它可以到达的点先输出**。

我们能够保证1所在连通块总有一个点会比其他连通块中的点后出现在拓扑序列中。

没看懂？接下来更详细讲解。（其实这个方法不常用，可以略过）

![](http://imglf0.ph.126.net/Y-YUUBrq-j8SKxzaPIrwvw==/6631329449471352951.jpg)

上图中ABC分别代表三个连通分量

一下以abc代表三个对应连通分量中的点

我们希望得到的顺是CBA，按照这个顺序可以放心地顺着乱搜

如果我们从BAC的顺序(随机)开始生产拓扑序（注意是反向沿着边走）

那么得到的会是babc

如果是CBA，那么会是cbabc

如果是ABC 那么会是abc

......

总之，我们得到的拓扑序的后几个的倒叙正是我们想要的。

为什么这样就可以了呢？

拿图二说吧：我们正常得到的拓扑序是14523

而看到图一中，我们从任意一个点开始深搜，一定可以访问到该点所在连通分量的所有点 和 拓扑序中在该点之后的 一些 连通分量。由于连通分量内部结构不可测，所以谁先进入即将生成的拓扑序不可确定，但是由于红色边的限制，只要我们访问到其他连通分量一定是会先把其他连通分量放入即将生成的拓扑序中，然后再将自己连通分量中的部分点放在其后。

所以沿着逆向边生成的伪拓扑序中的最后一部分是确定的，而且就是连通分量拓扑序的倒叙。

wuvin

导航

最近发表

友情链接