admin管理员组

文章数量:1037775

【拓扑排序】有向无环图、定点活动图、拓扑排序简介

Ⅰ. 有向无环图（DAG图）

​ DAG 图全称为 Directed Acyclic Graph，就是一个有向 + 无环的图。

​ DAG 图是相较于有向树的更特殊的图。它的作用挺重要的，比如：检查一个图是否有环，可以通过遍历+标记的方式进行检查，若某个顶点的弧指向了另一个已经遍历过的顶点，则该图必定含有环。

Ⅱ. AOV网 – 顶点活动图

​ 定义：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，称为 AOV网（Activity On Vertex Network），AOV 网中的弧表示活动之间的某种约束关系。

​ 此外 AOV 网中 不存在回路（即有向无环图），如下图所示：

Ⅲ. 拓扑排序

​ 其实拓扑排序非常的简单，一些书上的概念说的比较复杂，我们只需要记住，拓扑排序就是 找到 AOV 网中活动的先后执行顺序，所以拓扑排序的结果不是唯一的，因为一些活动是可以并行的。

​ 比如将上面途中的炒肉顺序，按照先后次序可以得到下面的一种情况：

​ 并且 拓扑排序不能出现环，因为其实现原理中如果出现了环的话，就无法得出一个序列了，所以拓扑排序的应用之一就是用来 判断图中是否存在环！

Ⅳ. 实现拓扑排序

可以看到其实拓扑排序并不难，无非就是借助队列和 BFS 来完成！下面是实现的步骤：

  1. 初始化：
    • 把所有入度为 0 的节点加入到队列中
  2. 当队列不为空的时候：
    1. 拿出队头节点，加入到最终结果中。
    2. 删除与该元素相连的边。
    3. 进行判断：
      • 判断 与删除边相连的点，是否入度变成了 0，如果为 0 的话则将其加入到队列中。

但此时有一个问题，就是我们需要 建图，并且需要知道每个节点的入度，所以我们有两种方式来建图：

  1. 看稠密度（即看数据量大小）
    • 邻接矩阵
    • 邻接表
  2. 根据算法流程，灵活建图

​ 一般来说邻接矩阵比较简单，我们这里主要来讲一下邻接表的建图方式！邻接表的建图方式不一定就要用链表结构来实现，也是可以使用 STL 中一些容器比如说 vector 或者 unordered_map 来实现，如下所示：

  • vector<vector<T>>
  • unordered_map<T, vector<V>>

​ 可以看到这两种方式其实和链表结构的思想是差不多的，并且使用哈希表来作为邻接表的建图方式是更加灵活的，因为它两个参数的类型是可以不同的！所以后面 我们大多都是采用哈希表来建立邻接表！

​ 而至于节点的入度的话，我们可以单独 用一个 vector 来存放入度，然后只需要在 建图的过程中将指向当前节点的次数累加一下 即可！

​ 具体如何建图以及求入度，可以看后面具体的ti’mu

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-03-11，如有侵权请联系 cloudcommunity@tencent 删除遍历队列链表排序容器

【拓扑排序】有向无环图、定点活动图、拓扑排序简介

Ⅰ. 有向无环图（DAG图）

​ DAG 图全称为 Directed Acyclic Graph，就是一个有向 + 无环的图。

​ DAG 图是相较于有向树的更特殊的图。它的作用挺重要的，比如：检查一个图是否有环，可以通过遍历+标记的方式进行检查，若某个顶点的弧指向了另一个已经遍历过的顶点，则该图必定含有环。

Ⅱ. AOV网 – 顶点活动图

​ 定义：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，称为 AOV网（Activity On Vertex Network），AOV 网中的弧表示活动之间的某种约束关系。

​ 此外 AOV 网中 不存在回路（即有向无环图），如下图所示：

Ⅲ. 拓扑排序

​ 其实拓扑排序非常的简单，一些书上的概念说的比较复杂，我们只需要记住，拓扑排序就是 找到 AOV 网中活动的先后执行顺序，所以拓扑排序的结果不是唯一的，因为一些活动是可以并行的。

​ 比如将上面途中的炒肉顺序，按照先后次序可以得到下面的一种情况：

​ 并且 拓扑排序不能出现环，因为其实现原理中如果出现了环的话，就无法得出一个序列了，所以拓扑排序的应用之一就是用来 判断图中是否存在环！

Ⅳ. 实现拓扑排序

可以看到其实拓扑排序并不难，无非就是借助队列和 BFS 来完成！下面是实现的步骤：

  1. 初始化：
    • 把所有入度为 0 的节点加入到队列中
  2. 当队列不为空的时候：
    1. 拿出队头节点，加入到最终结果中。
    2. 删除与该元素相连的边。
    3. 进行判断：
      • 判断 与删除边相连的点，是否入度变成了 0，如果为 0 的话则将其加入到队列中。

但此时有一个问题，就是我们需要 建图，并且需要知道每个节点的入度，所以我们有两种方式来建图：

  1. 看稠密度（即看数据量大小）
    • 邻接矩阵
    • 邻接表
  2. 根据算法流程，灵活建图

​ 一般来说邻接矩阵比较简单，我们这里主要来讲一下邻接表的建图方式！邻接表的建图方式不一定就要用链表结构来实现，也是可以使用 STL 中一些容器比如说 vector 或者 unordered_map 来实现，如下所示：

  • vector<vector<T>>
  • unordered_map<T, vector<V>>

​ 可以看到这两种方式其实和链表结构的思想是差不多的，并且使用哈希表来作为邻接表的建图方式是更加灵活的，因为它两个参数的类型是可以不同的！所以后面 我们大多都是采用哈希表来建立邻接表！

​ 而至于节点的入度的话，我们可以单独 用一个 vector 来存放入度，然后只需要在 建图的过程中将指向当前节点的次数累加一下 即可！

​ 具体如何建图以及求入度，可以看后面具体的ti’mu

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-03-11，如有侵权请联系 cloudcommunity@tencent 删除遍历队列链表排序容器

本文标签： 拓扑排序有向无环图定点活动图拓扑排序简介

版权声明：本文标题：【拓扑排序】有向无环图、定点活动图、拓扑排序简介 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://it.en369.cn/jiaocheng/1748341537a2288057.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。