algorithm - 寻找有向图根的算法

Question

我可以很容易地通过查看它来判断哪个节点是有向图的根，但是如果我想使用一种算法来找到一个，我应该从 DFS 开始吗？

标签： algorithmdirected-graph

Answer 1

有向图没有根，除非它是树。如果您想查找没有传入边的有向图的顶点，您可以运行 DFS 并跟踪如何发现顶点。如果一个顶点仅因为它是从顶点列表中被选择而被发现并且从未被边重新发现，那么它没有传入边。

另一种思考方式是使用 DFS 来检查图的所有边。任何从未出现在边缘接收端的顶点都将是“根”。