计算广度优先搜索中遍历的边数？

这是我的bfs算法。 我想存储遍历在字段边缘的边数，但我无法确定将变量放在哪里为每个边添加一个。 我总是得到太长的答案，所以我认为这比简单地增加边缘更难。

应该注意的是，这应该仅计算沿真实路径的边缘，而不是额外的边缘。

public int distance(Vertex x, Vertex y){ Queue search = new LinkedList(); search.add(x); x.visited = true; while(!search.isEmpty()){ Vertex t = search.poll(); if(t == y){ return edges; } for(Vertex n: t.neighbours){ if(!n.visited){ n.visited = true; search.add(n); } } System.out.println(search + " " + t); } return edges; } 

任何和所有的帮助表示赞赏。 如果您需要更多课程/方法，请告诉我

编辑

 import java.util.ArrayList; public class Vertex { public static char currentID = 'a'; protected ArrayList neighbours; protected char id; protected boolean visited = false; protected Vertex cameFrom = null; public Vertex(){ neighbours = new ArrayList(); id = currentID; currentID++; Graph.all.add(this); } public void addNeighbour(Vertex x){ int a; while(x == this){ a = (int) (Math.random()*(Graph.all.size())); x = Graph.all.get(a); } if(!(neighbours.contains(x))){ neighbours.add(x); x.addNeighbour(this); //System.out.println(this + " Linking to " + x); } } public void printNeighbours(){ System.out.println("The neighbours of: " + id + " are: " + neighbours); } public String toString(){ return id + ""; } } 

Answer 1

在Vertex类中，创建一个Vertex cameFrom字段，您将其设置为指向访问该节点时来自的Vertex 。 您甚至可以用此替换您的boolean visited字段（如果它为null ，则尚未访问Vertex ）。

然后，当你找到Vertex y只需按照指针返回Vertex x计算你走的步数。

如果您不想更改Vertex类，则只需在搜索期间保留Map ，它将存储从您正在访问的顶点到您来自的顶点的映射。 当你走到尽头时，你可以以同样的方式沿着开头的路径前进。

---

沿着这些方向的东西也许：

  public int distance(Vertex x, Vertex y){ Queue search = new LinkedList(); search.add(x); while(!search.isEmpty()){ Vertex t = search.poll(); if(t == y){ return pathLength( t ); } for(Vertex n: t.neighbours){ if(n.cameFrom == null || n != x){ n.cameFrom = t; search.add(n); } } System.out.println(search + " " + t); } return -1; } public int pathLength( Vertex v ) { int path = 0; while ( v.cameFrom != null ) { v = v.cameFrom; path++; } return path; } 

Answer 2

在此示例中，边数仅仅是search的大小。 队列。

编辑：

一种可能的解决方案是逐层进行。 让我们说你要求Vertex A，F之间的距离

图表看起来像：

 A |\ BC | D |\ EF 

首先计算A和B之间的距离C（这很容易，因为B和C是A的直接邻居。然后计算A和D之间的距离（这很容易，因为D是B的直接邻居，然后是A和E， F.将距离存储在A顶点节点中。现在，在运行BFS并确定搜索结果后，您可以简单地询问距离。请查看此可视图。