给定边列表的情况下如何进行DFS或BFS？

Question

仅给出边列表时如何执行DFS或BFS？

我知道在给定邻接列表或邻接矩阵时该怎么做，我也知道如何将边列表转换为邻接列表或邻接矩阵，但我想直接从边列表进行DFS或BFS。

[[1,2],[2,3],[3,4],[1,4],[1,5]]

Answer 1

假设这是一个有向图，您可以按源边对边列表进行排序，然后为每个源在列表中的起始或结束位置制作一个映射。 您可以有效地获得邻接列表表示，而无需重新创建整个数据结构。

可以使用像这样的就地计数排序在 O(N) 时间内完成排序：修改输入数组的计数排序实现，它可以方便地生成结束位置的映射作为副作用。

Answer 2

如果您知道节点（n），则使用边列表创建邻接列表。即 O(n)。然后进行DFS，即O(V+E)。

拥有正确的数据结构会带来不同。