使用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

回答

相关问题