c++ - BFS 实现

Question

我最近在解决一个 bfs 问题，其中每个节点都是数组元素的不同排列。但是我无法想出一个合适的数据结构来跟踪扩展树中的访问节点。通常，节点是不同的字符串，因此我们可以只使用映射将节点标记为已访问，但在上述情况下我应该使用什么 DS？

Answer 1

考虑以下伪代码:

type Node;  // information pertaining to a node
type Path;  // an ordered list of nodes
type Area;  // an area containing linked neighboring nodes
type Queue; // a FIFO queue structure

function Traverse(Area a, Node start, Node end) returns Path:
    Queue q;
    Node n;
                        // traverse backwards, from finish to start
    q.push(end);        // add initial node to queue
    end.parent = end;   // set first node's parent to itself

    while (not q.empty()):
        n = q.pop();    // remove first element

        if (n == start) // if element is the final element, we're done
            break;

        for (Node neighbor in a.neighbors(n)): // for each neighboring node
            if (neighbor.parent != Null):      // if already visited, skip
                continue;
            neighbor.parent = n;               // otherwise, visit 
            q.push(neighbor);                  // then add to queue

    Path p;             // prepare to build path from visited list

    for (Node previous = Null, current = n;
              previous != current;
              previous = current, current = current.parent):
        p.add(current); // for each node from start to end, add node to p
                        // Note that the first node's parent is itself
                        // thus dissatisfying the loop condition
    return p;

“访问列表”存储为节点的父节点。将其编码为 C++，您可能会将大部分节点作为引用或指针处理，因为该伪代码依赖于引用行为。

您从一个区域开始，它是节点的一个字段。该区域知道每个节点相对于其他节点的位置。您从一个特定节点(“开始”节点)开始，并将其插入队列。

遍历区域就像从区域中获取相邻节点列表一样简单，如果它们已经被访问过则跳过它们，设置它们的父节点并将它们添加到队列中，否则。当从队列中移除的节点等于目标节点时，遍历结束。当最初遇到节点时，您可以通过在邻居循环期间执行此检查来稍微加快算法速度。

注意:在开始遍历之前，您不需要在区域内生成每个可能的节点，Area 只需要在创建节点后跟踪它。这可能有助于您使用字符串或数组排列的情况:您可以将开始和结束节点插入区域，并且它可以动态生成和缓存邻居节点。您可以将它们存储为 vector ，可以根据它们的顺序和内容与 == 运算符比较它们是否相等。 See this example.

遍历向后而不是向前，因为它使重建路径更容易(而不是在结束节点结束，每个父节点在它之前，你在起始节点结束，每个父节点在它之后)

数据结构总结

Node 需要为 Area 跟踪足够的信息以唯一地标识它(通过数组索引或名称或其他东西)，以及父节点.父节点应该在遍历之前设置为 NULL 以避免奇怪的行为，因为遍历将忽略任何具有其父集的节点。这也跟踪访问状态:访问等同于 (parent != NULL)。这样做还可以让您不必跟踪队列中的整个路径，这将是计算密集型的。

Area 需要维护一个 Node 列表，并且需要一个邻居映射，或者哪些节点与哪些其他节点相邻的映射。有可能这个映射可以使用一个函数即时生成，而不是从表或一些更典型的方法中查找。它应该能够向调用者提供节点的邻居。拥有一个清除每个节点的父节点的辅助方法可能会有所帮助。

Path 基本上是一个列表类型，包含一个有序的节点列表。

Queue 是任何可用的 FIFO 队列。您可以使用链表来完成。

我喜欢语法突出显示在我的 Wuggythovasp++ 上的工作方式。