Question

C++

Write a program that outputs the nodes of a graph in a breadth-first traversal.

Answer 1

// Example program
#include <iostream>
#include <string>

#include <list>
#include <queue>
#include <cstdlib>
using namespace std;

struct AdjListNode{ //Adjacency List Node
int dest;
struct AdjListNode* next;
};

struct AdjList{ //Adjacency List
struct AdjListNode* head;
};

class Graph{
private:
int V;
struct AdjList* array;
public:
void BFS(int s);
Graph(int V){
this->V = V;
array = new AdjList [V];
for (int i = 0; i < V; ++i)
array[i].head = NULL;
}

AdjListNode* newAdjListNode(int dest){//create new adjacency list node
AdjListNode* newNode = new AdjListNode;
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}

void addEdge(int src, int dest){ //Add Edge to Graph
AdjListNode* newNode = newAdjListNode(dest);
newNode->next = array[src].head;
array[src].head = newNode;
newNode = newAdjListNode(src);
newNode->next = array[dest].head;
array[dest].head = newNode;
}

void printGraph(){ //print grao
int v;
for (v = 0; v < V; ++v)
{
AdjListNode* pCrawl = array[v].head;
cout<<"\n Adjacency list of vertex "<<v<<"\n head ";
while (pCrawl)
{
cout<<"-> "<<pCrawl->dest;
pCrawl = pCrawl->next;
}
cout<<endl;
}
}
};

void Graph::BFS(int s)
{
bool *traversed = new bool[V];
for(int i = 0; i < V; i++)
traversed[i] = false;

list<int> q;

traversed[s] = true;
q.push_back(s);
list<int>::iterator i;

while(!q.empty())
{
s = q.front();
cout << s << " ";
q.pop_front();

for(AdjListNode* pCrawl = array[s].head; pCrawl!=NULL;)
{
if(!traversed[pCrawl->dest])
{
traversed[pCrawl->dest] = true;
q.push_back(pCrawl->dest);
  
}
pCrawl = pCrawl->next;
}
}
}

int main(){
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
g.printGraph();
cout << "BFS from vertex 0"<<endl;
g.BFS(0);
  

  
}

=============================
See Output


D main.cpp DI main.cpp Adjacency list of vertex 0 head->2- 2- 1 /9 80 81 82 q.pop_front): for(Adj ListNode* pCrawl array [s].head; Adjacency list of vertex 1 head->2-> 0 pCrawl !=NULL; ) 83 84 85 86 87 if (!traversed [pCrawl->dest]) Adjacency list of vertex 2 head-3- 0-1- 0 traversed [pCrawl->dest] = true; q.push back(pCrawl->dest); Adjacency list of vertex 3 head -> 3-> 3-> 2 BFS from vertex 0 0 2 1 3 89 90 91 92 awt = pCrawl->next; 93 1 94 95 int main() Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge (2, 0); g.addEdge(2, 3); g.addEdge(3, 3); g.printGraph ) cout << "BFS from vertex 0"<endl; g. BFS(0); 96 97 98 100 101 102 103 104 105 106 107 108

Thanks, PLEASE UPVOTE if helpful