实验十一 拓扑排序

实验十一 拓扑排序

实验目的和要求

  1. 掌握拓扑排序的方法

实验环境

  1. Visual Studio 2017 Community
  2. Windows 10 Pro

实验内容

  1. 输出一个有向无环图的全部拓扑排序序列

实验过程

任务一

设计

下面讨论拓扑排序方法的实现。

  1. 由于求解方法中涉及“入度”,因而需要保存各顶点的入度,为此,不妨采用一个入度数组 ind。为简便起见,假设 ind 中各元素值已经设置好了。
  2. 为实现操作拓扑排序 1 中的“找出入度为 0 的顶点”的操作,有两种典型的方法:
  • 在 ind 数组中搜索。这种方法不理想,一方面要花费较多的搜索时间,另方面还要区分顶点是否已经被输出。
  • 将入度为 0 并且未输出的顶点放在一个结构中,需要时就直接从中取出,而不必搜索,从而节省搜索时间。这样,当出现新的入度为 0 的顶点时,就需要将其存放进来。
  1. 操作拓扑排序 2 中“删除”顶点的实现。有些初学者看到这一操作描述便想着如何在在储结构上实现删除顶点的操作,这不方便,同时也没有必要。完整分析拓扑排序的方法可发现,确定一个顶点是否能被输出的条件是其人度是否为 0,“删除顶点”的目的并非是真的要将其去掉,其真实目的是为了使其后继顶点少一个前驱(即入度减 1)。由此可知,删除顶点的实现可通过将其所有后继顶点的入度减 1 来实现。

编码实现

编码实现,通过 C++ 来实现以上分析过程。

测试

以下是测试结果:

压缩/解压效果图

实验收获

通过本次实验掌握了拓扑排序的方法。本次实验实现拓扑排序的过程中借鉴了 DFS 的思想,因此,同时也对 DFS 有了更深的理解。