图论进阶：如何实现有向无环图的拓扑排序算法？

本文共计3573个文字，预计阅读时间需要15分钟。

1. 前言：存在无环图，字面而言，指图中不存在环（回路），意味着从任意一点出发，发展都无法回到起点本身。有向无环图（DAG）也称其为DAG。有向无环图可用于描述节点间的关系。

1. 前言

有向无环图，字面而言，指图中不存在环(回路)，意味着从任一顶点出发都不可能回到顶点本身。有向无环图也称为 DAG（Directed Acycline Graph）。

有向无环图可用来描述顶点之间的依赖关系，依赖这个概念在面向对象编程中经常出现。如使用B组件时，需要先有A组件，或说B组件依赖A组件，通俗言之，有A才有B。可用如下图描述。

在面向对象编程的场景中，组件之间的依赖关系链中不能出现环。如现有 3 个组件，C依赖B，B依赖于A。正确的图解应该如下图。

如果在 A和C添加依赖，则会出现环，在面向对象中，称此种情况为循坏依赖，显然，会导致死锁，从而让程序崩溃。如下图所示，如果图结构是用来描述面向对象中组件之间的依赖关系，则会出现逻辑悖论：

• 图示有C才有A、有 A才有B，有B才有 C。
• 这里就出现了先有鸡还是先有蛋的悖论问题。因为图中出现了 A需要依赖自己的矛盾。

下文将更深入讲解有向无环图的特点及应用。