无向图求割点-Tarjan算法

C语言 无向图求割点-Tarjan算法

割点的定义

简单而言，在无向图中如果把某个顶点删去，此图不再连通，这样的顶点被称为割点。就例如下图：

上图的2号顶点就是割点

Tarjan算法求割点

对于每个顶点而言，都需要3个变量。
1.dfs定义是从根节点DFS遍历到该点的时间。
2.Low的定义是可以到达的、dfs树中的最小祖先。
3.used是定义是否被访问过。
4.对于起始节点还有一个变量就是snoroot记录以起始节点出发能遍历相邻节点（如果在DFS中遍历过则不计入）的个数。
思路:从起始节点出发进行DFS深度优先遍历（栈），每个结点起始的dfs,low值分别为上文定义的值，当某个节点通过非父节点的路径找到祖先（还有通过其他路径到达该点），则把自身的low值改为min（自身low值,祖先的dfs值)，直至为根节点，通过栈的回溯，（非起始节点）先将自身low=min(自身low,子节点low值),若该结点的dfs值<=子节点的low值则为割点。对于起始节点还有一个条件:snoroot>1。

图看懂就就很好理解了。

Code

#include <stdio.h>
#include <stdlib.h>
#define MAXH 100
typedef struct Graph{
       int NV;
       int NE;
       int G[MAXH+1][MAXH+1];
}Graph;
void build(Graph* T)
{
   scanf("%d%d",&T->NV,&T->NE);
   int i,j,k;
   for(i=0;i<=T->NV;i++)
   {
       for(j=0;j<=T->NV;j++)
       {
           T->G[i][j]=0;
           T->G[j][i]=0;
       }
   }
   for(i=0;i<T->NE;i++)
   {
       scanf("%d%d",&j,&k);
       T->G[j][k]=1;
       T->G[k][j]=1;
   }
};
//放割点的集合
int flag[MAXH+1];
int dfs[MAXH+1],low[MAXH+1];
int used[MAXH+1];
//sum代表割点的个数,Ds代表当前结点的遍历编号
int root,snoroot=0,sum=0,DS=0;
int findmin(int a,int b)
{
    return a>b?b:a;
};
void tarjan(Graph* T,int cur,int parent)
{
    used[cur]=1;
    dfs[cur]=++DS;
    low[cur]=DS;
    for(int i=1;i<=T->NV;i++)
    {
        if(T->G[cur][i]==0)
            continue;
        if(i==parent)
            continue;
        if(used[i]==0)
        {
            tarjan(T,i,cur);
            low[cur]=findmin(low[i],low[cur]);
            if(low[i]>=dfs[cur])
            {
                if(cur==root)
                    snoroot++;
                else
                {
                    flag[cur]=1;
                    sum++;
                }
            }
        }
        else
            low[cur]=findmin(dfs[i],low[cur]);
    }
};
int main()
{
    Graph* S=(Graph*)malloc(sizeof(Graph));
    build(S);
    root=2;
    tarjan(S,2,0);
    if(snoroot>1)
    {
        sum++;
        flag[root]=1;
    }
    printf("%d\n",sum);
    for(int i=1;i<=S->NV;i++)
    {
        if(flag[i]==1)
            printf("%d ",i);
    }
    return 0;
}