c# - 从邻接信息列表中查找路径

Question

我在数据库中有以下形式的数据：

A -> B
C -> D
B -> C
F -> G
G -> J
X -> Z

这基本上意味着 A 到 B，C 到 D 等等。给定这些数据和一个节点（例如 C），我想构建找到 C 的完整路径，即 A -> B -> C -> D . 我试图通过使用一些字典和递归循环来做到这一点，但我不喜欢这种缓慢的解决方案，因为 db 中有很多数据。有什么更好的方法来解决这个问题？在算法和数据结构方面？任何想法或提示表示赞赏。

Answer 1

您基本上是在寻找DFS，但您需要做两次 - 每个方向一次。

首先在反向“图表”上做一个 DFS，从 C 开始。
在你的例子中，它会给你Path1 = C->B->A

接下来，再次从 C 对原始图执行 DFS。
在您的示例中，它将为您提供Path2= C->D

现在，通过反转Path1和连接Path2它，您将得到：

reverse(Path1)  + Path2 = A->B->C + C->D = A->B->C->D

---

澄清 - DFS 只是抽象，你实际上在做的是类似于（伪代码）的东西：

current <- C
list = []
while (current != null):
   list.addFirst(current)
   current <- u such that (u,current) is in the DataBase
current <- C
list.deleteLast() // last is C
while (current != null):
   list.addLast(current)
   current <- u such that (current,u) is in the DataBase

请注意，查找u这两种情况是一个简单的字典查找，第一个“目标”是键，第二个“源”是键。