graph.java

图论中关于简单无向图的深度

/**
 * <p>Title: </p>
 * <p>Description: </p>
 * <p>Copyright: Copyright (c) 2005</p>
 * <p>Company: </p>
 * @author not attributable
 * @version 1.0
 */

public class Graph {
  //图的表示，用了两种表示方法，邻接矩阵和邻接链表
     public VertexNode AdjList[];//邻接链表的表示
   //       public int[][] matrix;//邻接矩阵
     public int numVertices;//图的节点数
     public int numEdges;//图的边数
     int result_index=0;

     /** Creates a new instance of Graph */
     public Graph(int node_cnt) {//构造函数

         numVertices=node_cnt;
         numEdges=0;
    //     matrix=new int[numVertices][numVertices];
         AdjList = new VertexNode[node_cnt];


         for(int i=0;i<numVertices;i++) {

             AdjList[i] = new VertexNode();
             AdjList[i].vertex=i;

             AdjList[i].firstedge=null;

      //       for(int j=0;j<numVertices;j++){
      //           matrix[i][j]=Integer.MAX_VALUE;
      //       }


         }
     }

     public void addEdge(int u,int v,int weight){//添加边
      //   matrix[u][v]=weight;
      //   matrix[v][u]=weight;
         numEdges++;

         EdgeNode s = new EdgeNode();
         s.adjvex=v;
         s.next=AdjList[u].firstedge;
         AdjList[u].firstedge=s;

         EdgeNode t = new EdgeNode();
         t.adjvex=u;
         t.next=AdjList[v].firstedge;
         AdjList[v].firstedge=t;
     }
}
  /*   public Edge[] Kruskal(){//克鲁斯卡尔方法，张平宇同学写的
         Edge[] result=new Edge[numVertices-1];
         MinHeap H=new MinHeap(numEdges);
         UFSets F=new UFSets(numVertices);
         int u,v;
         for(u=0;u<numVertices;u++)
             for(v=u+1;v<numVertices;v++)
                 if(matrix[u][v]!=Integer.MAX_VALUE){
                     Edge temp1=new Edge();
                     temp1.tail=u;
                     temp1.head=v;
                     temp1.weight=matrix[u][v];
                     H.Insert(temp1);
                 }
         int count=1;
         while(count<numVertices){
             Edge e=H.RemoveMin();
             u=F.Find(e.tail);
             v=F.Find(e.head);
             if(u!=v){
                 F.Union(u,v);
                 result[result_index]=e;
                 result_index++;
                 count++;
             }
         }
         return result;
     }

     public Edge[] Prim(){//普里姆方法，张平宇同学写的
         Edge[] result=new Edge[numVertices-1];
         int result_index=0;
         int[] lowcost=new int[numVertices];
         int[] nearvex=new int[numVertices];
         for(int i=1;i<numVertices;i++){
             lowcost[i]=matrix[0][i];
             nearvex[i]=0;
         }
         nearvex[0]=-1;
         for(int i=1;i<numVertices;i++){
             int min=Integer.MAX_VALUE;
             int v=0;
             for(int j=0;j<numVertices;j++)
                 if(nearvex[j]!=-1&&lowcost[j]<min){
                     v=j;
                     min=lowcost[j];
                 }
             if(v!=0){
                 Edge e=new Edge();
                 e.tail=nearvex[v];
                 e.head=v;
                 e.weight=lowcost[v];
                 result[result_index]=e;
                 result_index++;
                 nearvex[v]=-1;
                 for(int j=1;j<numVertices;j++)
                     if(nearvex[j]!=-1&&matrix[v][j]<lowcost[j]) {
                         lowcost[j]=matrix[v][j];
                         nearvex[j]=v;
                     }
             }
         }
         return result;
     }


     public void printGraph(){
         for(int i=0;i<numVertices;i++){
             for(int j=0;j<numVertices;j++){
                 if(matrix[i][j]==Integer.MAX_VALUE)
                     System.out.print(">< ");
                 else
                     System.out.print(matrix[i][j]+" ");
             }
             System.out.println();
         }
     }

     public boolean haveEdge(int u,int v){
         if(matrix[u][v]!=Integer.MAX_VALUE)
             return true;
         else
             return false;
     }
 }
  */