Блог

хотя я концептуально понимаю BFS, я не понял, как использовать итератор и очередь для реализации BFS. Я был бы очень признателен, если бы кто-нибудь мог дать мне некоторое представление о том, как правильно использовать итератор в моем коде. Спасибо.

Я даже не уверен, что итератор здесь хорошая идея, я тоже пытался изучить тип auto, но я не уверен, как это использовать.

 #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'
            }
        }
    }
}

  

Примечание: я решил свой собственный вопрос в комментариях.

Ваше первое сообщение об ошибке:

ошибка: нет жизнеспособной перегруженной ‘=’

Это связано со следующим:

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

Обратите внимание, что тип n->adj.begin() is 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 .

Вторая ошибка связана:

нет соответствующей функции-члена для вызова ‘push’

Это для этого:

 q.push(*i);
  

Здесь тип q is queue<vertex*> и тип *i is int . Если вы примените мое исправление выше, то тип *i будет adjVertex таким, который приведет к той же проблеме. Итак, вам понадобится:

 q.push(i->v);
  

Возвращаясь к первой ошибке, существует более современный способ итерации (начиная с C 11), использующий цикл на основе диапазона:

 for (autoamp; elem : n->adj) {
  

Выше это будет повторяться по вашему adj вектору, предоставляя вам доступ к его элементам через значение elem , которое будет иметь тип adjVertexamp; . Таким образом, вы сможете получить доступ vertex* к этому элементу с elem.v помощью .

Я внес небольшие изменения в свой код, чтобы исправить это. Я не использовал итератор (переменная int в цикле for была в порядке), и мне не нужно было разыменовывать подобное

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

Вот что в итоге сработало

 void getConnectedComponents(string buildingName, vertex *amp; 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;
}