4

给定一个无向循环图，我想通过广度优先搜索或深度优先搜索找到所有可能的遍历。给出一个图作为邻接列表：

A-BC
B-A
C-ADE
D-C
E-C

所以来自根 A 的所有 BFS 路径都是：

{ABCDE,ABCED,ACBDE,ACBED}

对于 DFS：

{ABCDE,ABCED,ACDEB,ACEDB}

我将如何以一种有意义的方式在算法上生成这些遍历？我想可以生成字母的所有排列并检查它们的有效性，但这对我来说似乎是最后的手段。

任何帮助，将不胜感激。

4

2 回答 2

0

BFS 应该很简单：每个节点都有一定的深度可以找到它。在您的示例中，您在深度 0 处找到 A，在深度 1 处找到 B 和 C，在深度 2 处找到 E 和 D。在每个 BFS 路径中，您将拥有深度为 0 (A) 的元素作为第一个元素，然后是深度 1（B 和 C）的元素，然后是深度 2（E 和 D）的元素的任何排列，等等...如果您查看示例，您的 4 个 BFS 路径与该模式匹配。A 始终是第一个元素，然后是 BC 或 CB，然后是 DE 或 ED。您可以将其推广到具有更深深度的节点的图。要找到它，您只需要 1 个非常便宜的 Dijkstra 搜索。

在 DFS 中，您没有很好的深度分离，这使得 BFS 变得简单。我没有立即看到与上述算法一样高效的算法。您可以通过遍历图形和回溯来设置图形结构并构建路径。在某些情况下，这不是很有效，但对于您的应用程序来说可能就足够了。

于 2012-10-28T20:40:02.307 回答
0

除了您实际执行所有可能的 DFS 和 BFS 遍历的明显方式之外，您可以尝试这种方法：

步骤 1. 在从根 A 开始的 dfs 遍历中，像这样转换当前访问节点的邻接列表： 首先从列表中删除节点的父节点。其次生成调整列表中剩余节点的所有排列。

因此，如果您在来自节点 A 的节点 C，您将执行以下操作：

C -> ADE transform into C -> DE transform into C -> [DE, ED]

第 2 步。在第 1 步之后，您有以下转换后的 adj 列表：

A -> [CB, BC]
B -> []
C -> [DE, ED]
D -> []
E -> []

现在您从 (A,0) 开始启动处理，其中对中的第一项是遍历路径，第二项是索引。假设我们有两个队列。一个 BFS 队列和一个 DFS 队列。我们将这对放入两个队列中。

现在我们重复以下操作，首先是一个队列，直到它为空，然后是另一个队列。

我们将第一对从队列中弹出。我们得到 (A,0)。节点 A 映射到 [BC, CB]。所以我们生成了两条新路径（ACB,1）和（ABC,1）。将这些新路径放入队列中。

将其中的第一个从队列中取出以获得 (ACB,1)。索引为 1，因此我们查看路径字符串中的第二个字符。这是 C。节点 C 映射到 [DE, ED]。

  • 该路径的 BFS 子节点将是 (ACBDE,2) 和 (ACBED,2)，我们通过附加子置换获得。
  • 该路径的 DFS 子代将是 (ACDEB,2) 和 (ACEDB,2)，我们通过将C 之后的子排列插入到路径字符串中来获得它们。

我们根据我们正在处理的队列生成新路径，基于上述并将它们放入队列中。因此，如果我们正在处理 BFS 队列，我们​​将放入 (ACBDE,2) 和 (ACBED,2)。我们队列的内容现在是：(ABC,1)、(ACBDE,2)、(ACBED,2)。

我们从队列中弹出 (ABC,1)。生成 (ABC,2) 因为 B 没有孩子。并获取队列：(ACBDE,2), (ACBED,2), (ABC,2) 等等。在某些时候，我们最终会得到一堆索引不包含在路径中的对。例如，如果我们得到 (ACBED,5)，我们知道这是一条完成的路径。

于 2012-10-28T21:14:08.717 回答