通过多分支图搜索并返回路径[C＃]

Question

在我的情况中，我有领土对象。每个地区都知道他们通过阵列连接的其他地区。这是说，领土的可视化因为它们将出现在地图上：

如果你绘制出图形上的联系，他们应该是这样的：

所以说我有一个单位驻扎在领土[b]，我想将其移动到领域[e]，我正在寻找一种方法来搜索这张图，并返回一个最终数组，代表我的单位在[b]区域必须达到的路径柯。在这种情况下，我会寻找它返回

[b, e]. 

如果我想从境内[a]去领土[f]那么它将返回：

[a, b, e, f]. 

我会爱的例子，但即使只是帖子指向我在正确的方向表示赞赏。提前致谢！ :)

Answer 1

您是否听说过广度优先搜索（BFS）？

基本上，你只需把你的初始领土，“一”，在你的榜样，为其他空队列Q

你需要的是布尔值数组与尽可能多的元素，你有领土的第二数据结构，在这种情况下9.它有助于记住我们已经检查过哪些区域。我们称之为V（用于“访问”）。它需要进行如下初始化：除了与初始平方对应的元素之外，所有元素都等于false。对于所有地区t，我们有V [t] = false，但V [a] =真，因为“a”已经在队列中。

您需要的第三个也是最后一个数据结构是一个存储父节点的数组（即我们来自哪个节点）。它也具有与您所在地区一样多的元素。我们称之为P（对于“父母”），并且每个元素最初指向自己，即对于P中的所有t，设置P [t] = t。

然后，它是非常简单的：

while Q is not empty: 
    t = front element in the queue (remove it also from Q) 
    if t = f we can break from while loop //because we have found the goal 
    for all neighbors s of t for which V[s] = false: 
     add s into the back of Q //we have never explored the territory s yet as V[s] = false 
     set V[s] = true //we do not have to visit s again in the future 

     //we found s because there is a connection from t to s 
     //therefore, we need to remember that in s we are coming from the node t 
     //to do this we simply set the parent of s to t: 
     P[s] = t 

你怎么看现在的解决方案？

只需检查f的父项，然后是父项，然后是父项，依此类推，直到找到开头。一旦你找到了一个以父母为自身的元素（记住，我们让他们最初指向自己），或者你也可以将它与a进行比较，你就会知道开始是什么。 基本上，你只需要一个空列表L，加˚F进去又

while f != a: 
    f = P[f] 
    add f into L 

注意，如果因为˚F永远等于一个不存在的路径，这显然是失败。 因此，这个：

while f != P[f]: 
    f = P[f] 
    add f into L 

是有点更好。它利用了这样一个事实，即最初所有领土都指向P.

如果你尝试这种在纸上用你上面的例子，那么你将最终 L = [F，E，B，A] 如果你简单地扭转这个列表中，那么你有你想要的东西。

我不知道C＃，所以我没有打扰使用C＃语法。我假设你知道用整数索引你的领域是最容易的，然后使用一个数组来访问它们。

你会很快意识到为什么这会起作用。这就是所谓的广度优先搜索，因为您首先只考虑领土“a”的邻居，通往他们的路径最短（只有一条边），只有一次处理完所有这些后，距离较远的领域才会出现在队列中从现在开始只有2条边）等等。这就是为什么我们使用队列执行此任务而不是堆栈。

此外，这是领土和边缘数量的线性因为您只需要查看每个领土和边缘（最多）一次（虽然从两个方向的边缘）。

我给你的算法基本上与https://en.wikipedia.org/wiki/Breadth-first_search一样，只添加了P数据结构来跟踪你来自哪里，能够找出所采取的路径。