need help for printing BFS node source

[GonlyG]

I'm testing around with BFS and I understand the basic algorithm to display the nodes in visited order, but am struggling to get the nodes used to visit that particular node. Any hints?

#include<iostream> 
#include <list> 
  
using namespace std; 
  
class Graph 
{ 
    int V;    
  
    list<int> *adj;    
public: 
    Graph(int V);  
  
    void addEdge(int v, int w);  
  
    void BFS(int s);   
}; 
  
Graph::Graph(int V) 
{ 
    this->V = V; 
    adj = new list<int>[V]; 
} 
  
void Graph::addEdge(int v, int w) 
{ 
    adj[v].push_back(w); // Add w to v’s list. 
} 
  
void Graph::BFS(int s) 
{ 
    // Mark all the vertices as not visited 
    bool *visited = new bool[V]; 
    for(int i = 0; i < V; i++) 
        visited[i] = false; 
  
    list<int> queue; 
  
    // Mark the current node as visited and enqueue it 
    visited[s] = true; 
    queue.push_back(s); 
  
    list<int>::iterator i; 
  
    while(!queue.empty()) 
    { 
        s = queue.front(); 
        cout << s << " "; //displays in order BFS as expected
        queue.pop_front(); 
  
        // Get all adjacent vertices, if it has not been visited,  
        // then mark it visited and enqueue it 
        for (i = adj[s].begin(); i != adj[s].end(); ++i) 
        {  
            if (!visited[*i]) 
            {   cout<<s<<" "; //doesn't work to display source of where this was visited from, surprisingly
                visited[*i] = true; 
                queue.push_back(*i); 
            } 
        } 
    } 
} 

[dutch]

I think you mean to print *i in the inner loop.

[GonlyG]

wouldn't *i just be which one is going to be visited? I output s because it's the vertex originally popped

[dutch]

I guess I don't understand what you are trying to do.
You've already printed s, so printing it a bunch more times in the inner loop seems pointless.

[dhayden]

Right now you're printing the nodes when they go in the list AND when they come out. Don't print them in the inner loop at all.

You're leaking the memory allocated at lines 22 and 34. Why not use vectors instead?

[GonlyG]

the inner loop is to see if I can know where a node was visited from. Right now, it only prints out the nodes in BFS order.

Ooop, didn't realize about memory leak. The original code was actually Java equivalent and I was in a rush so I forgot about vectors.

[dhayden]

Okay. Then print the path in the inner loop and don't print anything in the outer loop. You'll need a special case for the first node:

void Graph::BFS(int s) 
{ 
    // Mark all the vertices as not visited 
    bool *visited = new bool[V]; 
    for(int i = 0; i < V; i++) 
        visited[i] = false; 
  
    list<int> queue; 
  
    // Mark the current node as visited and enqueue it 
    visited[s] = true; 
    queue.push_back(s); 
  
    cout << "null -> " << s << '\n';
    list<int>::iterator i; 
  
    while(!queue.empty()) 
    { 
        s = queue.front(); 
        queue.pop_front(); 
  
        // Get all adjacent vertices, if it has not been visited,  
        // then mark it visited and enqueue it 
        for (i = adj[s].begin(); i != adj[s].end(); ++i) 
        {  
            if (!visited[*i]) {
		cout<<s<<" -> " << *i << '\n';
                visited[*i] = true; 
                queue.push_back(*i); 
            } 
        } 
    } 
    delete [] visited;
} 

[GonlyG]

I feel like maybe I'm outputting stuff in a wrong order. Using this, I got:

-1 -> 0 0-> 25 0-> 22 0-> 8 25-> 36 25-> 15 25-> 16 25-> 39 22-> 23 22-> 35 22-> 31 22-> 44 22-> 6 8-> 7 8-> 29 8-> 24 36-> 17 36-> 2 36-> 27 36-> 3 15-> 12 16-> 37 16-> 42 16-> 13 39-> 32 39-> 20 23-> 28 23-> 10 23-> 1 31-> 18 44-> 41 44-> 34 7-> 19 29-> 38 29-> 26 2-> 14 27-> 40 3-> 21 12-> 9 12-> 5 37-> 11 28-> 43 18-> 33 18-> 30 41-> 4

but the expected values were:

-1 23 36 36 41 12 8 8 0 28 23 37 39 16 38 25 25 36 31 7 39 3 0 22 8 0 24 24 6 8 26 22 39 19 44 22 8 16 29 8 19 44 29 28 22

as you can see it directly jumped to 23 somehow, despite not visiting it until after 22. The problem statement says to sort the neighbors by increasing ID but this didn't work either. Any insight?

[dhayden]

Please post your current code and the input.