algorithm - 决定有向图是否具有唯一拓扑排序的dfs算法

Question

我正在尝试构建一个使用 DFS 的算法，以确定给定的有向图是否具有唯一的拓扑排序。
我解决这个问题的方法是只有一个特定的图有一个独特的拓扑排序。该图是一个链状图，其中所有顶点都在一条线上相互连接。我的困境是如何做一个高效的 DFS 算法，以及我到底应该检查什么。

Answer 1

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

所以，你运行 DFS 并且你需要检查你从起始顶点经过的最长路径的长度是否为 |V|，然后你就有了唯一的拓扑顺序。正如 MattTimmermans 指出的那样，这种图可以简化为“链图”。