上篇文章介绍了什么是拓扑排序以及拓扑排序的应用场景，还是老规矩，介绍完基本概念，我们接着通过数据结构和算法来实现它，拓扑排序的基本实现思路如下：
在 AOV 网中，找到一个入度为 0 的顶点，然后删除此顶点，并删除以此顶点为起点的弧，重复此步骤，直到输出所有顶点，或者 AOV 网中不存在入度为 0 的顶点为止。
和最小生成树和最短路径一样，我们还是通过邻接表来定义一个 AOV 网，考虑到始终需要查找入度为 0 的顶点，我们在原来的顶点数据结构基础上，新增一个入度域 in，用来表示入度值：
/**
* 顶点
* Class VNode
*/
class VNode extends Node
{
public $in; // 入度
public function __construct($data, $in = 0)
{
$this->in = $in;
parent::__construct($data);
}
}
此外拓扑排序针对的是有向图，而我们之前实现最小生成树和最短路径的时候，都是基于无向图，所以我们还要编写一个新的继承自 EdgeWeightedGraph 的子类：
class DirectedWeightedGraph extends EdgeWeightedGraph
{
// 添加边
public function addEdge($s, $t, $weight)
{
$etNode = new ENode($t, $weight);
$this->adj[$s]->insertENode($etNode);
$this->edges[] = new Edge($s, $t, $weight);
// 将指向顶点入度值加1
$vNode = $this->getVertex($t);
$vNode->in += 1;
}
/**
* @param $position
* @return bool|VNode
*/
public function getVertex($position)
{
$vertex = $this->adj[$position]->get(0);
return $vertex;
}
}
我们在表示有向图的子类 DirectedWeightedGraph 中重写了 addEdge 方法，因为有向图的方向是固定的，需要和无向图区分开来，另外，在新增弧的时候，还为弧指向的顶点更新了入度值。
> 注：记得将父类 EdgeWeightedGraph 中的所有属性可见性调整为 protected，以便在子类中可以访问。
做了以上准备工作后，接下来，我们在子类 DirectedWeightedGraph 中编写拓扑排序实现方法 TopologicalSort：
public function TopologicalSort()
{
$stack = []; // 存放入度为零的顶点（以栈的方式实现）
$count = 0; // 统计输出顶点数
$sorted = []; // 存储拓扑排序结果
foreach ($this->vData as $pos => $data) {
$vertex = $this->getVertex($pos);
if ($vertex && $vertex->in == 0) {
$stack[] = $pos;
}
}
while ($stack) {
$start = array_pop($stack); // 开始顶点
$vertex = $this->getVertex($start);
if (!in_array($vertex->data, $sorted)) {
$sorted[$start] = $vertex->data;
}
$count++;
$eNode = $vertex->next;
while ($eNode) {
$k = $eNode->data; // 与起点相邻的顶点
$oVertex = $this->getVertex($k);
if (!(--$oVertex->in)) { // 「删除」该弧，将对应顶点入度值减1
$stack[] = $k; // 若为0则入栈，以便下次循环输出
}
$eNode = $eNode->next;
}
}
if ($count < $this->vNum) {
return false; // 存在环
}
return $sorted;
}
实现逻辑很简单，分析整个算法，对于一个有 n 个顶点和 e 条边的有向图来说，扫描顶点表查找入度为 0 的顶点的时间复杂度为 O(n)，而之后的 while 循环中，每个顶点进一次栈，出一次栈，总共执行此次数为e，所以整个算法的时间复杂度为 O(n+e)。
测试代码可以参照之前编写的示例，这里就不演示了。