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

while I understand the BFS conceptually I haven’t grasped how to use an iterator and a queue to implement the BFS. I’d really appreciate it if somebody could give me some insight how to properly use the iterator in my code. Thank you.

I’m not even sure if an iterator is a good idea here, I tried to learn the auto type too but I’m not sure how to use that.

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

Note: I solved my own question in the comments.

Answer

I made slight changes to my code to fix it. I didn’t use the iterator (an int variable in the for loop was fine), and I didn’t need to dereference like this

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

Here’s what ended up working

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;
}

Leave a Reply

Your email address will not be published. Required fields are marked *