拓扑排序

2018-05-24 本文已影响4人四喜汤圆

一、总体架构

总体架构.png

二、重点说明

1.作用

现实生活中的项目工程、生产活动，都有一个所谓的流程，流程中包含各个步骤，步骤间具有优先级。可以把这个流程抽象为一个有向图。并且有向图中不能有环（因为有环意味着设计逻辑出错）。

2.来源

是对实际问题的抽象。现实生活中的工程项目、生产过程都有一个流程，按照特定的步骤进行执行，步骤之间具有执行的优先级，把这个抽象为有向无环图（DAG图）。

3.定义

4.前提条件

在有向无环图中才可找到拓扑排序，其余的情况找不到拓扑排序。

5. 思想

选取一个入度为0的点输出
将该节点、以及由该节点出发的边从图中删除
重复上述两个步骤，直到当前DAG图为空或不存在入度为0的节点。（后一种情况说明图中必有环）

6.实现

此处用图的邻接表进行存储。需要存储每个节点的入度数。

public class 拓扑排序 {
    public static void main(String[] args) {
        new 拓扑排序().exe();
    }

    public void exe() {
        // 构建图
        Scanner scan=new Scanner(System.in);
        int N=scan.nextInt();
        // 边数
        int E=scan.nextInt();
        ArcGraph2 g=new ArcGraph2(N,E);
        for(int i=0;i<E;i++){
            int vi=scan.nextInt();
            int vj=scan.nextInt();
            g.insertAdj(vi,vj);
        }
        System.out.println("深度优先遍历********");
        travel(g);
        System.out.println("拓扑排序********");
        topSort(g);
    }
    
    // 遍历图
    public void travel(ArcGraph2 g){
        int[] visited=new int[g.n];
        for(int i=0;i<g.n;i++){
            if(visited[i]==0){
                DFS(g,i,visited);
                System.out.println("***********");
            }
        }
    }
    
    public void DFS(ArcGraph2 g,int v,int[] visited){
        // 从节点v开始访问
        visited[v]=1;
        print(g,v);
        ArcNode p=g.nodes[v].firstArc;
        while(p!=null){
            if(visited[p.num]==0){
                DFS(g,p.num,visited);
            }
            p=p.nextArc;
        }
    }

    private void print(ArcGraph2 g, int v) {
        System.out.println(g.nodes[v].toString());
    }
    
    /**
     * 输出有向无环图的拓扑排序
     * @param g
     * @return：true：拓扑排序成功；flase：不成功
     */
    public boolean topSort(ArcGraph2 g){
        // 计数器，记录已经输出的节点
        int n=0;
        Stack<Integer> stack=new Stack<Integer>();
        // 遍历图的n个节点，将入度为0的节点入栈
        for(int i=0;i<g.n;i++){
            if(g.nodes[i].count==0){
                stack.push(i);
            }
        }
        // 开始访问栈中入度为0的节点
        while(!stack.isEmpty()){
            // 出栈
            int t=stack.pop();
            n++;
            print(g,t);
            // 将该节点，及从该节点出发的边去掉（即对应的入度减1）
            ArcNode p=g.nodes[t].firstArc;
            // 对于每一个邻接节点，入度减1
            while(p!=null){
                g.nodes[p.num].count--;
                if(g.nodes[p.num].count==0){
                    stack.push(p.num);
                }
                p=p.nextArc;
            }
        }
        if(n==g.n){
            return true;
        }else{
            return false;
        }
    }
}

public class ArcGraph2 {

    class ArcNode{
        int num;// 节点编号（从0开始）
        ArcNode nextArc;
        public ArcNode(int num){
            this.num=num;
            this.nextArc=null;
        }
    }
    
    class VNode{
        int num;// 节点编号（从0开始）
        String info;// 节点信息
        int count;// 节点入度
        ArcNode firstArc;
        public VNode(int num){
            this.num=num;
            count=0;
            this.info=null;
            this.firstArc=null;
        }
        @Override
        public String toString() {
            return "VNode [num=" + num + ", info=" + info + ", count=" + count
                    + ", firstArc=" + firstArc + "]";
        }
        
    }
    
    // 节点数
    int n;
    // 边数
    int e;
    
    // 节点数组
    VNode[] nodes;
    
    public ArcGraph2(int n,int e){
        this.n=n;
        this.e=e;
        nodes=new VNode[n];// 因为节点编号从0开始
        for(int i=0;i<n;i++){
            nodes[i]=new VNode(i);
        }
    }

    // 节点vi的邻接节点vj
    public void insertAdj(int vi, int vj) {
        nodes[vj].count++;
        ArcNode p=nodes[vi].firstArc;
        if(p==null){
            nodes[vi].firstArc=new ArcNode(vj);
        }else{
            while(p.nextArc!=null){
                p=p.nextArc;
            }
            p.nextArc=new ArcNode(vj);
        }
        
    }
}