确定有向图是否具有唯一的拓扑顺序？

本文介绍了确定有向图是否具有唯一的拓扑顺序？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在尝试为算法创建伪代码，该伪代码将能够确定有向图是否具有唯一的拓扑顺序。我已经为拓扑排序提出了以下伪代码，但是为了确定有向图是否具有唯一的拓扑次序，我必须添加或编辑什么？

I'm trying to create pseudo-code for an algorithm that will be able to determine whether a directed graph has a unique topological ordering. I've already come up with the following pseudo-code for a topological sort, but what would I have to add or edit in order to determine whether a digraph has a unique topological ordering?

Input: A graph G Output: A list L that contain the sorted vertices define an empty list L; create a stack Stack; push all vertices with no incoming edges into Stack; while Stack is not empty do v ← Stack.pop(); add v to the list L; for all the vertices w with an edge e from v to w do remove edge e from G; if w has no other incoming edges then push w into Stack; if G has edges left then return error (graph G can’t be topological ordered);  else return L;

推荐答案

没有特别的理由使用堆栈而不是其他种类的收藏。如果我们不确定地弹出元素，那么我们可以实现所有可能的拓扑顺序。因此，当且仅当每次我们弹出集合中包含一个元素时（除非结尾处为空），拓扑顺序才是唯一的。

There's no particular reason to use a stack as opposed to some other kind of collection. If we pop elements nondeterministically, then we can realize all possible topological orders. Thus, the topological order is unique if and only if the collection contains one element each time we pop (except when it's empty at the end).