Dfs算法，决定有向图是否具有唯一的拓扑排序 [英] Dfs algorithm that decides if a directed graph has a unique topological sort

问题描述

我试图构造一个使用DFS的算法来决定给定的有向图是否具有唯一的拓扑排序。

我对这个问题的解决方法是只有一个特定的图形具有唯一的拓扑排序。而且这个图形是一个像图一样的链，其中所有的顶点在一条线上相互连接。
我的两难困境是如何做一个有效的DFS算法，以及我应该检查什么。

解决方案

From here

<一个有向图有一个唯一的拓扑排序当且仅当在拓扑顺序中每对连续顶点之间存在有向边（即该有向图有一个哈密尔顿路径）。

因此，您运行DFS，并且您需要检查从起始顶点开始走的最长路径是否具有长度| V |，那么您具有唯一的拓扑顺序。正如MattTimmermans指出的那样，这样的图可以简化为链式图。

I'm trying to struct an algorithm that uses DFS for the purpose of deciding whether a given directed graph has unique topological sort or not.
My approach to the problem is that only a specific graph has a unique topological sort. And that graph is a chain like graph, in which all of the vertices are connected to each other in one line. My dilemma is how to do an efficient DFS algorithm, and what exactly should I check.

解决方案

From here

a digraph has a unique topological ordering if and only if there is a directed edge between each pair of consecutive vertices in the topological order (i.e., the digraph has a Hamiltonian path).

So, you run DFS and you need to check that the longest path you went from start vertex has length |V|, then you have unique topological order. As MattTimmermans pointed out such graph can be reduced to a "chain graph".

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