2

我正在研究一个图形库，该库需要确定两个节点是否连接，如果连接，它们之间的分离程度是多少，即从源节点到达目标节点所需的节点数。

由于它是一个非加权图，bfs 给出了最短路径。但是如何在到达目标节点之前跟踪发现的节点数量。

一个在发现新节点时递增的简单计数器将给出错误答案，因为它可能包括甚至不在路径中的节点。

另一种方法是将其视为均匀加权边的加权图并使用 Djkastra 的最短路径算法。

但我只想用 bfs 来管理它。

怎么做 ？

4

3 回答 3

2

在 BFS 期间，让每个节点存储一个指向其前驱节点的指针（图中的节点首先沿着其边发现该节点）。然后，一旦你运行了 BFS，你就可以从目标节点到源节点重复地跟随这个指针。如果您计算这需要多少步，您将获得从目标节点到源节点的距离。

或者，如果您需要重复确定节点之间的距离，您可能需要使用 Floyd-Warshall 全对最短路径算法，如果预先计算，您可以立即读取任何节点对之间的距离。

希望这可以帮助！

于 2013-01-14T17:52:14.167 回答
2

我不明白为什么一个简单的计数器不起作用。在这种情况下，广度优先搜索肯定会为您提供最短路径。因此，您要做的是将一个属性附加到每个名为“count”的节点。现在，当您遇到尚未访问的节点时，您可以使用当前计数填充“计数”属性并继续前进。

如果稍后，您回到节点，您应该通过填充的计数属性知道它已经被访问过。

编辑：要在这里扩展我的答案，您必须维护一个变量，该变量将在您浏览图表时跟踪与起始节点的分离程度。对于您加载到队列中的每组新子项，请确保增加该变量中的值。

于 2013-01-14T17:53:11.220 回答
0

如果您只想知道距离（如果距离太大，可能会切断搜索），并且所有边的权重相同（即 1）：

伪代码：

Let Token := a new node object which is different from every node in the graph.
Let Distance := 0
Let Queue := an empty queue of nodes
Push Start node and Token onto Queue 

(Breadth-first-search):
While Queue is not empty:
    If the head of Queue is Target node:
        return Distance
    If the head of Queue is Token:
        Increment Distance
        Push Token onto back of the Queue
    If the head of Queue has not yet been seen:
        Mark the head of the Queue as seen
        Push all neighbours of the head of the Queue onto the back of Queue
    Pop the head of Queue
(Did not find target)
于 2013-01-14T18:31:06.210 回答