计算连通图中两个节点之间的分离程度

3 回答

• 0

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

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

  希望这可以帮助！

  回复于 2024-05-14T15:35:54+08:00
• 2

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

  如果稍后再返回节点，则应通过填充的count属性知道它已被访问过 .

  EDIT ：要在此处扩展我的答案，您在浏览图表时会跟踪起始节点的分离程度 . 对于加载到队列中的每个新子集，请确保增加该变量中的值 .

  回复于 2024-05-14T15:35:54+08:00
• 2

  如果您只想知道距离（如果距离太大，可能会切断搜索），并且所有边都具有相同的权重（即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)
  

  回复于 2024-05-14T15:35:54+08:00