使用Tarjan算法求解图的割点和桥。
1、割点
主要的算法结构就是DFS，一个点是割点，当且仅当以下两种情况:
(1)该节点是根节点，且有两棵以上的子树;
(2)该节点的任一子节点，没有到该节点祖先的反向边（就是说如果没有这个割点，那么这个子节点和那个祖先之间不连通）;
void cutpoint_Tarjan(int u,int parent)
{
int son; //节点m的儿子节点
ENode *ptr=(ENode *)malloc(sizeof(ENode)); dfn[u]=low[u]=depth++; //访问+标记+遍历
vis[u]=;
ptr=ALG->vlist[u].firstedge;
while(ptr!=NULL)
{
son=ptr->key;
if(!vis[son])
{
DFS(son,u);
low[u]=MIN(low[u],low[son]); if(u==root) //不同之处//根节点[要定义初始访问节点，因为要考虑割点的2个判断条件]
cut[u]++;
else if(u!=root && dfn[u] <= low[son])
cut[u]++; //m是割点
}
else if(son != parent) //有后向边
{
low[u]=MIN(low[u],dfn[son]);
}
ptr=ptr->next;
}
}
2、桥
Tarjan算法求割边(桥)：
【1】使用(son!=parent && dfn[son]<dfn[u]);
void init_Tarjan(void)
{
depth=;
for(int i=;i<ALG->n;i++)
{
dfn[i]=low[i]=-;
vis[i]=;
} num_bridge=;
for(int j=;j<ALG->e;j++)
{
bridge_Node[j].front=;
bridge_Node[j].rear =;
}
} void Add_to_BNode(int front,int rear) //从坐标1开始存储
{
bridge_Node[num_bridge].front=front;
bridge_Node[num_bridge].rear =rear;
} void bridgenode_Tarjan(int u,int parent)
{
int son;
ENode *ptr=(ENode*)malloc(sizeof(ENode)); dfn[u]=low[u]=depth++; //访问+标记+遍历
vis[u]=;
ptr=ALG->vlist[u].firstedge;
while(ptr!=NULL)
{
son=ptr->key;
if(son!=parent && dfn[son]<dfn[u]) //避免走重边，效果和id一样
{
if(!vis[son])
{
bridge_node_Tarjan(son,u);
low[u]=MIN(low[u],low[son]);
if(low[son] > dfn[u]) //(u,son)是桥
{
num_bridge++;
Add_to_BNode(u,son); //存储桥
}
}
else if(son != parent)
{
low[u]=MIN(low[u],dfn[son]);
}
}
ptr=ptr->next;
}
}
【2】为每一条边标号 id记录每条边（一条无向边拆成的两条有向边id相同）,每个点的父亲到它的边的标号;
//结点定义 /*****注意边表节点定义有所变化****/
typedef struct edge_node{
int key; //儿子节点[边的终点]
int id; //边的编号
struct edge_node *next;
}ENode;
void init_Tarjan(void) //Tarjan算法初始化
{
depth=;
for(int i=;i<ALG->n;i++)
{
vis[i]=;
dfn[i]=low[i]=-;
}
count_bridge=;
for(int j=;j<=ALG->e;j++) //取值于1-e
bridge[j]=;
}
void bridge_Tarjan(int u,int id) //id是u的父亲边的编号
{
int son; //u的儿子节点
ENode *ptr=(ENode *)malloc(sizeof(ENode)); dfn[u]=low[u]=depth++; //访问+标记+遍历
vis[u]=;
ptr=ALG->vlist[u].firstedge;
while(ptr!=NULL)
{
if(ptr->id != id) //避免走重边，相当于cutpoint_Tarjan中的(son != parent)
{
son=ptr->key;
if(!vis[son])
{
bridge_Tarjan(son,ptr->id);
low[u]=MIN(low[u],low[son]);
if(dfn[u] < low[son]) //注意不取等号,当DFN[u]==LOW[v]时，当u->v dfs递归，存在一条v->u的回边，使得LOW[v]=DFN[u];故不为桥
{
bridge[ptr->id]=; //第id边是桥
printf("(%c,%c) ",ALG->vlist[u].vertex,ALG->vlist[son].vertex); //用于输出割边
}
}
else
{
low[u]=MIN(low[u],dfn[son]);
}
}
ptr=ptr->next;
}
}