确定有向图是否具有唯一的拓扑顺序？ [英] Determine whether a directed graph has a unique topological ordering?

问题描述

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

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).

这篇关于确定有向图是否具有唯一的拓扑顺序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！