有向无环图Directed Acyclic Graph(DAG)

有向无环图Directed Acyclic Graph(DAG)1、DAG有向无环图DirectedAcyclicGraph(DAG)DAG是一个没有有向循环的、有限的有向图。它由有限个顶点和有向边组成,每条有向边都从一个顶点指向另一个顶点;从任意一个顶点出发都不能通过这些有向边回到原来的顶点。有向无环图就是从一个图中的任何一点出发,不管走过多少个分叉路口,都没有回到原来这个点的可能性。条件每个顶点出现且只出现一次若存在一条从顶点A到顶点B的路径,那么在序列中顶点A出现在顶点B的前面。计算一个DAG的拓扑关系

1、DAG

  • 有向无环图Directed Acyclic Graph(DAG)
  • DAG是一个没有 有向循环的、有限的有向图
    1. 它由有限个顶点和有向边组成,每条有向边都从一个顶点指向另一个顶点;
    2. 从任意一个顶点出发都不能通过这些有向边回到原来的顶点
    3. 有向无环图就是从一个图中的任何一点出发,不管走过多少个分叉路口,都没有回到原来这个 点的可能性。
  • 条件
    • 每个顶点出现且只出现一次
    • 若存在一条从顶点 A 到顶点 B 的路径,那么在序列中顶点 A 出现在顶点 B 的前面。
  • 计算一个DAG的拓扑关系
    1. 1→4表示4的入度+1,4是1的邻接点
    2. 首先将边与边的关系确定,建立好入度表和邻接表。
    3. 从入度为0的点开始删除,如上图显然是1的入度为0,先删除。
    4. 判断有无环的方法,对入度数组遍历,如果有的点入度不为0,则表明有环。
    5. { 1, 2, 4, 3, 5 }

在这里插入图片描述

今天的文章有向无环图Directed Acyclic Graph(DAG)分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/9209.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注