graphsc.java

有向图的强连通分支查找

package graphsc;

// 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){
        System.out.println("The LingkedList of the graph");
        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 GraphSc{     
    private int scnt;
    private int cnt;
    private int [] id;
    private int[] postI;
    private int[] postR;
    private void dfsR(Graph G,int w){
        id[w]=scnt;
        AdjList A=G.getAdjList(w);
        for(int v=A.beg();!A.end();v=A.nxt()){
            if(id[v]==-1){
                dfsR(G,v);                
            }
        }
        postI[cnt++]=w;
    }
    GraphSc(Graph g){
        Graph R=reverse(g);
        id=new int[g.V()];
        postI=new int[g.V()];
        cnt=0;
        scnt=0;
        for(int v=0;v<R.V();v++){
            id[v]=-1;
        }
        for(int v=0;v<R.V();v++){
            if(id[v]==-1){                 
                dfsR(R,v);                
            }
        }
        postR=new int[g.V()];
        for(int t=0;t<R.V();t++){
            postR[t]=postI[t];            
        }
        cnt=0;
        scnt=0;
        for(int t=0;t<R.V();t++){
            id[t]=-1;
        }
        for(int v=g.V()-1;v>=0;v--){
            if(id[postR[v]]==-1){
                dfsR(g,postR[v]);
                scnt++;
            }
        }
    }
    Graph reverse(Graph g){
        Graph R=new Graph(g.V(),true);
        for(int w=0;w<g.V();w++){ 
            AdjList A=g.getAdjList(w);
            for(int v=A.beg();!A.end();v=A.nxt()){
                R.insert(new Edge(v,w));
            }
            
        }
        return R;
        
    }
        
    
    
    // return the count of strongly component

    int count(){
        return scnt;
    }

   // show each strongly component

    void showComponent(){         
        System.out.println("The numbers of strong component:"+count());        
        for(int i=0; i <count(); i++){
            for(int v=0;v<id.length;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]));
        }        
        GraphSc graphSc=new GraphSc(graph1);            
        graphSc.showComponent();
        graph1.show(graph1);
    }
}