有向图的拓扑排序

本篇经验主要介绍如何对有向图进行拓扑排序。拓扑排序是有向无环图的一种应用,它是将有向图的顶点排成一个线性序列的过程。那么我们如何对图进行拓扑排序呢?接下来我们一起来看一下吧。

工具/原料

    纸,笔

    智慧的大脑

方法/步骤

    1

    对图进行拓扑排序首先要任意选择一个没有前驱的顶点,然后将它输出。在下面这张图中我们选择1为出发点。

    有向图的拓扑排序

    2

    选择1为出发点之后,我们将它输出,并删除该节点以及与它相关联的所有边。如下图所示。

    有向图的拓扑排序

    3

    然后在删除后的图中继续找一个没有前驱的节点,这里没有前驱的节点只有2和3,这里我们选择3.那么将节点3输出后的图 如下图所示。

    有向图的拓扑排序

    4

    接下来没有前驱的节点只有2和6了。我们这里选择节点6,同样的输出节点6后删除,然后继续找没有前驱的节点。这时候没有前驱的节点只剩下节点2.

    有向图的拓扑排序

    5

    接下来的点继续进行拓扑排序,得到的拓扑排序的一种如下图所示。

    有向图的拓扑排序

    6

    相信大家也都发现其实拓扑排序是不唯一的,我们选择的出发点不同,结果就是不一样的。这里给出大家针对上图几种拓扑排序序列。

    有向图的拓扑排序END

注意事项

    感觉有帮助的话,可以点个赞哟。

温馨提示:经验内容仅供参考,如果您需解决具体问题(尤其法律、医学等领域),建议您详细咨询相关领域专业人士。
免责声明:本文转载来之互联网,不代表本网站的观点和立场。如果你觉得好欢迎分享此网址给你的朋友。
转载请注明出处:https://www.i7q8.com/jiaoyu/2087.html

打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2023年07月12日
下一篇 2023年07月12日
single-end

热门百科

single-end

相关推荐

  • 有向图的拓扑排序

    有向图的拓扑排序,本篇经验主要介绍如何对有向图进行拓扑排序。拓扑排序是有向无环图的一种应用,它是将有向图的顶点排成一个线性序列的过程。那么我们如何对图进行拓扑排序呢?接下来我们一起来看一下吧。...

    2023年07月12日
    0℃
关注微信