#Try to implement BFS in Graph but not showing any output..

7 messages · Page 1 of 1 (latest)

hasty iron
# 
#include <iostream>
#include <vector>
#include <unordered_map>
#include <list>
#include <queue>

using namespace std;

class graph
{
public:
    unordered_map<int, bool> visited;
    void addEdge(int u, int v, bool direction);
    vector<int>BFS(unordered_map<int, list<int>> adj, int node);
    void BFSIN(unordered_map<int, list<int>> adj,int vertex);
};

void graph ::addEdge(int u, int v, bool direction)
{
    unordered_map<int, list<int>> adj;

    adj[u].push_back(v);

    if (direction == 0)
    {
        adj[v].push_back(u);
    }
}

vector<int> graph ::BFS(unordered_map<int, list<int>> adj, int node)
{
    int front;
    queue<int> q;
    vector<int> result;
    q.push(node);
    visited[node] = true;

    while (q.empty() == false)
    {
        front = q.front();
        result.push_back(front);
        q.pop();
    }
    for (auto i : adj[front])
    {
        if (!visited[i])
        {
            q.push(i);
            visited[i] = true;
            result.push_back(i);
        }
    }
    return result;
}

void graph :: BFSIN(unordered_map<int, list<int>> adj,int vertex)
{
    for (int  i = 0; i < vertex; i++)
    {
       if (visited[i]==false)
       {
       BFS(adj,i);
       }
       
    }
    
}
int main()
{  
    int vertex = 7;
    unordered_map<int , list<int>>adj;
    graph g;
    g.addEdge(0,2,0); 
    g.addEdge(2,3,0); 
    g.addEdge(1,3,0); 
    g.addEdge(4,5,0);
    g.addEdge(5,6,0);
    g.addEdge(4,6,0);

    cout << "Following is Breadth First Traversal: "<< endl; 
    g.BFSIN( adj,vertex); 


    return 0;
}
carmine canyon
#

The code you provided is an implementation of a graph using an adjacency list and performs Breadth First Search (BFS) traversal on the graph. It seems like there are a few issues with the code:

  1. The addEdge method is currently creating a new adj map within the method instead of using the member variable adj. You should remove the line unordered_map<int, list<int>> adj; from the addEdge method to resolve this issue.

  2. In the BFS method, the loop that processes the adjacent nodes should be inside the while loop. Move the for loop inside the while loop so that it correctly processes all adjacent nodes before moving to the next level of traversal.

Here's the corrected code:

#include <iostream>
#include <vector>
#include <unordered_map>
#include <list>
#include <queue>

using namespace std;

class graph
{
public:
    unordered_map<int, bool> visited;
    unordered_map<int, list<int>> adj;
    void addEdge(int u, int v, bool direction);
    vector<int> BFS(int node);
    void BFSIN(int vertex);
};

void graph::addEdge(int u, int v, bool direction)
{
    adj[u].push_back(v);

    if (direction == 0)
    {
        adj[v].push_back(u);
    }
}

vector<int> graph::BFS(int node)
{
    queue<int> q;
    vector<int> result;
    
    q.push(node);
    visited[node] = true;

    while (!q.empty())
    {
        int front = q.front();
        result.push_back(front);
        q.pop();

        for (auto i : adj[front])
        {
            if (!visited[i])
            {
                q.push(i);
                visited[i] = true;
                result.push_back(i);
            }
        }
    }

    return result;
}

void graph::BFSIN(int vertex)
{
    for (int i = 0; i < vertex; i++)
    {
        if (!visited[i])
        {
            BFS(i);
        }
    }
}

int main()
{
    int vertex = 7;
    graph g;
    g.addEdge(0, 2, 0);
    g.addEdge(2, 3, 0);
    g.addEdge(1, 3, 0);
    g.addEdge(4, 5, 0);
    g.addEdge(5, 6, 0);
    g.addEdge(4, 6, 0);
#

cout << "Following is Breadth First Traversal: " << endl;
g.BFSIN(vertex);

return 0;

}


This code should now perform the BFS traversal correctly.
hasty iron
hasty iron
carmine canyon
#

If only the cout statement is printing and the rest of the code is not executing, it is likely that there is an issue with the condition or loop control in your code. Please provide the specific code you are referring to so that I can help you identify and resolve the issue.

hasty iron
# 
#include<bits/stdc++.h> 
using namespace std; 

void BFS(vector<int> adj[], int s, bool visited[]) {     
    queue<int>  q;
    visited[s] = true; 
    q.push(s); 
    while(q.empty()==false) { 
        int u = q.front(); 
        q.pop();
        cout << u << " "; 
         
        for(int v:adj[u])
            if(visited[v]==false){
                visited[v]=true;
                q.push(v);
            }
    } 
}

void BFSDin(vector<int> adj[], int V){
    bool visited[V]; 
    for(int i = 0; i<V; i++) 
        visited[i] = false;
        
    for(int i=0; i<V; i++){
        if(visited[i]==false)
            BFS(adj,i,visited);
    }
}

void addEdge(vector<int> adj[], int u, int v){
    adj[u].push_back(v);
    adj[v].push_back(u);
}

int main() { 
    int V=7;
    vector<int> adj[V];
    addEdge(adj,0,1); 
    addEdge(adj,0,2); 
    addEdge(adj,2,3); 
    addEdge(adj,1,3); 
    addEdge(adj,4,5);
    addEdge(adj,5,6);
    addEdge(adj,4,6);

    cout << "Following is Breadth First Traversal: "<< endl; 
    BFSDin(adj,V); 

    return 0; 
}