你如何使用stl迭代器和队列来实现图的广度优先遍历？

Question

虽然我从概念上理解了 BFS，但我还没有掌握如何使用迭代器和队列来实现 BFS。如果有人能告诉我如何在我的代码中正确使用迭代器，我将不胜感激。谢谢。

我什至不确定迭代器在这里是否是个好主意，我也尝试学习自动类型但我不确定如何使用它。

#ifndef GRAPH_H
#define GRAPH_H
#include<vector>
#include<iostream>
using namespace std;

struct vertex;

struct adjVertex{
    vertex *v;
};

struct vertex{

    string name;
    bool visited = false;
    int distance = 0;
    vector<adjVertex> adj;
};

class Graph
{
    public:
        void addEdge(string v1, string v2);
        void addVertex(string name);
        void displayEdges();
        void breadthFirstTraverse(string sourceVertex);
        int getConnectedBuildings();


    private:
        vector<vertex*> vertices;
};

#endif // GRAPH_H

void Graph::breadthFirstTraverse(string sourceVertex){
    
    //first initialize everything as not found
    for(int i = 0; i < vertices.size(); i++)
    {
        vertices[i]->visited = false;
    }

    //pointer to sourceVertex
    vertex *vStart;

    for(int i=0; i < vertices.size(); i++)
    {
        if(vertices[i]->name == sourceVertex){
            vStart = vertices[i];
            cout << "Starting vertex (root): " << vStart->name << " -> " << endl;
        }
    }
    queue<vertex*> q;
    vStart->visited = true;
    q.push(vStart);
    vertex *n;
    vector<int>:: iterator i;
    
    while(!q.empty()){
        n = q.front();

        q.pop();

        for(i = n->adj.begin(); i != n->adj.end(); ++i){ // error: no viable overloaded '='

            cout << n->adj[*i].v->name <<"(" << n->adj[*i].v->distance << ")" << " ";

            if(!n->adj[*i].v->visited){
                n->adj[*i].v->visited = true;
                q.push(*i); //no matching member function for call to 'push'
            }
        }
    }
}

注意：我在评论中解决了自己的问题。

Answer 1

您的第一条错误信息：

error: no viable overloaded '='

这与以下内容有关：

vector<int>:: iterator i;
for(i = n->adj.begin(); i != n->adj.end(); ++i) {

注意n->adj.begin()的类型是vector<adjVertex>::iterator。但是，变量 i 的类型是 vector<int>::iterator。编译器错误中的内容比您显示的要多得多。这样就可以完美地解释问题了。

这应该可以修复错误：

for(vector<adjVertex>::iterator i = n->adj.begin(); i != n->adj.end(); ++i) {

既然你问的是auto，那也是可以接受的：

for(auto i = n->adj.begin(); i != n->adj.end(); ++i) {

在这种情况下，i 的类型将为 vector<adjVertex>::iterator。

第二个错误相关：

no matching member function for call to 'push'

这是为了这个：

q.push(*i);

这里q的类型是queue<vertex*>，*i的类型是int。如果你应用我上面的修复，那么 *i 的类型将是 adjVertex 这将产生同样的问题。所以，你需要：

q.push(i->v);

回到第一个错误，有一种更现代的迭代方式（C++11 起），使用 range-based 循环:

for (auto& elem : n->adj) {

上面，这将遍历您的 adj 向量，让您通过值 elem 访问它的元素，该值将是 adjVertex& 类型。因此，您可以使用 elem.v.

访问该元素中的 vertex*

Answer 2

我对我的代码做了细微的修改以修复它。我没有使用迭代器（for 循环中的 int 变量很好），我不需要像这样取消引用

n->adj[*i].v->name

这是最终起作用的

void getConnectedComponents(string buildingName, vertex *& node){
    //pointer to sourceVertex
    vertex *vStart;
    vStart = node;

    queue<vertex*> q; 
    
    
    vStart->visited = true;
    q.push(vStart); 
    vertex *n; //pointer to elements in queue
    while(!q.empty()){
       
        n = q.front();
       
        q.pop();
        
        for(int i = 0; i  < n->adj.size(); i++){
               if(!n->adj[i].v->visited){
                 
                   //cout << n->adj[i].v->name <<"(" << n->adj[i].v->distance << ")" << " ";
               
                n->adj[i].v->visited = true;
                q.push(n->adj[i].v);
               }
        }
    }
    cout << endl;
}

你如何使用stl迭代器和队列来实现图的广度优先遍历？

How do you use stl iterator and a queue to implement a breadth first traversal of a graph?

c++

stl

graph

breadth-first-search

data-structures