图的强连通问题

怼烎@ 2021-11-19 15:24 235阅读 0赞

**图的强连通问题**

**——求强连通分量个数，找出每个最大强连通子图。**

三种算法，Tarjan、Kosaraju、Garbow。先说Tarjan。

**Tarjan**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<algorithm>
     2 #include<iostream>
     3 #include<cstring>
     4 #include<cstdio>
     5 #include<stack>
     6 using namespace std;
     7 const int maxv= 110;
     8 const int maxe= 5010;  //可能的最大值
     9 
    10 struct ENode
    11 {
    12     int to;
    13     int Next;
    14 };
    15 ENode edegs[maxe];
    16 int Head[maxv], tnt;
    17 void init()
    18 {
    19     memset(Head, -1, sizeof(Head));
    20     tnt= -1;
    21 }
    22 void Add_ENode (int a, int b)
    23 {
    24     ++ tnt;
    25     edegs[tnt].to= b;
    26     edegs[tnt].Next= Head[a];
    27     Head[a]= tnt;
    28 }
    29 
    30 int dfn[maxn];  //深度优先搜索中顶点被访问的时间
    31 int low[maxn];  //顶点v 和它的邻接点中low[]的最小值
    32 int temp[maxn];  //判断节点是否已被访问过(0-未访问 1-已访问未删除 2-已访问已删除)
    33 int Stack[maxn];  //手动栈
    34 int TarBfs (int v, int lay, int &scc_num)
    35 {
    36     /*v: 新加入的点; lay: 时间戳; scc_num: 记录强连通分量的数量*/
    37 
    38     /*第2步：初始化dfn[v]和low[v]*/
    39     temp[v]= 1;
    40     low[v]= lay;
    41     dfn[v]= lay;
    42     Stack[++ m]= k;
    43     for (int k= Head[v]; k!= -1; k= edegs[k].Next)
    44     {
    45         /*对于v 的所有邻接节点u：*/
    46         int u= edegs[k].to;
    47         if (temp[u]== 0)
    48         {
    49             /*第2-1步：如果没有访问过，则跳转执行第2步，同时维护low[v]*/
    50             TarBfs(u, ++ lay, scc_num);
    51         }
    52         if (temp[u]== 1)
    53         {
    54             /*第2-2步：如果访问过，但没有删除，维护low[v]*/
    55             low[v]= min(low[v], low[u]);
    56         }
    57     }
    58     if (dfn[v]== low[v])
    59     {
    60         /*如果low[v]== dfn[v]，则当前节点是一个强连通分量的根，
    61         那么输出相应的强连通分量。*/
    62         ++ scc_num;
    63         do
    64         {
    65             low[Stack[m]]= scc_num;
    66             temp[Stack[m]]= 2;  //已删除的节点temp更新为2
    67         }while (Stack[m --]!= k);
    68     }
    69     return 0;
    70 }
    71 
    72 int Tarjan(int n)
    73 {
    74     int scc_num= 0, lay= 1;
    75     m= 0;
    76     memset(temp, 0, sizeof(temp));
    77     memset(low, 0, sizeof(low));
    78     for (int i= 1; i<= n; i ++)
    79     {
    80         if (temp[i]== 0)
    81         {
    82             /*第1步：找一个没有被访问过的节点v，否则算法结束*/
    83             TarBfs(i, lay, scc_num);
    84         }
    85     }
    86     /*返回强连通分量的个数*/
    87     return scc_num;
    88 }
    89 
    90 int main()
    91 {
    92     int n;
    93     /*建图*/
    94     int ans= Tarjan(n);
    95     return 0;
    96 }

只求个数

思路：

如果对于原图进行深度优先搜索，由强连通分量定义可知，任何一个强连通分量是原图的深度优先搜索树的子树。那么，只要确定每个极大强连通子图（强连通分量子树）的根，然后根据这些根从数的最底层开始，一个一个地取出强连通分量即可。

对于确定强连通分量的根，这里维护两个数组，一个是dfn\[ \]，一个是low\[ \]，其中dfn\[v \] 表示顶点v 被访问的时间，low\[v \]为与顶点v 邻接的未删除的顶点u 的low\[u \]与low\[v \]的最小值（low\[v \]初始化为dfn\[v \] ）。如果发现一个点，low\[v \]== dfn\[v \] ，则该点就是一个强连通分量的根。

伪代码：

1.找一个没有被访问过的节点v，否则算法结束

2.初始化dfn\[v\]和low\[v\]。对于v 的所有邻接节点u：

①如果没有访问过，则跳转执行第2步，同时维护low\[v\]；

②如果访问过，但没有删除，维护low\[v\]；

如果low\[v\]== dfn\[v\]，则当前节点是一个强连通分量的根，那么输出相应的强连通分量。

转载于:https://www.cnblogs.com/Amaris-diana/p/11254066.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211119/6fc46b50329f4257a5c88a565cb3790a.png