连通性问题 1

(1) 两个小问题

1. 判断两点是否连通：

Ÿ 方法一——使用Floyd算法，时间复杂度O(n3)

Ÿ 方法二——从起点出发，使用DFS遍历，可以找到与它连通的其他点。时间复杂度O(n2)

Ÿ 方法三——（仅用于无向图）使用并查集。时间复杂度O(an)（a是一个小常数）。

2. 统计无向图的强连通分量个数：使用并查集，最后只需统计父亲结点个数。

(2) 强连通分量（Kosaraju算法）  [邻接矩阵]

该算法可用来计算有向图的强连通分量个数，并收缩强连通分量。

这个算法可以说是最容易理解，最通用的算法，其比较关键的部分是同时应用了原图 G 和反图 G’（）。

操作步骤如下：

① 对原图进行DFS并将出栈顺序进行逆序，得到的顺序就是拓扑顺序；

② 将原图每条边进行反向；

③ 按照①中生成顺序再进行DFS染色，染成同色的即一个强连通块。

该算法具有一个隐藏性质：如果我们把求出来的每个强连通分量收缩成一个点，并且用求出每个强连通分量的顺序来标记收缩后的结点，那么这个顺序其实就是强连通分量收缩成点后形成的有向无环图的拓扑序列。

int dfn[N], top; int color[N], cnt; void dfs1(int k) {  color[k] = 1;  for(int i=0; i<n; i++)   if(G[k]!=INF && !color)    dfs1(i);  dfn[top++] = k;     // 记录第cnt个出栈的顶点为k } void dfs2(int k) { color[k] = cnt;     // 本次DFS染色的点，都属于同一个scc，用num数组做记录  for(int i=0; i<n; i++)   if(G[k]!=INF && !color)    // 注意，我们在访问原矩阵的对称矩阵    dfs2(i); } int Kosaraju()      // 返回强连通分量个数 {  top=cnt=0;  memset(color, 0, sizeof(color)); for(int i=0; i<n; i++)    // DFS求得拓扑排序   if(!color) dfs1(i); /*    我们本需对原图的边反向，但由于我们使用邻接矩阵储存图，    所以反向的图的邻接矩阵，即原图邻接矩阵的对角线对称矩阵，    所以我们什么都不用做，只需访问对称矩阵即可 */

(3) 强连通分量（Tarjan算法）  [邻接表]

该算法的效率要高于Kosaraju算法。

任何一个强连通分量，必定是对原图的深度优先搜索树的子树（记住这句话）。那么，我们只要确定每个强连通分量的子树的根，然后根据这些根从树的最低层开始，一个一个的拿出强连通分量。

我们维护两个数组，一个是index，一个是low。其中index[i]表示顶点 i 的开始访问时间。low[i]是最小访问时间，初始化为index[i]，维护时low[i]取它与low[j]的最小值，其中 j 是与顶点 i 邻接但未删除的顶点。

在一次深搜的回溯过程中，如果发现low[i]＝index[i]，那么，当前顶点就是一个强连通分量的根（因为如果它不是强连通分量的根，那么它一定是属于另一个强连通分量，而且它的根是当前顶点的祖宗，那么存在包含当前顶点的到其祖宗的回路，可知low[i]一定被更改为一个比index[i]更小的值）。

拿出强连通分量的方法很简单。如果当前结点为一个强连通分量的根，那么它的强连通分量一定是以该根为根结点（剩下结点）的子树。在深度优先遍历的时候维护一个堆栈，每次访问一个新结点，就压入堆栈。

因为当前结点是这个强连通分量中最先被压入堆栈的，那么在当前结点以后压入堆栈的并且仍在堆栈中的结点都属于这个强连通分量。

算法实现——对于所有未访问的结点 x，都进行以下操作：

① 初始化index[x]和low[x]；

② 对于 x 所有的邻接顶点 v：

memset(color, 0, sizeof(color));  for(int i=n-1; i>=0; i--)   if(!color[dfn]){   // 按照拓扑序进行第二次DFS    cnt++;    dfs2(dfn);   } return cnt; }

如果没有访问过，则用同样方法访问 v，同时维护low[x]；如果访问过，但没有删除，就维护low[x]。

③ 如果index[x]＝low[x]，那么输出相应的强连通分量  

enum _flag { NOTVIS=0, VIS, OVER } flag[N]; // NOTVIS、VIS、OVER分别表示顶点没有被访问过、顶点被访问过但未删除、顶点已被删除的状态。 int color[N];    // color表示顶点i所属的强连通分量 int stack[N], top;  // 堆栈，辅助作用 int low[N];    // 很关键，与其邻接但未删除顶点的最小访问时间 int index[N];    // 顶点访问时间 void DFS(int x, int &sig, int &count)  // 深搜过程，该算法的主体都在这里 {  stack[++top] = x;  flag[x] = VIS;  low[x] = index[x] = ++sig;

for (edge *e=adj[x]; e!=NULL; e=e->next)

{

  int &v=e->v;

  if (flag[v]==NOTVIS)

{

DFS(v, sig, count);

if (low[v]<low[x]) low[x]=low[v];   }   else if (flag[v]==VIS && index[v]<low[x])    low[x]=index[v];    // 该部分的index应该是low，但是根据算法的属性，使用index也可以，且时间更少 } if (low[x]==index[x]) {   count++;   int t;   do   {    t=stack[top--];    color[t] = count;    flag[t] = OVER;   } while (t!=x); } }  int Tarjan() {  int sig, count;  memset(flag, 0, sizeof(flag));  sig=count=top=0;  for (int i=0; i<n; i++)   if (flag==NOTVIS)    DFS(i,sig,count);  return count; }