計算廣度優先搜索中遍歷的邊數？

Question

這是我的bfs算法。我想存儲我在場邊中穿過的邊的數量，但我無法確定將變量放置在哪裏以便爲每個邊添加一個邊。我不斷得到答案太長，所以我認爲這比簡單地增加邊緣更困難。

應該指出，這應該只計算沿着真實路徑的邊緣，而不是額外的邊緣。

public int distance(Vertex x, Vertex y){ 
     Queue<Vertex> search = new LinkedList<Vertex>(); 
     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<Vertex> neighbours; 
    protected char id; 
    protected boolean visited = false; 
    protected Vertex cameFrom = null; 
    public Vertex(){ 
     neighbours = new ArrayList<Vertex>(); 
     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字段（如果它是nullVertex還沒有被訪問過）。

然後，當您發現Vertex y時，只需按照指針回到Vertex x即可計算出您走多遠的步驟。

如果您不想更改Vertex類，那麼只需在搜索期間保留Map<Vertex,Vertex>即可存儲從您訪問的頂點到您來自的頂點的映射。當你走到最後時，你可以用同樣的方式沿着路徑前進。

---

沿着也許這些東西線：

public int distance(Vertex x, Vertex y){ 
     Queue<Vertex> search = new LinkedList<Vertex>(); 
     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的大小。隊列。

編輯：

一種可能的解決方案是通過層做層。比方說，你要的頂點之間的距離，F

和圖形的樣子：

A 
|\ 
B C 
| 
D 
|\ 
E F 

首先計算，因爲B和C是近鄰這是很容易A和B，C之間的距離（然後計算A和D之間的距離（這很容易，因爲D是B的直接鄰居，然後是A和E，F。將距離存儲在A頂點節點中。現在，在您運行BFS並確定之後搜索結果，你可以簡單地問一下這個距離。看看this可視圖。