【问题描述】
给定一个无向图，设计一个算法，判断该图中是否存在关节点，并划分双连通分量。
package org.xiu68.exp.exp9;
import java.util.Stack;
public class Exp9_3 {
//无向图的双连通分量问题
public static void main(String[] args) {
// TODO Auto-generated method stub
int[][] graph=new int[][]{
{0,1,1,0,0},
{1,0,1,0,0},
{1,1,0,1,1},
{0,0,1,0,1},
{0,0,1,1,0}
};
MGraph1 m=new MGraph1(graph);
m.bicompDFS(0);
//运行结果
/*
双连通部件:
(4,2) (3,4) (2,3)
双连通部件:
(2,0) (1,2) (0,1)
*/
}
}
//邻接矩阵表示无向图
class MGraph1{
private int vexNum; //顶点数量
private int[][] edges; //边
private Stack<Edge> edgeStack; //边栈
private int[][] visitedEdge; //记录哪条边已经访问过,1为访问过,0为未访问过
private int[] color; //记录顶点的访问状态，-1为未访问到,0为正在搜索中,1为已搜索完成
private int clock; //访问时刻
private int[] pre; //记录顶点的访问时间
private int[] post; //记录顶点的结束访问时刻
public MGraph1(int[][] edges) {
this.edges = edges;
this.vexNum=edges.length;
this.color=new int[vexNum];
this.pre=new int[vexNum];
this.post=new int[vexNum];
this.clock=1;
this.edgeStack=new Stack<>();
this.visitedEdge=new int[vexNum][vexNum];
//初始化所有结点为未访问状态
for(int i=0;i<vexNum;i++){
color[i]=-1;
}
}
//返回从v出发，经过一条其后代组成的边包括回退边,所能访问到的顶点的最小的pre值
public int bicompDFS(int v){
//color[v]的值：-1为未访问到,0为正在搜索中,1为已搜索完成
color[v]=0; //顶点v正在搜索中
pre[v]=clock; //顶点v的访问时刻
clock++;
int back=pre[v]; //表示从v出发，经过一条其后代组成的边包括回退边,所能访问到的顶点的最小的pre值
for(int i=0;i<vexNum;i++){
if(edges[v][i]==1 && color[i]!=1 && visitedEdge[v][i]!=1){ //顶点v和i之间有边未访问过
edgeStack.push(new Edge(v,i)); //放入边栈中
visitedEdge[v][i]=visitedEdge[i][v]=1; //记录边已访问过
if(color[i]==-1){ //树边
int wBack=bicompDFS(i);
if(wBack>=pre[v]){ //说明v的子树没有回路关联到v的祖先
System.out.println("双连通部件: ");
Edge e=edgeStack.pop();
while(true){
System.out.print("("+e.getHead()+","+e.getTail()+") ");
if(e.getHead()==v && e.getTail()==i)
break;
e=edgeStack.pop();
}
System.out.println();
}
if(wBack<back)
back=wBack; //记录从v开始经过的顶点的最小的pre值
}else if(color[i]==0){ //回边
if(pre[i]<back)
back=pre[i]; //记录从v开始经过的顶点的最小的pre值
}
}//if
}//for
post[v]=clock;
clock++;
color[v]=1;
return back;
}
}
class Edge{
private int head; //边的头
private int tail; //边的尾
public Edge(int head,int tail){
this.head=head;
this.tail=tail;
}
public int getHead() {
return head;
}
public void setHead(int head) {
this.head = head;
}
public int getTail() {
return tail;
}
public void setTail(int tail) {
this.tail = tail;
}
}