无向图的双连通分量

  1 package org.xiu68.exp.exp9;
  2 
  3 import java.util.Stack;
  4 
  5 public class Exp9_3 {
  6     //无向图的双连通分量问题
  7     public static void main(String[] args) {
  8         // TODO Auto-generated method stub
  9         int[][] graph=new int[][]{
 10             {0,1,1,0,0},
 11             {1,0,1,0,0},
 12             {1,1,0,1,1},
 13             {0,0,1,0,1},
 14             {0,0,1,1,0}
 15         };
 16         MGraph1 m=new MGraph1(graph);
 17         m.bicompDFS(0);
 18     }
 19 
 20 }
 21 
 22 
 23 //邻接矩阵表示无向图
 24 class MGraph1{
 25     private int vexNum;                //顶点数量
 26     private int[][] edges;            //边
 27     private Stack<Edge> edgeStack;    //边栈
 28     private int[] color;            //记录顶点的访问状态，-1为未访问到,0为正在搜索中,1为已搜索完成
 29     private int[] pre;                //记录顶点的访问时间
 30     private int[] post;                //记录顶点的结束访问时刻
 31     private int    clock;                //访问时刻
 32     
 33     public MGraph1(int[][] edges) {
 34         this.edges = edges;
 35         this.vexNum=edges.length;
 36         this.color=new int[vexNum];
 37         this.pre=new int[vexNum];
 38         this.post=new int[vexNum];
 39         this.clock=1;
 40         this.edgeStack=new Stack<>();
 41         
 42         //初始化所有结点为未访问状态
 43         for(int i=0;i<vexNum;i++){
 44             color[i]=-1;
 45         }
 46     }
 47     
 48 
 49     public int bicompDFS(int v){
 50         //color[v]的值：-1为未访问到,0为正在搜索中,1为已搜索完成
 51         color[v]=0;                        //顶点v正在搜索中
 52         pre[v]=clock;                    //顶点v的访问时刻
 53         clock++;
 54         
 55         int back=pre[v];    //表示从v出发，经过一条其后代组成的边包括回退边,所能访问到的顶点的最小的开始搜索时间
 56         
 57         for(int i=0;i<vexNum;i++){
 58             if(edges[v][i]==1 && color[i]!=1){
 59                 
 60                 edgeStack.push(new Edge(v,i));    //放入边栈中
 61                 
 62                 if(color[i]==-1){                 //树边
 63                     int wBack=bicompDFS(i);
 64                     
 65                     if(wBack>=pre[v]){          //说明v的子树没有回路关联到v的祖先
 66                         System.out.println("双连通部件: ");
 67                         Edge e=edgeStack.pop();
 68                         while(true){
 69                             System.out.println("("+e.getHead()+","+e.getTail()+") ");
 70                             if(e.getHead()==v && e.getTail()==i)
 71                                 break;
 72                             e=edgeStack.pop();
 73                         }
 74                     }
 75                     if(wBack<back)
 76                         back=wBack;
 77                 }else if(color[i]==0){            //回边
 78                     if(pre[i]<back)
 79                         back=pre[i];
 80                 }
 81             }//if
 82         }//for
 83         
 84         post[v]=clock;
 85         clock++;
 86         color[v]=1;
 87         return back;
 88     }
 89 }
 90 
 91 class Edge{
 92     private int head;    //边的头
 93     private int tail;    //边的尾
 94     
 95     public Edge(int head,int tail){
 96         this.head=head;
 97         this.tail=tail;
 98     }
 99 
100     public int getHead() {
101         return head;
102     }
103 
104     public void setHead(int head) {
105         this.head = head;
106     }
107 
108     public int getTail() {
109         return tail;
110     }
111 
112     public void setTail(int tail) {
113         this.tail = tail;
114     }
115     
116 }
View Code