graphcc.java

来自「有向图的强连通分量算法的java语言实现」· Java 代码 · 共 186 行

package algorithm;

// A iterator interface for a vertex's relation

interface AdjList{
    int beg();              //the begin method of iterator
    int nxt();              //the next method of iterator
    boolean end();          // the end method of iterrator
}
// the blueprint class of graph object
class Graph{

    private int Vcnt;
    private int Ecnt;
    private boolean digraph;//digraph sign the graph is directed or not 
    
    //the node structure of the linkedlist
    
    private class Node{
        int v;
        Node next;
        Node(int x,Node t){
            v=x;
            next=t;
        }
    }
    private Node adj[];
       
    Graph(int V,boolean flag){
        Vcnt=V;
        Ecnt=0;
        digraph=flag;
        adj=new Node[V];
    }

    // return the vertex numbers of a graph

    int V(){
        return Vcnt;
    }
    
    // return the edge numbers of a graph
    int E(){
        return Ecnt;
    }

    boolean directed(){
        return digraph;
    }
    
    // insert an edge into the graph

    void insert(Edge e){
        int v=e.v;
        int w=e.w;
        adj[v]=new Node(w,adj[v]);
        if(!digraph){
            adj[w]=new Node(v,adj[w]);
        }
        Ecnt++;
    } 

    // return a iterator of a vertex

    AdjList getAdjList(int v){
        return new AdjLinkedList(v);
    }
    
   //print the graph in the manner of int patters

    static void show(Graph G){
        for(int s=0;s<G.V();s++){
            System.out.print(s+": ");
            AdjList A=G.getAdjList(s);
            for(int t=A.beg();!A.end();t=A.nxt()){
                System.out.print(t+" ");
            }
            System.out.println();
        }
    }
    
    // the implements of iterator interface
   
    private class AdjLinkedList implements AdjList{         
        private int v;
        private Node t;
        
        AdjLinkedList(int v){
            this.v=v;
            t=null;
        }
        
        public int beg(){
            t=adj[v];
            return t==null?-1:t.v;
        }
   
        public int nxt(){
            if(t!=null){
                t=t.next;
            }
            return t==null?-1:t.v;        }

        public boolean end(){
           return t==null;
        }
    }
    
}

// the bleprint of edge in the graph

class Edge{
        int v;
        int w;
        Edge(int v,int w){
            this.v=v;
            this.w=w;
        }
}

// the bluprint of strongly directed graph

public class GraphCC{
    private Graph G;
    private int ccnt;
    private int [] id;
    private void ccR(int w){
        id[w]=ccnt;
        AdjList A=G.getAdjList(w);
        for(int v=A.beg();!A.end();v=A.nxt()){
            if(id[v]==-1){
                ccR(v);                
            }
        }
    }
    GraphCC(Graph g){
        this.G=g;
        ccnt=0;
        id=new int[G.V()];
        for(int v=0;v<G.V();v++){
            id[v]=-1;
        }
        for(int v=0;v<G.V();v++){
            if(id[v]==-1){                 
                ccR(v);
                ccnt++;
            }
        }
    }
    
    // return the count of strongly component

    int count(){
        return ccnt;
    }

   // show each strongly component

    void showComponent(){
        for(int j=0;j<13;j++){
            System.out.println(id[j]);
        }
        for(int i=0; i <count(); i++){
            for(int v=0;v<G.V();v++){                
                if(id[v]==i){
                    System.out.print(v +" ");
                }
            }
            System.out.println(" in the "+i+" component");            
        }
    }
       
    public static void main(String[]arg){
        int a[]={4,2,3,0,0,2,11,12,9,9,8,10,4,4,3,7,8,5,0,6,6,7};
        int b[]={2,3,2,6,1,0,12,9,10,11,9,12,11,3,5,8,7,4,5,4,9,6};
        Graph graph1=new Graph(13,true);
        for(int i=0;i<22;i++){
            graph1.insert(new Edge(a[i],b[i]));
        }        
        GraphCC graphcc=new GraphCC(graph1);            
        graphcc.showComponent();
        graph1.show(graph1);
    }
}