調試BFS樹travesal算法

我一個人在這個項目上工作，可以使用另一組眼睛來看看這個，看看我做錯了什麼。第一個循環無限運行。調試BFS樹travesal算法

public void bfs(String start) 
    { 
     //Initial Case 
     add_queue.add(start); 
     graph.visit(start); 

     Iterator<String> neighbors; 
     String neighbor; 

     while(!add_queue.empty()) 
     { 
      neighbors = graph.neighbors(start); 
      neighbor = neighbors.next(); 
      graph.visit(neighbor); 
      add_queue.add(neighbor); 
      while(neighbors.hasNext()) 
      { 
       neighbor = neighbors.next(); 
       if(!graph.isVisited(neighbor)) //If vertex is not visited it is new and is added to the queue 
       { 
        add_queue.add(neighbor); 
        graph.visit(neighbor); 
       } 

      } 
      start = add_queue.remove(); 
      remove_queue.add(start); //transfers vertex from add_queue to remove queue so that the order that the vertices were traversed is stored in memory  
     } 
    }

來源

2010-06-04 Nathan

我認爲傑克的建議修正了它。堆棧中至少有一個頂點。我拿出neighbors.next（）賦值行，並在第一個循環的開始處添加和訪問行，它工作。感謝所有及時有效的幫助。 – Nathan 2010-06-04 20:53:01

我想你要添加的鄰居的第一個頂點沒有，如果它已經訪問過檢查..在這裏：

neighbor = neighbors.next(); <- you get first 
graph.visit(neighbor); <- you visit 
add_queue.add(neighbor); <- you add it without any check 
while(neighbors.hasNext()) 
{ 
    neighbor = neighbors.next(); 
    if(!graph.isVisited(neighbor)) <- you do check for the others 
    { 
    add_queue.add(neighbor); 
    graph.visit(neighbor); 
    } 
}

這意味着你將永遠不會空該隊列..因爲它的大小爲1開始，那麼你在每次迭代中刪除1個元素，但是你至少添加了1個元素（你永遠不會添加任何一個元素）。

來源

2010-06-04 18:49:47 Jack

什麼add_queue的的empty()定義是什麼？

這可能是一個壞的命名問題，但它聽起來像empty()做的東西，而不是隻檢查是否是空的（這將是大概叫isEmpty()）。

另外，它看起來總是在每個外部循環中添加至少1個add_queue（在內部while之前），但每次迭代只從add_queue中刪除一個項目。

來源

2010-06-04 18:49:10 Mike

幾個地方調查：

檢查，以確保graph.isVisited()當一個節點已經通過graph.visit()訪問實際上是承認。
是graph.neighbor(start)真的回到開始的鄰居嗎？而不包括在此列表中開始？

來源

2010-06-04 18:50:20

您的代碼有點不清楚。 graph.neighbors究竟返回什麼？

一般來說做一個BFS你想把當前節點的子加到隊列中，而不是它的鄰居。由於它全部進入隊列，這將確保您以正確的順序訪問樹中的每個節點。假設它是一棵樹而不是一般圖，這也將確保您不會多次訪問一個節點，從而允許您將支票移除到isVisited。

因此，將下一個節點從隊列中取出，將所有子節點添加到隊列中，訪問節點並重復，直到隊列爲空。

來源

2010-06-04 18:54:34 Donnie

Donnie，graph.neighbors（string）返回指定頂點的鄰居的迭代器。不過，我很抱歉，這是一張圖表。「樹遍歷」在我看來是錯誤的。 – Nathan 2010-06-04 19:32:23

調試BFS樹travesal算法

回答

相關問題