algorithm - 给定起始顶点的图的子图

Question

我想得到给定起点的图的子图。连接到起始顶点的所有顶点都被视为应返回的子图的一部分。

我已经解决了这个需求，但很好奇是否有更有效的解决方案。我想出的解决方案是对图进行 DFS 并记录在集合 S 中遇到的每个顶点。然后，我简单地从原始图中提取所有连接到 S 中的顶点的边，然后我从中构建子图。原始图中的边存储在 C# 字典中，我认为它基本上是一个哈希。

DFS 和 BFS 不起作用，因为如果您有两个顶点都具有相同的子节点，则 BFS 或 DFS 将不会遍历这些边之一。因此，这种情况下的子图将包含所有正确的顶点，但会遗漏一些边对。

有没有比我想出的更好的解决方案？

Answer 1

我认为 BFS 遍历是最有效的算法。

如果您执行 BFS 并为每个节点排队 所有 邻居(即遍历附加到当前节点的所有边)并且仅在 当前节点 具有时中止遍历已经被访问过，你避免了你用“同一个 child ”/“遗漏的边缘”描述的问题。