tarjan算法用来求解一个有向图的强连通分量

算法要求我们

  • 有$dfn$数组记录每一个节点在深度优先搜索中的访问次序
  • $visited$数组作为全局变量，记录某一个节点是否被访问过
  • $Stack$作为栈，储存在一次深度优先搜索中访问到的节点,$top$为栈顶指针，初始值为$-1$,$inStack$数组记录该节点是否在栈中
  • $low$数组记录每一个节点能回溯到的最早访问到的节点
  • $index$记录访问次序，初始值为0或者1

算法流程

对图中每一个节点进行访问，首先判断节点是否被访问过，也就是判断

1
if(visited[v])

如果该节点访问过就跳过该节点，否则就从这个节点开始深度优先搜索

1
void DFS(int vertex,Gragh G)

进入深度优先搜索函数后，我们先进行以下赋值

1
2
3
4
visited[vertex]=1;
dfn[vertex]=low[vertex]=index++;
Stack[++top]=vertex;
inStack[vertex]=1;

然后我们对该节点的所有相邻节点进行深度优先访问

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
PtrToV p;//p是一个顶点指针
for(p=G->VertexArr[vertex];p!=NULL;p=p->next){
    if(！visited[p->vert]){
        DFS(p->vert,G);
        low[vertex] = min(low[vertex],low[p->vert])
    }//判断p对应的顶点是否访问过
    else if(inStack[p->vert]){
        low[vertex]=min(low[vertex],dfn[p->vert])
    }//如果该节点在栈中，那么说明这个节点到vertex节点之间存在一条路径，并且vertex到这个节点也存在一条路径，也就是说这两个节点之间存在一条回路，我们将其中访问次序靠前的视作树根，更新vertex能回溯到的最早访问的顶点
}
if(dfn[vertex]==low[vertex]){
    while(Stack[top]！=vertex){
        v=Stack[top--];
        print(v);
    }//按照出栈顺序打印顶点
}

完整代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
void DFS(int vertex,Graph G,void(*visit)(Vertex V));
int min(int a,int b);
int dfn[2*MaxVertices],low[2*MaxVertices],visited[2*MaxVertices],Stack[2*MaxVertices],top=-1,index=0,inStack[2*MaxVertices];
int min(int a,int b){
    return (a<b)?a:b;
}
void StronglyConnectedComponents( Graph G, void (*visit)(Vertex V) ){
    for(int i=0;i<G->NumOfVertices;++i){
        if(visited[i]==0){
            DFS(i,G,visit);
        }
    }
}
void DFS(int vertex,Graph G,void(*visit)(Vertex V)){
    visited[vertex]=inStack[vertex]=1;
    dfn[vertex]=low[vertex]=index++;//记录访问次序
    Stack[++top]=vertex;
    PtrToVNode p;
    for(p = G->Array[vertex];p != NULL;p=p->Next){
        if(!visited[p->Vert]){
            DFS(p->Vert,G,visit);
            low[vertex]=min(low[vertex],low[p->Vert]);
        }
        else if(inStack[p->Vert]){
                low[vertex] = min(low[vertex],dfn[p->Vert]);
            }
    }
    if(dfn[vertex]==low[vertex]){
        while (Stack[top]!=vertex)
        {
            visit(Stack[top]);
            inStack[Stack[top]]=0;
            top--;
        }
        visit(Stack[top]);
        inStack[Stack[top]]=0;
        top--;
        printf("\n");
    }
}
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。