精华内容
下载资源
问答
  • 拓扑排序详解

    2020-09-09 10:17:34
    拓扑排序详解 本文转载自https://blog.csdn.net/qq_35644234/article/details/60578189 前言 The time of test,family is best. Name:Willam Time:2017/3/6 1、拓扑排序的介绍 对一个有向无环图(Directed Acyclic ...

    拓扑排序详解

    本文转载自https://blog.csdn.net/qq_35644234/article/details/60578189

    前言
    The time of test,family is best.
    Name:Willam
    Time:2017/3/6

    1、拓扑排序的介绍
    对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。
    拓扑排序对应施工的流程图具有特别重要的作用,它可以决定哪些子工程必须要先执行,哪些子工程要在某些工程执行后才可以执行。为了形象地反映出整个工程中各个子工程(活动)之间的先后关系,可用一个有向图来表示,图中的顶点代表活动(子工程),图中的有向边代表活动的先后关系,即有向边的起点的活动是终点活动的前序活动,只有当起点活动完成之后,其终点活动才能进行。通常,我们把这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network),简称AOV网。
    一个AOV网应该是一个有向无环图,即不应该带有回路,因为若带有回路,则回路上的所有活动都无法进行(对于数据流来说就是死循环)。在AOV网中,若不存在回路,则所有活动可排列成一个线性序列,使得每个活动的所有前驱活动都排在该活动的前面,我们把此序列叫做拓扑序列(Topological order),由AOV网构造拓扑序列的过程叫做拓扑排序(Topological sort)。AOV网的拓扑序列不是唯一的,满足上述定义的任一线性序列都称作它的拓扑序列。

    2、拓扑排序的实现步骤
    在有向图中选一个没有前驱的顶点并且输出
    从图中删除该顶点和所有以它为尾的弧(白话就是:删除所有和它有关的边)
    重复上述两步,直至所有顶点输出,或者当前图中不存在无前驱的顶点为止,后者代表我们的有向图是有环的,因此,也可以通过拓扑排序来判断一个图是否有环。
    3、拓扑排序示例手动实现
    如果我们有如下的一个有向无环图,我们需要对这个图的顶点进行拓扑排序,过程如下:
    在这里插入图片描述

    首先,我们发现V6和v1是没有前驱的,所以我们就随机选去一个输出,我们先输出V6,删除和V6有关的边,得到如下图结果:
    在这里插入图片描述

    然后,我们继续寻找没有前驱的顶点,发现V1没有前驱,所以输出V1,删除和V1有关的边,得到下图的结果:
    在这里插入图片描述

    然后,我们又发现V4和V3都是没有前驱的,那么我们就随机选取一个顶点输出(具体看你实现的算法和图存储结构),我们输出V4,得到如下图结果:
    在这里插入图片描述

    然后,我们输出没有前驱的顶点V3,得到如下结果:
    在这里插入图片描述

    然后,我们分别输出V5和V2,最后全部顶点输出完成,该图的一个拓扑序列为:

    v6–>v1—->v4—>v3—>v5—>v2

    4、拓扑排序的代码实现
    下面,我们将用两种方法来实现我么的拓扑排序:

    Kahn算法
    基于DFS的拓扑排序算法
    首先我们先介绍第一个算法的思路:
    Kahn的算法的思路其实就是我们之前那个手动展示的拓扑排序的实现,我们先使用一个栈保存入度为0 的顶点,然后输出栈顶元素并且将和栈顶元素有关的边删除,减少和栈顶元素有关的顶点的入度数量并且把入度减少到0的顶点也入栈。具体的代码如下:

    bool Graph_DG::topological_sort() {
        cout << "图的拓扑序列为:" << endl;
        //栈s用于保存栈为空的顶点下标
        stack<int> s;
        int i;
        ArcNode * temp;
        //计算每个顶点的入度,保存在indgree数组中
        for (i = 0; i != this->vexnum; i++) {
            temp = this->arc[i].firstarc;
            while (temp) {
                ++this->indegree[temp->adjvex];
                temp = temp->next;
            }
    
        }
    
        //把入度为0的顶点入栈
        for (i = 0; i != this->vexnum; i++) {
            if (!indegree[i]) {
                s.push(i); 
            }
        }
        //count用于计算输出的顶点个数
        int count=0;
        while (!s.empty()) {//如果栈为空,则结束循环
            i = s.top();
            s.pop();//保存栈顶元素,并且栈顶元素出栈
            cout << this->arc[i].data<<" ";//输出拓扑序列
            temp = this->arc[i].firstarc;
            while (temp) {
                if (!(--this->indegree[temp->adjvex])) {//如果入度减少到为0,则入栈
                    s.push(temp->adjvex);
                }
                temp = temp->next;
            }
            ++count;
        }
        if (count == this->vexnum) {
            cout << endl;
            return true;
        } 
        cout << "此图有环,无拓扑序列" << endl;
        return false;//说明这个图有环
    }
    

    现在,我们来介绍第二个算法的思路:
    其实DFS就是深度优先搜索,它每次都沿着一条路径一直往下搜索,知道某个顶点没有了出度时,就停止递归,往回走,所以我们就用DFS的这个思路,我们可以得到一个有向无环图的拓扑序列,其实DFS很像Kahn算法的逆过程。具体的代码实现如下:

    bool Graph_DG::topological_sort_by_dfs() {
        stack<string> result;
        int i;
        bool * visit = new bool[this->vexnum];
        //初始化我们的visit数组
        memset(visit, 0, this->vexnum);
        cout << "基于DFS的拓扑排序为:" << endl;
        //开始执行DFS算法
        for (i = 0; i < this->vexnum; i++) {
            if (!visit[i]) {
                dfs(i, visit, result);
            }
        }
        //输出拓扑序列,因为我们每次都是找到了出度为0的顶点加入栈中,
        //所以输出时其实就要逆序输出,这样就是每次都是输出入度为0的顶点
        for (i = 0; i < this->vexnum; i++) {
            cout << result.top() << " ";
            result.pop();
        }
        cout << endl;
        return true;
    }
    void Graph_DG::dfs(int n, bool * & visit, stack<string> & result) {
    
            visit[n] = true;
            ArcNode * temp = this->arc[n].firstarc;
            while (temp) {
                if (!visit[temp->adjvex]) {
                    dfs(temp->adjvex, visit,result);
                }
                temp = temp->next;
            }
            //由于加入顶点到集合中的时机是在dfs方法即将退出之时,
            //而dfs方法本身是个递归方法,
            //仅仅要当前顶点还存在边指向其他不论什么顶点,
            //它就会递归调用dfs方法,而不会退出。
            //因此,退出dfs方法,意味着当前顶点没有指向其他顶点的边了
            //,即当前顶点是一条路径上的最后一个顶点。
            //换句话说其实就是此时该顶点出度为0了
            result.push(this->arc[n].data);
    
    }
    

    两种算法总结:
    对于基于DFS的算法,增加结果集的条件是:顶点的出度为0。这个条件和Kahn算法中入度为0的顶点集合似乎有着异曲同工之妙,Kahn算法不须要检测图是否为DAG,假设图为DAG,那么在入度为0的栈为空之后,图中还存在没有被移除的边,这就说明了图中存在环路。而基于DFS的算法须要首先确定图为DAG,当然也可以做出适当调整,让环路的检测測和拓扑排序同一时候进行,毕竟环路检測也可以在DFS的基础上进行。
    二者的复杂度均为O(V+E)。

    5、完整的代码和输出展示
    topological_sort.h文件的代码
    /***********************************************************/
    /
    程序作者:Willam /
    /
    程序完成时间:2017/3/6 /
    /
    有任何问题请联系:2930526477@qq.com /
    /
    ***********************************************************/
    //@尽量写出完美的程序

    #pragma once
    //#pragma once是一个比较常用的C/C++杂注,
    //只要在头文件的最开始加入这条杂注,
    //就能够保证头文件只被编译一次。

    /*
    拓扑排序必须是对有向图的操作
    算法实现:
    (1)Kahn算法
    (2)DFS算法
    采用邻接表存储图

    */
    #include<iostream>
    #include<string>
    #include<stack>
    using namespace std;
    //表结点
    struct ArcNode {
        ArcNode * next; //下一个关联的边
        int adjvex;   //保存弧尾顶点在顶点表中的下标
    };
    struct Vnode {
        string data; //顶点名称
        ArcNode * firstarc; //第一个依附在该顶点边
    };
    
    class Graph_DG {
    private:
        int vexnum; //图的顶点数
        int edge;   //图的边数
        int * indegree; //每条边的入度情况
        Vnode * arc; //邻接表
    public:
        Graph_DG(int, int);
        ~Graph_DG();
        //检查输入边的顶点是否合法
        bool check_edge_value(int,int);
        //创建一个图
        void createGraph();
        //打印邻接表
        void print();
        //进行拓扑排序,Kahn算法
        bool topological_sort();
        //进行拓扑排序,DFS算法
        bool topological_sort_by_dfs();
        void dfs(int n,bool * & visit, stack<string> & result);
    };
    

    topological_sort.cpp文件代码

    #include"topological_sort.h"
    
    Graph_DG::Graph_DG(int vexnum, int edge) {
        this->vexnum = vexnum;
        this->edge = edge;
        this->arc = new Vnode[this->vexnum];
        this->indegree = new int[this->vexnum];
        for (int i = 0; i < this->vexnum; i++) {
            this->indegree[i] = 0;
            this->arc[i].firstarc = NULL;
            this->arc[i].data = "v" + to_string(i + 1);
        }
    }
    //释放内存空间
    Graph_DG::~Graph_DG() {
        ArcNode * p, *q;
        for (int i = 0; i < this->vexnum; i++) {
            if (this->arc[i].firstarc) {
                p = this->arc[i].firstarc;
                while (p) {
                    q = p->next;
                    delete p;
                    p = q;
                }
            }
        }
        delete [] this->arc;
        delete [] this->indegree;
    }
    //判断我们每次输入的的边的信息是否合法
    //顶点从1开始编号
    bool Graph_DG::check_edge_value(int start, int end) {
        if (start<1 || end<1 || start>vexnum || end>vexnum) {
            return false;
        }
        return true;
    }
    void Graph_DG::createGraph() {
        int count = 0;
        int start, end;
        cout << "输入每条起点和终点的顶点编号(从1开始编号)" << endl;
        while (count != this->edge) {
            cin >> start;
            cin >> end;
            //检查边是否合法
            while (!this->check_edge_value(start, end)) {
                cout << "输入的顶点不合法,请重新输入" << endl;
                cin >> start;
                cin >> end;
            }
            //声明一个新的表结点
            ArcNode * temp = new ArcNode;
            temp->adjvex = end - 1;
            temp->next = NULL;
            //如果当前顶点的还没有边依附时,
            if (this->arc[start - 1].firstarc == NULL) {
                this->arc[start - 1].firstarc = temp;
            }
            else {
                ArcNode * now = this->arc[start - 1].firstarc;
                while(now->next) {
                    now = now->next;
                }//找到该链表的最后一个结点
                now->next = temp;
            }
            ++count;
        }
    }
    void Graph_DG::print() {
        int count = 0;
        cout << "图的邻接矩阵为:" << endl;
        //遍历链表,输出链表的内容
        while (count != this->vexnum) {
            //输出链表的结点
            cout << this->arc[count].data<<" ";
            ArcNode * temp = this->arc[count].firstarc;
            while (temp) {
                cout<<"<"<< this->arc[count].data<<","<< this->arc[temp->adjvex].data<<"> ";
                temp = temp->next;
            }
            cout << "^" << endl;
            ++count;
        }
    }
    
    bool Graph_DG::topological_sort() {
        cout << "图的拓扑序列为:" << endl;
        //栈s用于保存栈为空的顶点下标
        stack<int> s;
        int i;
        ArcNode * temp;
        //计算每个顶点的入度,保存在indgree数组中
        for (i = 0; i != this->vexnum; i++) {
            temp = this->arc[i].firstarc;
            while (temp) {
                ++this->indegree[temp->adjvex];
                temp = temp->next;
            }
    
        }
    
        //把入度为0的顶点入栈
        for (i = 0; i != this->vexnum; i++) {
            if (!indegree[i]) {
                s.push(i); 
            }
        }
        //count用于计算输出的顶点个数
        int count=0;
        while (!s.empty()) {//如果栈为空,则结束循环
            i = s.top();
            s.pop();//保存栈顶元素,并且栈顶元素出栈
            cout << this->arc[i].data<<" ";//输出拓扑序列
            temp = this->arc[i].firstarc;
            while (temp) {
                if (!(--this->indegree[temp->adjvex])) {//如果入度减少到为0,则入栈
                    s.push(temp->adjvex);
                }
                temp = temp->next;
            }
            ++count;
        }
        if (count == this->vexnum) {
            cout << endl;
            return true;
        } 
        cout << "此图有环,无拓扑序列" << endl;
        return false;//说明这个图有环
    }
    bool Graph_DG::topological_sort_by_dfs() {
        stack<string> result;
        int i;
        bool * visit = new bool[this->vexnum];
        //初始化我们的visit数组
        memset(visit, 0, this->vexnum);
        cout << "基于DFS的拓扑排序为:" << endl;
        //开始执行DFS算法
        for (i = 0; i < this->vexnum; i++) {
            if (!visit[i]) {
                dfs(i, visit, result);
            }
        }
        //输出拓扑序列,因为我们每次都是找到了出度为0的顶点加入栈中,
        //所以输出时其实就要逆序输出,这样就是每次都是输出入度为0的顶点
        for (i = 0; i < this->vexnum; i++) {
            cout << result.top() << " ";
            result.pop();
        }
        cout << endl;
        return true;
    }
    void Graph_DG::dfs(int n, bool * & visit, stack<string> & result) {
    
            visit[n] = true;
            ArcNode * temp = this->arc[n].firstarc;
            while (temp) {
                if (!visit[temp->adjvex]) {
                    dfs(temp->adjvex, visit,result);
                }
                temp = temp->next;
            }
            //由于加入顶点到集合中的时机是在dfs方法即将退出之时,
            //而dfs方法本身是个递归方法,
            //仅仅要当前顶点还存在边指向其他不论什么顶点,
            //它就会递归调用dfs方法,而不会退出。
            //因此,退出dfs方法,意味着当前顶点没有指向其他顶点的边了
            //,即当前顶点是一条路径上的最后一个顶点。
            //换句话说其实就是此时该顶点出度为0了
            result.push(this->arc[n].data);
            }
    

    main.cpp文件:

    #include"topological_sort.h"
    
    //检验输入边数和顶点数的值是否有效,可以自己推算为啥:
    //顶点数和边数的关系是:((Vexnum*(Vexnum - 1)) / 2) < edge
    bool check(int Vexnum, int edge) {
        if (Vexnum <= 0 || edge <= 0 || ((Vexnum*(Vexnum - 1)) / 2) < edge)
            return false;
        return true;
    }
    int main() {
        int vexnum; int edge;
    
    
        cout << "输入图的顶点个数和边的条数:" << endl;
        cin >> vexnum >> edge;
        while (!check(vexnum, edge)) {
            cout << "输入的数值不合法,请重新输入" << endl;
            cin >> vexnum >> edge;
        }
        Graph_DG graph(vexnum, edge);
        graph.createGraph();
        graph.print();
        graph.topological_sort();
        graph.topological_sort_by_dfs();
        system("pause");
        return 0;
    
    }
    

    输入:
    在这里插入图片描述

    输出:
    在这里插入图片描述

    输入:
    在这里插入图片描述

    输出:
    在这里插入图片描述

    展开全文
  • 拓扑排序 详解

    千次阅读 2016-08-17 10:51:11
    本文将从以下几个方面介绍拓扑排序拓扑排序的定义和前置条件和离散数学中偏序/全序概念的联系 典型实现算法 Kahn算法基于DFS的算法 解的唯一性问题 实际例子 取材自以下材料: ...

    本文将从以下几个方面介绍拓扑排序:

    • 拓扑排序的定义和前置条件
    • 和离散数学中偏序/全序概念的联系
    • 典型实现算法
      • Kahn算法
      • 基于DFS的算法
    • 解的唯一性问题
    • 实际例子

    取材自以下材料:

    http://en.wikipedia.org/wiki/Topological_sorting

    http://en.wikipedia.org/wiki/Hamiltonian_path


    定义和前置条件:

    定义:将有向图中的顶点以线性方式进行排序。即对于任何连接自顶点u到顶点v的有向边uv,在最后的排序结果中,顶点u总是在顶点v的前面。

     

    如果这个概念还略显抽象的话,那么不妨考虑一个非常非常经典的例子——选课。我想任何看过数据结构相关书籍的同学都知道它吧。假设我非常想学习一门机器学习的课程,但是在修这么课程之前,我们必须要学习一些基础课程,比如计算机科学概论,C语言程序设计,数据结构,算法等等。那么这个制定选修课程顺序的过程,实际上就是一个拓扑排序的过程,每门课程相当于有向图中的一个顶点,而连接顶点之间的有向边就是课程学习的先后关系。只不过这个过程不是那么复杂,从而很自然的在我们的大脑中完成了。将这个过程以算法的形式描述出来的结果,就是拓扑排序。

     

    那么是不是所有的有向图都能够被拓扑排序呢?显然不是。继续考虑上面的例子,如果告诉你在选修计算机科学概论这门课之前需要你先学习机器学习,你是不是会被弄糊涂?在这种情况下,就无法进行拓扑排序,因为它中间存在互相依赖的关系,从而无法确定谁先谁后。在有向图中,这种情况被描述为存在环路。因此,一个有向图能被拓扑排序的充要条件就是它是一个有向无环图(DAGDirected Acyclic Graph)


    偏序/全序关系:

    偏序和全序实际上是离散数学中的概念。

    这里不打算说太多形式化的定义,形式化的定义教科书上或者上面给的链接中就说的很详细。

     

    还是以上面选课的例子来描述这两个概念。假设我们在学习完了算法这门课后,可以选修机器学习或者计算机图形学。这个或者表示,学习机器学习和计算机图形学这两门课之间没有特定的先后顺序。因此,在我们所有可以选择的课程中,任意两门课程之间的关系要么是确定的(即拥有先后关系),要么是不确定的(即没有先后关系),绝对不存在互相矛盾的关系(即环路)以上就是偏序的意义,抽象而言,有向图中两个顶点之间不存在环路,至于连通与否,是无所谓的。所以,有向无环图必然是满足偏序关系的。

     

    理解了偏序的概念,那么全序就好办了。所谓全序,就是在偏序的基础之上,有向无环图中的任意一对顶点还需要有明确的关系(反映在图中,就是单向连通的关系,注意不能双向连通,那就成环了)可见,全序就是偏序的一种特殊情况。回到我们的选课例子中,如果机器学习需要在学习了计算机图形学之后才能学习(可能学的是图形学领域相关的机器学习算法……),那么它们之间也就存在了确定的先后顺序,原本的偏序关系就变成了全序关系。

     

    实际上,很多地方都存在偏序和全序的概念。

    比如对若干互不相等的整数进行排序,最后总是能够得到唯一的排序结果(从小到大,下同)。这个结论应该不会有人表示疑问吧:)但是如果我们以偏序/全序的角度来考虑一下这个再自然不过的问题,可能就会有别的体会了。

     

    那么如何用偏序/全序来解释排序结果的唯一性呢?

    我们知道不同整数之间的大小关系是确定的,即1总是小于4的,不会有人说1大于或者等于4吧。这就是说,这个序列是满足全序关系的。而对于拥有全序关系的结构(如拥有不同整数的数组),在其线性化(排序)之后的结果必然是唯一的。对于排序的算法,我们评价指标之一是看该排序算法是否稳定,即值相同的元素的排序结果是否和出现的顺序一致。比如,我们说快速排序是不稳定的,这是因为最后的快排结果中相同元素的出现顺序和排序前不一致了。如果用偏序的概念可以这样解释这一现象:相同值的元素之间的关系是无法确定的。因此它们在最终的结果中的出现顺序可以是任意的。而对于诸如插入排序这种稳定性排序,它们对于值相同的元素,还有一个潜在的比较方式,即比较它们的出现顺序,出现靠前的元素大于出现后出现的元素。因此通过这一潜在的比较,将偏序关系转换为了全序关系,从而保证了结果的唯一性。

     

    拓展到拓扑排序中,结果具有唯一性的条件也是其所有顶点之间都具有全序关系。如果没有这一层全序关系,那么拓扑排序的结果也就不是唯一的了。在后面会谈到,如果拓扑排序的结果唯一,那么该拓扑排序的结果同时也代表了一条哈密顿路径。


    典型实现算法:

    Kahn算法:

    摘一段维基百科上关于Kahn算法的伪码描述:

    L← Empty list that will contain the sorted elements
    S ← Set of all nodes with no incoming edges
    while S is non-empty do
        remove a node n from S
        insert n into L
        foreach node m with an edge e from nto m do
            remove edge e from thegraph
            ifm has no other incoming edges then
                insert m into S
    if graph has edges then
        return error (graph has at least onecycle)
    else 
        return L (a topologically sortedorder)

     

    不难看出该算法的实现十分直观,关键在于需要维护一个入度为0的顶点的集合:

    每次从该集合中取出(没有特殊的取出规则,随机取出也行,使用队列/栈也行,下同)一个顶点,将该顶点放入保存结果的List中。

    紧接着循环遍历由该顶点引出的所有边,从图中移除这条边,同时获取该边的另外一个顶点,如果该顶点的入度在减去本条边之后为0,那么也将这个顶点放到入度为0的集合中。然后继续从集合中取出一个顶点…………

     

    当集合为空之后,检查图中是否还存在任何边,如果存在的话,说明图中至少存在一条环路。不存在的话则返回结果List,此List中的顺序就是对图进行拓扑排序的结果。


    实现代码:

    [java] view plain copy
     print?在CODE上查看代码片派生到我的代码片
    1. public class KahnTopological  
    2. {  
    3.     private List<Integer> result;   // 用来存储结果集  
    4.     private Queue<Integer> setOfZeroIndegree;  // 用来存储入度为0的顶点  
    5.     private int[] indegrees;  // 记录每个顶点当前的入度  
    6.     private int edges;  
    7.     private Digraph di;  
    8.       
    9.     public KahnTopological(Digraph di)  
    10.     {  
    11.         this.di = di;  
    12.         this.edges = di.getE();  
    13.         this.indegrees = new int[di.getV()];  
    14.         this.result = new ArrayList<Integer>();  
    15.         this.setOfZeroIndegree = new LinkedList<Integer>();  
    16.           
    17.         // 对入度为0的集合进行初始化  
    18.         Iterable<Integer>[] adjs = di.getAdj();  
    19.         for(int i = 0; i < adjs.length; i++)  
    20.         {  
    21.             // 对每一条边 v -> w   
    22.             for(int w : adjs[i])  
    23.             {  
    24.                 indegrees[w]++;  
    25.             }  
    26.         }  
    27.           
    28.         for(int i = 0; i < indegrees.length; i++)  
    29.         {  
    30.             if(0 == indegrees[i])  
    31.             {  
    32.                 setOfZeroIndegree.enqueue(i);  
    33.             }  
    34.         }  
    35.         process();  
    36.     }  
    37.       
    38.     private void process()  
    39.     {  
    40.         while(!setOfZeroIndegree.isEmpty())  
    41.         {  
    42.             int v = setOfZeroIndegree.dequeue();  
    43.               
    44.             // 将当前顶点添加到结果集中  
    45.             result.add(v);  
    46.               
    47.             // 遍历由v引出的所有边  
    48.             for(int w : di.adj(v))  
    49.             {  
    50.                 // 将该边从图中移除,通过减少边的数量来表示  
    51.                 edges--;  
    52.                 if(0 == --indegrees[w])   // 如果入度为0,那么加入入度为0的集合  
    53.                 {  
    54.                     setOfZeroIndegree.enqueue(w);  
    55.                 }  
    56.             }  
    57.         }  
    58.         // 如果此时图中还存在边,那么说明图中含有环路  
    59.         if(0 != edges)  
    60.         {  
    61.             throw new IllegalArgumentException("Has Cycle !");  
    62.         }  
    63.     }  
    64.       
    65.     public Iterable<Integer> getResult()  
    66.     {  
    67.         return result;  
    68.     }  
    69. }  




    对上图进行拓扑排序的结果:

    2->8->0->3->7->1->5->6->9->4->11->10->12


    复杂度分析:

    初始化入度为0的集合需要遍历整张图,检查每个节点和每条边,因此复杂度为O(E+V);

    然后对该集合进行操作,又需要遍历整张图中的,每条边,复杂度也为O(E+V);

    因此Kahn算法的复杂度即为O(E+V)


    基于DFS的拓扑排序:

    除了使用上面直观的Kahn算法之外,还能够借助深度优先遍历来实现拓扑排序。这个时候需要使用到栈结构来记录拓扑排序的结果。

    同样摘录一段维基百科上的伪码:

    L ← Empty list that will contain the sorted nodes
    S ← Set of all nodes with no outgoing edges
    for each node n in S do
        visit(n) 
    function visit(node n)
        if n has not been visited yet then
            mark n as visited
            for each node m with an edgefrom m to ndo
                visit(m)
            add n to L

    DFS的实现更加简单直观,使用递归实现。利用DFS实现拓扑排序,实际上只需要添加一行代码,即上面伪码中的最后一行:add n to L

    需要注意的是,将顶点添加到结果List中的时机是在visit方法即将退出之时。

    这个算法的实现非常简单,但是要理解的话就相对复杂一点。

    关键在于为什么在visit方法的最后将该顶点添加到一个集合中,就能保证这个集合就是拓扑排序的结果呢?

    因为添加顶点到集合中的时机是在dfs方法即将退出之时,而dfs方法本身是个递归方法,只要当前顶点还存在边指向其它任何顶点,它就会递归调用dfs方法,而不会退出。因此,退出dfs方法,意味着当前顶点没有指向其它顶点的边了,即当前顶点是一条路径上的最后一个顶点。

     

    下面简单证明一下它的正确性:

    考虑任意的边v->w,当调用dfs(v)的时候,有如下三种情况:

    1. dfs(w)还没有被调用,即w还没有被mark,此时会调用dfs(w),然后当dfs(w)返回之后,dfs(v)才会返回
    1. dfs(w)已经被调用并返回了,即w已经被mark
    1. dfs(w)已经被调用但是在此时调用dfs(v)的时候还未返回

    需要注意的是,以上第三种情况在拓扑排序的场景下是不可能发生的,因为如果情况3是合法的话,就表示存在一条由wv的路径。而现在我们的前提条件是由vw有一条边,这就导致我们的图中存在环路,从而该图就不是一个有向无环图(DAG),而我们已经知道,非有向无环图是不能被拓扑排序的。

     

    那么考虑前两种情况,无论是情况1还是情况2w都会先于v被添加到结果列表中。所以边v->w总是由结果集中后出现的顶点指向先出现的顶点。为了让结果更自然一些,可以使用栈来作为存储最终结果的数据结构,从而能够保证边v->w总是由结果集中先出现的顶点指向后出现的顶点。


    实现代码:

    [java] view plain copy
     print?在CODE上查看代码片派生到我的代码片
    1. public class DirectedDepthFirstOrder  
    2. {  
    3.     // visited数组,DFS实现需要用到  
    4.     private boolean[] visited;  
    5.     // 使用栈来保存最后的结果  
    6.     private Stack<Integer> reversePost;  
    7.   
    8.     /** 
    9.      * Topological Sorting Constructor 
    10.      */  
    11.     public DirectedDepthFirstOrder(Digraph di, boolean detectCycle)  
    12.     {  
    13.         // 这里的DirectedDepthFirstCycleDetection是一个用于检测有向图中是否存在环路的类  
    14.         DirectedDepthFirstCycleDetection detect = new DirectedDepthFirstCycleDetection(  
    15.                 di);  
    16.           
    17.         if (detectCycle && detect.hasCycle())  
    18.             throw new IllegalArgumentException("Has cycle");  
    19.               
    20.         this.visited = new boolean[di.getV()];  
    21.         this.reversePost = new Stack<Integer>();  
    22.   
    23.         for (int i = 0; i < di.getV(); i++)  
    24.         {  
    25.             if (!visited[i])  
    26.             {  
    27.                 dfs(di, i);  
    28.             }  
    29.         }  
    30.     }  
    31.   
    32.     private void dfs(Digraph di, int v)  
    33.     {  
    34.         visited[v] = true;  
    35.   
    36.         for (int w : di.adj(v))  
    37.         {  
    38.             if (!visited[w])  
    39.             {  
    40.                 dfs(di, w);  
    41.             }  
    42.         }  
    43.   
    44.         // 在即将退出dfs方法的时候,将当前顶点添加到结果集中  
    45.         reversePost.push(v);  
    46.     }  
    47.   
    48.     public Iterable<Integer> getReversePost()  
    49.     {  
    50.         return reversePost;  
    51.     }  
    52. }  

    复杂度分析:

    复杂度同DFS一致,即O(E+V)。具体而言,首先需要保证图是有向无环图,判断图是DAG可以使用基于DFS的算法,复杂度为O(E+V),而后面的拓扑排序也是依赖于DFS,复杂度为O(E+V)

     

    还是对上文中的那张有向图进行拓扑排序,只不过这次使用的是基于DFS的算法,结果是:

    8->7->2->3->0->6->9->10->11->12->1->5->4


    两种实现算法的总结:

    这两种算法分别使用链表和栈来表示结果集。

    对于基于DFS的算法,加入结果集的条件是:顶点的出度为0。这个条件和Kahn算法中入度为0的顶点集合似乎有着异曲同工之妙,这两种算法的思想犹如一枚硬币的两面,看似矛盾,实则不然。一个是从入度的角度来构造结果集,另一个则是从出度的角度来构造。

     

    实现上的一些不同之处:

    Kahn算法不需要检测图为DAG,如果图为DAG,那么在出度为0的集合为空之后,图中还存在没有被移除的边,这就说明了图中存在环路。而基于DFS的算法需要首先确定图为DAG,当然也能够做出适当调整,让环路的检测和拓扑排序同时进行,毕竟环路检测也能够在DFS的基础上进行。

    二者的复杂度均为O(V+E)

     

    环路检测和拓扑排序同时进行的实现:

    [java] view plain copy
     print?在CODE上查看代码片派生到我的代码片
    1. public class DirectedDepthFirstTopoWithCircleDetection  
    2. {  
    3.     private boolean[] visited;  
    4.     // 用于记录dfs方法的调用栈,用于环路检测  
    5.     private boolean[] onStack;  
    6.     // 用于当环路存在时构造之  
    7.     private int[] edgeTo;  
    8.     private Stack<Integer> reversePost;  
    9.     private Stack<Integer> cycle;  
    10.   
    11.     /** 
    12.      * Topological Sorting Constructor 
    13.      */  
    14.     public DirectedDepthFirstTopoWithCircleDetection(Digraph di)  
    15.     {  
    16.         this.visited = new boolean[di.getV()];  
    17.         this.onStack = new boolean[di.getV()];  
    18.         this.edgeTo = new int[di.getV()];  
    19.         this.reversePost = new Stack<Integer>();  
    20.   
    21.         for (int i = 0; i < di.getV(); i++)  
    22.         {  
    23.             if (!visited[i])  
    24.             {  
    25.                 dfs(di, i);  
    26.             }  
    27.         }  
    28.     }  
    29.   
    30.     private void dfs(Digraph di, int v)  
    31.     {  
    32.         visited[v] = true;  
    33.         // 在调用dfs方法时,将当前顶点记录到调用栈中  
    34.         onStack[v] = true;  
    35.   
    36.         for (int w : di.adj(v))  
    37.         {  
    38.             if(hasCycle())  
    39.             {  
    40.                 return;  
    41.             }  
    42.             if (!visited[w])  
    43.             {  
    44.                 edgeTo[w] = v;  
    45.                 dfs(di, w);  
    46.             }  
    47.             else if(onStack[w])  
    48.             {  
    49.                 // 当w已经被访问,同时w也存在于调用栈中时,即存在环路  
    50.                 cycle = new Stack<Integer>();  
    51.                 cycle.push(w);  
    52.                 for(int start = v; start != w; start = edgeTo[start])  
    53.                 {  
    54.                     cycle.push(v);  
    55.                 }  
    56.                 cycle.push(w);  
    57.             }  
    58.         }  
    59.   
    60.         // 在即将退出dfs方法时,将顶点添加到拓扑排序结果集中,同时从调用栈中退出  
    61.         reversePost.push(v);  
    62.         onStack[v] = false;  
    63.     }  
    64.   
    65.     private boolean hasCycle()   
    66.     {  
    67.         return (null != cycle);  
    68.     }  
    69.       
    70.     public Iterable<Integer> getReversePost()  
    71.     {  
    72.         if(!hasCycle())  
    73.         {  
    74.             return reversePost;  
    75.         }  
    76.         else   
    77.         {  
    78.             throw new IllegalArgumentException("Has Cycle: " + getCycle());  
    79.         }  
    80.     }  
    81.       
    82.     public Iterable<Integer> getCycle()   
    83.     {  
    84.         return cycle;  
    85.     }  
    86. }  

    拓扑排序解的唯一性:

    哈密顿路径:

    哈密顿路径是指一条能够对图中所有顶点正好访问一次的路径。本文中只会解释一些哈密顿路径和拓扑排序的关系,至于哈密顿路径的具体定义以及应用,可以参见本文开篇给出的链接。

     

    前面说过,当一个DAG中的任何两个顶点之间都存在可以确定的先后关系时,对该DAG进行拓扑排序的解是唯一的。这是因为它们形成了全序的关系,而对存在全序关系的结构进行线性化之后的结果必然是唯一的(比如对一批整数使用稳定的排序算法进行排序的结果必然就是唯一的)

     

    需要注意的是,非DAG也是能够含有哈密顿路径的,为了利用拓扑排序来实现判断,所以这里讨论的主要是判断DAG中是否含有哈密顿路径的算法,因此下文中的图指代的都是DAG

     

    那么知道了哈密顿路径和拓扑排序的关系,我们如何快速检测一张图是否存在哈密顿路径呢?

    根据前面的讨论,是否存在哈密顿路径的关键,就是确定图中的顶点是否存在全序的关系,而全序的关键,就是任意一对顶点之间都是能够确定先后关系的。因此,我们能够设计一个算法,用来遍历顶点集中的每一对顶点,然后检查它们之间是否存在先后关系,如果所有的顶点对有先后关系,那么该图的顶点集就存在全序关系,即图中存在哈密顿路径。

     

    但是很显然,这样的算法十分低效。对于大规模的顶点集,是无法应用这种解决方案的。通常一个低效的解决办法,十有八九是因为没有抓住现有问题的一些特征而导致的。因此我们回过头来再看看这个问题,有什么特征使我们没有利用的。还是举对整数进行排序的例子:

    比如现在有3 2 1三个整数,我们要对它们进行排序,按照之前的思想,我们分别对(1,2)(2,3)(1,3)进行比较,这样需要三次比较,但是我们很清楚,13的那次比较实际上是多余的。我们为什么知道这次比较是多余的呢?我认为,是我们下意识的利用了整数比较满足传递性的这一规则。但是计算机是无法下意识的使用传递性的,因此只能通过其它的方式来告诉计算机,有一些比较是不必要的。所以,也就有了相对插入排序,选择排序更加高效的排序算法,比如归并排序,快速排序等,将n2的算法加速到了nlogn。或者是利用了问题的特点,采取了更加独特的解决方案,比如基数排序等。

     

    扯远了一点,回到正题。现在我们没有利用到的就是全序关系中传递性这一规则。如何利用它呢,最简单的想法往往就是最实用的,我们还是选择排序,排序后对每对相邻元素进行检测不就间接利用了传递性这一规则嘛?所以,我们先使用拓扑排序对图中的顶点进行排序。排序后,对每对相邻顶点进行检测,看看是否存在先后关系,如果每对相邻顶点都存在着一致的先后关系(在有向图中,这种先后关系以有向边的形式体现,即查看相邻顶点对之间是否存在有向边)。那么就可以确定该图中存在哈密顿路径了,反之则不存在。

     

    实现代码:

    [java] view plain copy
     print?在CODE上查看代码片派生到我的代码片
    1. /** 
    2.  * Hamilton Path Detection for DAG 
    3.  */  
    4. public class DAGHamiltonPath  
    5. {  
    6.     private boolean hamiltonPathPresent;  
    7.     private Digraph di;  
    8.     private KahnTopological kts;  
    9.       
    10.     // 这里使用Kahn算法进行拓扑排序  
    11.     public DAGHamiltonPath(Digraph di, KahnTopological kts)  
    12.     {  
    13.         this.di = di;  
    14.         this.kts = kts;  
    15.           
    16.         process();  
    17.     }  
    18.       
    19.     private void process()  
    20.     {  
    21.         Integer[] topoResult = kts.getResultAsArray();  
    22.           
    23.         // 依次检查每一对相邻顶点,如果二者之间没有路径,则不存在哈密顿路径  
    24.         for(int i = 0; i < topoResult.length - 1; i++)  
    25.         {  
    26.             if(!hasPath(topoResult[i], topoResult[i + 1]))  
    27.             {  
    28.                 hamiltonPathPresent = false;  
    29.                 return;  
    30.             }  
    31.         }  
    32.         hamiltonPathPresent = true;  
    33.     }  
    34.       
    35.     private boolean hasPath(int start, int end)  
    36.     {  
    37.         for(int w : di.adj(start))  
    38.         {  
    39.             if(w == end)  
    40.             {  
    41.                 return true;  
    42.             }  
    43.         }  
    44.         return false;  
    45.     }  
    46.   
    47.     public boolean hasHamiltonPath()  
    48.     {  
    49.         return hamiltonPathPresent;  
    50.     }  
    51. }  

    实际例子:

    TestNG中循环依赖的检测:

    http://blog.csdn.net/dm_vincent/article/details/7631916

     

    以后还会陆续补充一些例子……



    相关代码请参考这里:

    https://github.com/destiny1020/algorithm_playground/tree/master/src/main/java/chap4

    展开全文
  • 拓扑排序详解与实现

    2020-05-17 21:22:07
    拓扑排序详解与实现 介绍 拓扑排序,很多人都可能听说但是不了解的一种算法。或许很多人只知道它是图论的一种排序,至于干什么的不清楚。又或许很多人可能还会认为它是一种啥排序。而实质上它是对有向图的顶点排...
    
    
    

    介绍

    拓扑排序,很多人都可能听说但是不了解的一种算法。或许很多人只知道它是图论的一种排序,至于干什么的不清楚。又或许很多人可能还会认为它是一种啥排序。而实质它是对有向图的顶点排成一个线性序列

    至于定义,百科上是这么说的:

    对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边<u,v>∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序

    为什么会有拓扑排序?拓扑排序有何作用?

    举个例子,学习java系列的教程

    代号 科目 学前需掌握
    A1 javaSE  
    A2 html  
    A3 Jsp A1,A2
    A4 servlet A1
    A5 ssm A3,A4
    A6 springboot A5

    就比如学习java系类(部分)从java基础,到jsp/servlet,到ssm,到springboot,springcloud等是个循序渐进且有依赖的过程。在jsp学习要首先掌握java基础html基础。学习框架要掌握jsp/servlet和jdbc之类才行。那么,这个学习过程即构成一个拓扑序列。当然这个序列也不唯一你可以对不关联的学科随意选择顺序(比如html和java可以随便先开始哪一个。)

    那上述序列可以简单表示为:

    在这里插入图片描述

    其中五种均为可以选择的学习方案,对课程安排可以有参考作用,当然,五个都是拓扑序列。只是选择的策略不同!

    一些其他注意:

    DGA:有向无环图
    AOV网:数据在顶点 可以理解为面向对象
    AOE网:数据在边上,可以理解为面向过程!

    而我们通俗一点的说法,就是按照某种规则将这个图的顶点取出来,这些顶点能够表示什么或者有什么联系

    规则

    • 图中每个顶点只出现一次
    • A在B前面,则不存在B在A前面的路径。(不能成环!!!!)
    • 顶点的顺序是保证所有指向它的下个节点在被指节点前面!(例如A—>B—>C那么A一定在B前面,B一定在C前面)。所以,这个核心规则下只要满足即可,所以拓扑排序序列不一定唯一

    拓扑排序算法分析

    在这里插入图片描述
    正常步骤为(方法不一定唯一)

    • 从DGA图中找到一个没有前驱的顶点输出。(可以遍历,也可以用优先队列维护)
    • 删除以这个点为起点的边。(它的指向的边删除,为了找到下个没有前驱的顶点)
    • 重复上述,直到最后一个顶点被输出。如果还有顶点未被输出,则说明有环!

    对于上图的简单序列,可以简单描述步骤为:

    • 1:删除1或2输出
      在这里插入图片描述
    • 2:删除2或3以及对应边
      在这里插入图片描述
    • 3:删除3或者4以及对应边在这里插入图片描述
    • 3:重复以上规则步骤
      在这里插入图片描述

    这样就完成一次拓扑排序,得到一个拓扑序列,但是这个序列并不唯一!从过程中也看到有很多选择方案,具体得到结果看你算法的设计了。但只要满足即是拓扑排序序列。

    另外观察 1 2 4 3 6 5 7 9这个序列满足我们所说的有关系的节点指向的在前面,被指向的在后面。如果完全没关系那不一定前后(例如1,2)

    拓扑排序代码实现

    对于拓扑排序,如何用代码实现呢?对于拓扑排序,虽然在上面详细介绍了思路和流程,也很通俗易懂。但是实际上代码的实现还是很需要斟酌的,如何在空间和时间上能够得到较好的平衡且取得较好的效率?

    首先要考虑存储。对于节点,首先他有联通点这么多属性。遇到稀疏矩阵还是用邻接表比较好。因为一个节点的指向节点较少,用邻接矩阵较浪费资源

    另外,如果是1,2,3,4,5,6这样的序列求拓扑排序,我们可以考虑用数组,但是如果遇到1,2,88,9999类似数据,可以考虑用map中转一下。那么,

    我们具体的代码思想为:

    • 新建node类,包含节点数值和它的指向(这里直接用list集合替代链表了)
    • 一个数组包含node(这里默认编号较集中)。初始化,添加每个节点指向的时候同时被指的节点入度+1!(A—>C)那么C的入度+1;
    • 扫描一遍所有node。将所有入度为0的点加入一个栈(队列)
    • 当栈(队列)不空的时候,抛出其中任意一个node(栈就是尾,队就是头,顺序无所谓,上面分析了只要同时入度为零可以随便选择顺序)。将node输出,并且node指向的所有元素入度减一如果某个点的入度被减为0,那么就将它加入栈(队列)
    • 重复上述操作,直到栈为空。

    这里主要是利用栈或者队列储存入度只为0的节点,只需要初次扫描表将入度为0的放入栈(队列)中。

    • 这里你或许会问为什么。
    • 因为节点之间是有相关性的,一个节点若想入度为零,那么它的父节点(指向节点)肯定在它为0前入度为0,拆除关联箭头。从父节点角度,它的这次拆除联系,可能导致被指向的入读为0,也可能不为0(还有其他节点指向儿子)

    至于具体demo:

    package 图论;
    
    import java.util.ArrayDeque;
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Queue;
    import java.util.Stack;
    
    public class tuopu {
    	static class node
    	{
    		int value;
    		List<Integer> next;
    		public node(int value) {
    			this.value=value;
    			next=new ArrayList<Integer>();
    		}
    		public void setnext(List<Integer>list) {
    			this.next=list;
    		}
    	}
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		node []nodes=new node[9];//储存节点
    		int a[]=new int[9];//储存入度
    		List<Integer>list[]=new ArrayList[10];//临时空间,为了存储指向的集合
    		for(int i=1;i<9;i++)
    		{
    			nodes[i]=new node(i);
    			list[i]=new ArrayList<Integer>();
    		}
    		initmap(nodes,list,a);
    		
    		//主要流程
    		//Queue<node>q1=new ArrayDeque<node>();
    		Stack<node>s1=new Stack<node>();
    		for(int i=1;i<9;i++)
    		{
    			//System.out.print(nodes[i].next.size()+" 55 ");
    			//System.out.println(a[i]);
    			if(a[i]==0) {s1.add(nodes[i]);}
    			
    		}
    		while(!s1.isEmpty())
    		{
    			node n1=s1.pop();//抛出输出
    		    
    			System.out.print(n1.value+" ");
    			
    			List<Integer>next=n1.next;
    			for(int i=0;i<next.size();i++)
    			{
    				a[next.get(i)]--;//入度减一
    				if(a[next.get(i)]==0)//如果入度为0
    				{
    					s1.add(nodes[next.get(i)]);
    				}
    			}
    		}
    	}
    
    	private static void initmap(node[] nodes, List<Integer>[] list, int[] a) {
    		list[1].add(3);
    		nodes[1].setnext(list[1]);
    		a[3]++;
    		list[2].add(4);list[2].add(6);
    		nodes[2].setnext(list[2]);
    		a[4]++;a[6]++;
    		list[3].add(5);
    		nodes[3].setnext(list[3]);
    		a[5]++;
    		list[4].add(5);list[4].add(6);
    		nodes[4].setnext(list[4]);
    		a[5]++;a[6]++;
    		list[5].add(7);
    		nodes[5].setnext(list[5]);
    		a[7]++;
    		list[6].add(8);
    		nodes[6].setnext(list[6]);
    		a[8]++;
    		list[7].add(8);
    		nodes[7].setnext(list[7]);
    		a[8]++;
    		
    	}
    }
    
    

    输出结果

    2 4 6 1 3 5 7 8

    在这里插入图片描述
    当然,上面说过用栈和队列都可以!如果使用队列就会得到1 2 3 4 5 6 7 8的拓扑序列

    至于图的构造,因为没有条件可能效率并不高,算法也可能不太完美,如有优化错误还请大佬指正!

    相关leetcode题:https://leetcode-cn.com/problems/course-schedule-ii/

    展开全文
  • 拓扑排序详解 拓扑排序是对一个有向图构造拓扑序列。构造时有 2 种结果: 此图全部顶点被输出:说明说明图中无「环」存在, 是 AOV 网 没有输出全部顶点:说明图中有「环」存在,不是 AOV 网 AOV(Activity On ...

    拓扑排序详解


    拓扑排序是对一个有向图构造拓扑序列,解决工程是否能顺利进行的问题。构造时有 2 种结果:

    1. 此图全部顶点被输出:说明说明图中无「环」存在, 是 AOV 网
    2. 没有输出全部顶点:说明图中有「环」存在,不是 AOV 网

    AOV(Activity On Vertex Network) :一种 有向 无回路 的图


    image-20201226125511379

    1. 应用

    排序类似 流程图一样 任务

    例如早上起床的任务:

    例如:这里你只有穿了衬衣才能穿外套,而不是穿了外套再穿衬衣

    image-20201226130755559


    2. 要点


    每次删除一个入度边个数为 0 的点,并刷新其他点的出度边个数。


    3. 图解案例分析

    对下面的图进行拓扑排序:

    image-20201226132037571

    • graph:使用 领接表 作为图的数据结构

    • stack:使用 储存 入度边个数为 0 的点(减少每次查询入度边为 0 的边的计算)

    • inNumber:考虑到始终要计算入度边的数量,所以 在来的 Vertex 顶点结构中 增加 inNumber 来表示入度边的数量。

    数据结构:

    /** 边 */
    static class Edge{
        /** 权重 */
        int weight;
        /** 出度指向的点 */
        int toVertex;
        /** 下一个出度边 */
        Edge next;
    }
    /** 顶点 */
    static class Vertex{
        /** 入度 数量 */
        int inNumber;
        /** 顶点信息 */
        Character data;
        /** 第一条边 */
        Edge firstEdge;
    }
    

    image-20201226132903118


    3.1 初始化:

    将所有入度边数为 0 的点放入 stack 栈中

    (只有 A 入度边数 为 0,将其放入栈中)

    image-20201226133505389


    3.2 删除一个入度边数 为 0 的顶点 A,并刷新其他点的入度边数

    • stack 中弹出 A 点
    • 遍历 A 点的出度边并删除(只有 AB 一条出度边)
    • 刷新其他点的入度边数:
      • B 点的入度边数量刷新为 0
      • 判断 B 入度数量为 0 就入 stack 栈

    image-20201226134335223


    3.3 删除一个入度边数 为 0 的顶点 B,并刷新其他点的入度边数

    • stack 中弹出 B 点
    • 遍历 B 点的出度边并删除(只有 BC 一条出度边)
    • 刷新其他点的入度边数:
      • C 点的入度边数量刷新为 0
      • 判断 C 入度数量为 0 就入 stack 栈

    image-20201226134610500


    3.4 删除一个入度边数 为 0 的顶点 C,并刷新其他点的入度边数

    • stack 中弹出 C 点
    • 遍历 C 点的出度边并删除(C 没有出度边,所以无法刷新其他点的入度边数)
    • stack 栈中数据为空,程序结束

    image-20201226135037190

    4. 代码

    请结合代码理解图解案例分析

    public class TopologicalSort {
        /** 边 */
        static class Edge{
            /** 权重 */
            int weight;
            /** 出度指向的点 */
            int toVertex;
            Edge next;
            public Edge(int weight, int toVertex, Edge next) {
                this.weight = weight;
                this.toVertex = toVertex;
                this.next = next;
            }
        }
        /** 顶点 */
        static class Vertex{
            /** 入度 数量 */
            int inNumber;
            /** 顶点信息 */
            Character data;
            /** 第一条边 */
            Edge firstEdge;
    
            public Vertex(int inNumber, Character data, Edge firstEdge) {
                this.inNumber = inNumber;
                this.data = data;
                this.firstEdge = firstEdge;
            }
        }
        /** 拓扑排序 */
        public static boolean topological(List<Vertex> graph){
            // 输出顶点的个数
            int outVertices = 0;
            // 栈:用来储存入度个数为 0 的顶点
            Stack<Vertex> stack = new Stack<>();
            //将顶点入度个数为 0 的元素入栈
            for (Vertex vertex : graph) {
                if (vertex.inNumber == 0) {
                    stack.push(vertex);
                }
            }
            // 直到 AOV 网中不存在入度为 0 的点 
            while (!stack.empty()){
                // 弹出顶点
                Vertex pop = stack.pop();
                // 输出弹出的顶点
                System.out.println(pop.data);
                // 统计输出个数
                outVertices ++;
                //遍历这个点的出度
                Edge outEdge = pop.firstEdge;
                while (outEdge!=null){
                    //出度的目标入度减少
                    Vertex toVertex = graph.get(outEdge.toVertex);
                    toVertex.inNumber --;
                    //目标减少后 入度为 0 就入栈
                    if (toVertex.inNumber == 0){
                        stack.push(toVertex);
                    }
                    outEdge = outEdge.next;
                }
    
            }
            // 输出所有点才返回 true.
            if (outVertices == graph.size()){
                return true;
            }
            return false;
        }
    		/** 测试 */
        public static void main(String[] args) {
            //构建图 A -> B -> C
            ArrayList<Vertex> graph = new ArrayList<>();
            //环 测试
    //        Edge edge1 = new Edge(10, 1,null);
    //        Edge edge2 = new Edge(10, 2,null);
    //        Edge edge3 = new Edge(10, 0,null);
    //        Vertex a = new Vertex(1, 'A', edge1);
    //        Vertex b = new Vertex(1, 'B', edge2);
    //        Vertex c = new Vertex(1, 'C', edge3);
            //无环 测试
            Edge edge1 = new Edge(10, 1,null);
            Edge edge2 = new Edge(10, 2,null);
            Vertex a = new Vertex(0, 'A', edge1);
            Vertex b = new Vertex(1, 'B', edge2);
            Vertex c = new Vertex(1, 'C', null);
            graph.add(a);
            graph.add(b);
            graph.add(c);
            //判断是否拓扑
            System.out.println(topological(graph));
        }
    }
    
    
    展开全文
  • 数据结构---拓扑排序详解

    万次阅读 多人点赞 2017-03-06 19:54:41
    Time:2017/3/61、拓扑排序的介绍对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。...
  • 图论-拓扑排序详解

    2019-09-29 07:05:06
    拓扑排序(topsort)详解 这篇随笔就信息学奥林匹克竞赛中图论的一个知识点——拓扑排序进行讲解。拓扑排序的内容比较基础,只要求读者学习过并了解信息学中图的相关定义和一些专业名词,但是拓扑排序的变形题目比较...
  • 拓扑排序详解2(ACM-ICPC训练题) 练习1:HUDOJ 1285 确定比赛名次 如何保证输出的拓扑序是再同级别的情况下的最小的呢? 也就是说,当前有节点:1和节点:4,这俩当前都是入度为0,那这个时候我们规定这个1要先输出...
  • 图的拓扑排序详解

    千次阅读 2018-12-06 18:19:45
    拓扑排序:图中的点以线性方式进行排序。即若图中有一条边是u->v,则最后的排序结果中u总在v前面。类似于先序图的概念,必须先到达u点才能到达v点,则u>v。 适用条件: 并不是所有图都可以进行拓扑排序。...
  • 拓扑排序 对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边<u,v>∈E(G),则u在线性序列中出现在v之前。通常,这样的线性...
  • 拓扑排序 拓扑序就是后边走的点有前边的先决条件 上图就是个拓扑序 学数据结构之前必须先学习c语言 以此类推 学习顺序可以是 c语言 数据结构 python 面向对象 c++ linux 网、系统 分布式项目 c语言 linux 数据结构...
  • 拓扑排序详解 + 并查集详解 + 最小生成树(MST)详解【普利姆算法 + 优先队列优化 & 克鲁斯卡尔算法】   本人QQ :2319411771 邮箱 : cyb19950118@163.com  若您发现本文有什么错误,请联系我,我会及时...
  • 拓扑排序详解及其习题

    千次阅读 2019-07-26 17:36:41
    当且仅当图形没有定向循环,即如果它是有向无环图(DAG),则拓扑排序是可能的。  ——来自维基百科   在图论中,由一个有向无环图的顶点组成的序列,当且仅当满足下列 条件 时,称为该图的一个 拓扑...
  • 拓扑排序详解(超详细+模板)

    千次阅读 多人点赞 2019-08-09 19:50:42
    拓扑排序 1.什么是拓扑排序 对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图 中任 意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。通常,...
  •  拓扑排序的算法:选一个入度为 0 的顶点输出,并将其所有后继顶点的入度—1,重复这两步直至输出所有顶点,或找不到入度为 0 的顶点为止,为便于查找入度为 0 的顶点,算法中利用顶点的入度域建立一个存放入度为 0...

空空如也

空空如也

1 2 3 4 5 ... 12
收藏数 231
精华内容 92
关键字:

拓扑排序详解