使用相鄰列表實現的bfs調試

我正在嘗試使用相鄰列表調試bfs算法。它會正確打印到某個點然後進入無限循環。我做了一些打印輸出，並注意到它最終遍歷了圖的前兩個節點。我不知道在我的代碼導致這個問題。這是我得到的分配，這是我最後的手段。如果任何人都能指出我的正確方向，那麼問題可能會有多大幫助。使用相鄰列表實現的bfs調試

void bfsList(linkedList adjList[], int visit[], int j){ 
    Queue queue(24); 
    if (visit[j] == 0){ 
     cout << j+1 << endl; 
     visit[j] = 1; 
     queue.enqueue(j); 
     while(!queue.isEmpty()){ 
      int k = queue.dequeue(); 
      //queue.print(); 
      for(int i=0;i<adjList[k].len();i++){ 
       if (visit[adjList[k].elementAt(i)-1]==0){ 
        cout << adjList[k].elementAt(i) << endl; 
        visit[adjList[k].elementAt(i)-1] = 1; 
       } 
       if (!queue.isFull()){ 
        queue.enqueue(adjList[k].elementAt(i)-1); 
       } 
      } 
     } 
    } 
}

來源

2014-02-27 user2079902

我也檢查了鄰接表。列表沒有什麼問題，因爲它與我用於執行深度優先搜索的方法相同。該圖從csv文件加載。 – user2079902

只有在未訪問節點時排隊。

if (visit[adjList[k].elementAt(i)-1]==0){ 
    cout << adjList[k].elementAt(i) << endl; 
    visit[adjList[k].elementAt(i)-1] = 1; 

    if (!queue.isFull()){ 
    queue.enqueue(adjList[k].elementAt(i)-1); 
    } 

}

來源

2014-02-27 17:06:15

謝謝你們兩位，我做了你所說的，但我更新了排隊後的訪問數組 – user2079902

queue.enqueue(adjList[k].elementAt(i)-1);

需要依賴，節點是否已被訪問。未經測試：

if (!queue.isFull() && !visit[adjList[k].elementAt(i)-1]){ 
       queue.enqueue(adjList[k].elementAt(i)-1); 
      }

來源

2014-02-27 17:02:21 Karamba

我在發帖前試過，它只打印出第一個節點，然後是第二個節點。我對bfs的理解是，雖然它可能訪問節點。它需要被排隊以獲得它們的相鄰節點。所以如果我在那裏進行檢查，它將在打印第一個節點的鄰居節點後停止。 – user2079902

謝謝你們，我做了你所說的，但我更新了排隊後的訪問陣列 – user2079902

使用相鄰列表實現的bfs調試

回答

相關問題