PHP怎样实现拓扑排序算法_PHP实现拓扑排序算法方法【算法】

在PHP开发中，如果需要对有向无环图（DAG）的节点进行线性排序，使得每条有向边 u → v 中，u 始终排在 v 前面，那就要用到拓扑排序。说白了，就是给一堆有依赖关系的任务排个先后顺序。下面介绍三种常用的实现方法，各有各的适用场景。

一、基于入度统计的Kahn算法

这个思路很直观：不断把那些“没人依赖它”的节点（入度为0）拎出来，然后更新它邻居的依赖计数。适合用邻接表或邻接矩阵表示图，时间复杂度O(V+E)，效率没得说。

具体步骤：

1、先构建图的邻接表，同时统计每个节点的入度。

2、把入度为0的所有节点扔进队列（比如PHP的SplQueue）。

3、队列不空就循环：取出队首节点，加入结果数组。

4、遍历该节点的所有邻接节点，把它们的入度减1；如果某个邻接节点入度变成0，也把它入队。

5、循环结束后，如果结果数组的长度小于图中节点总数，说明图中存在环，没法完成拓扑排序。

二、基于深度优先搜索的DFS递归法

这个方法利用DFS的回溯特性：先递归访问所有后继，等后继都处理完了，再把当前节点压入结果栈。最后把栈反转一下，就是拓扑序。需要维护一个访问状态数组，用来识别环和已访问节点。

步骤拆解：

1、给每个节点定义三个状态：未访问（0）、访问中（1）、已访问（2）。

2、对每个未访问的节点调用DFS函数。

3、DFS里，先把当前节点标记为“访问中”，然后递归访问所有未访问的邻接节点。

4、如果递归过程中遇到状态为“访问中”的节点，说明检测到环，拓扑排序失败。

5、当前节点的所有邻接点都处理完后，把它改为“已访问”，并压入结果栈。

三、使用PHP内置数据结构优化的迭代DFS法

递归写法虽然简洁，但遇到深度很大的图容易栈溢出。这时候可以用显式栈来模拟DFS过程，同时维护节点状态和路径记录，避免递归调用过深。

实现要点：

1、为每个节点初始化状态数组，外加一个布尔标记数组记录当前DFS路径。

2、用SplStack作为显式栈，初始压入任意未访问节点以及它的路径深度信息。

3、每次弹出栈顶元素，检查状态：如果它是“访问中”且路径标记为true，那就发现环，立即终止。

4、如果是未访问状态，就标记为“访问中”，然后把所有邻接节点依次压栈。

5、等到该节点的所有邻接点都处理完了，再把它改为“已访问”，并加入结果列表尾部。