拓扑排序及java实现

柔光的暖阳◎ 2023-07-10 08:40 19阅读 0赞

拓扑排序是通过对**有向无环图**进行**深度优先搜索**实现的，对于一个有向无环图G来说，其拓扑排序是G中**所有节点**的一种线性排序，有很多生活活动都可以使用有向无环图来指明事件的优先顺序，比如下图所示的早晨起床过程：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvaG4xMzM3_size_16_color_FFFFFF_t_70][]

上图为某人的早晨起床涉及的一系列活动，图中标注数字为该图可能存在的一种的一种深度优先搜索方案，有些事件之间存在必然的先后顺序，比如打领带之前比如穿衬衣，系腰带之前必须穿裤子等等，有些事件之间没有必然的先后顺序，比如穿袜子跟穿衬衣没有必然的先后顺序，所以该有向图深度优先遍历会生成一个森林。拓扑排序是在深度优先搜索过程中产生的，我们按照节点的截止时间倒叙排序形成的一个链表就是对应的拓扑排序，这里仅将与深度排序不同的不同列举出来，其他的可以参考笔者的另一篇文章：[https://blog.csdn.net/john1337/article/details/104581678][https_blog.csdn.net_john1337_article_details_104581678]

//拓扑排序
        @Test
        public void topologicalSort(){
            Graph g= new Graph(7);
    
            Vertex v1 = new Vertex(1);
            Vertex v2 = new Vertex(2);
            Vertex v3 = new Vertex(3);
            Vertex v4 = new Vertex(4);
            Vertex v5 = new Vertex(5);
            Vertex v6 = new Vertex(6);
            Vertex v7 = new Vertex(7);
            //初始化图的顶点数组
            g.addVertex(v1);
            g.addVertex(v2);
            g.addVertex(v3);
            g.addVertex(v4);
            g.addVertex(v5);
            g.addVertex(v6);
            g.addVertex(v7);
            //初始化邻接矩阵
            v1.addVertex(v2);
            v1.addVertex(v4);
            //
            v2.addVertex(v4);
            v2.addVertex(v7);
            //
            v3.addVertex(v1);
            v3.addVertex(v5);
            //
            v4.addVertex(v5);
            v4.addVertex(v6);
            //
            v5.addVertex(v6);
            //
            v7.addVertex(v6);
            //
            System.out.println("以v3为起始点遍历");
            init(g);
            for(Vertex v:g.getVertexes()){
                if(v.getColor() == VertexColor.WHITE){
                    dfsVisit(g,v);
                }
            }
            //输出拓扑排序
            println("输出拓扑排序");
            for(Vertex v:toplogicalTree){
                System.out.println(v.toString());
            }
        }
    
        private void init(Graph g){
            for(Vertex v:g.getVertexes()){
                v.setColor(VertexColor.WHITE);
                v.pre = null;
                v.start =-1;
                v.end =0;
            }
            //重置time
            time = 0;
        }
    
        private void dfsVisit(Graph g,Vertex v){
            time = time +1;
            v.start = time;
            v.setColor(VertexColor.GRAY);
            for(Vertex c:v.getAdjList()){
                if(c.getColor() == VertexColor.WHITE){
                    c.pre = v;
                    dfsVisit(g,c);
                }
            }
            //遍历完子节点
            v.setColor(VertexColor.BLACK);
            time = time +1;
            v.end = time;
            //下面的操作为队列操作，所以截止时间最大的将在队列的最靠前位置
            toplogicalTree.addFirst(v);
        }
    }

PS：

1、上面代码中涉及到的所有类可以在[https://blog.csdn.net/john1337/article/details/104581678][https_blog.csdn.net_john1337_article_details_104581678]博文中找到

2、拓扑排序算法的时间复杂度为O(V+E)，V为该有向无环图边数，E为该图顶点数

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvaG4xMzM3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200301165524296.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvaG4xMzM3,size_16,color_FFFFFF,t_70
[https_blog.csdn.net_john1337_article_details_104581678]: https://blog.csdn.net/john1337/article/details/104581678