使用STL中的鄰接列表的BFS

我正在嘗試編寫一個使用STL在C++中實現BFS的程序。我使用嵌套向量表示鄰接列表，其中向量中的每個單元格都包含連接到特定頂點的節點列表。使用STL中的鄰接列表的BFS

while(myQ.size()!=0) 
{ 
    int j=myQ.front(); 
    myQ.pop(); 
    int len=((sizeof(adjList[j]))/(sizeof(*adjList[j]))); 
    for (int i=0;i<len;i++) 
    { 
     if (arr[adjList[j][i]]==0) 
     { 
      myQ.push(adjList[j][i]); 
      arr[adjList[j][i]]=1; 
      dist(v)=dist(w)+1; 
     } 
    } 

}

myQ是我正在使用的隊列來保留其邊緣我將探索圖的節點。在符號中，adjList [j]表示指向列表的向量，adjList [j] [i]表示該列表中的特定節點。我正在存儲是否通過在數組arr中輸入1來探索特定節點。此外DIST（V）= DIST（W）+1是不是代碼的一部分，但我想知道我可以在正確的語法寫在我的v是新的頂點和w是舊的，其發現v即W = myQ.front（）。

來源

2014-07-08 arrhhh

如果我明白你的問題，那麼你想要的數據結構來存儲圖節點的距離。

這可以很容易地使用地圖。

使用此：

typedef std::map <GraphNode*, int> NodeDist; 
NodeDist node_dist;

替換DIST（V）= DIST（W）1;與：

NodeDist::iterator fi = node_dist.find (w); 
if (fi == node_dist.end()) 
{ 
    // Assuming 0 distance of node w. 
    node_dist[v] = 1; 
} 
else 
{ 
    int w_dist = (*fi).second; 
    node_dist[v] = w_dist + 1; 
}

請讓我，如果我誤解了你的問題或給定的解決方案不適合你。我們可以爲此努力。

來源

2014-07-09 03:02:18

使用STL中的鄰接列表的BFS

回答

相關問題