Question

Please provide C language code no c++ ,txt file also needed

with comment

Finish task 5
Task5: Breadth First Search (15 pts) · Write a program to read the graph information from the file and traverse the graph using BFS algorithm as introduced in lecture. The input for each algorithm is an undirected unweighted connected graph stored in a local file using an adjacency list. Following is the example of the input file (graph.txt) and the graph First line is the number of nodes. Start from second line, the first integer is the node number and remaining numbers forms the adjacency list of this node). . . 1 3 5 1 2,3,5 2 1,5 3 1,4 43,5 5 1,2,4 graph.txt 2 5 4

Answer 1

All the explanation is in the code comments. Hope this helps!

Code:

#include <iostream>
#include <fstream>
#include <vector>
#include <list>

using namespace std;

int main(int argc, char** argv)
{
// open file
// ifstream fin("graph.txt");
// for command line inputfile, use the following
ifstream fin(argv[1]);
  
// read number of nodes
int n, node, edge;
string edges;
fin >> n;
  
// create adjacency list for graph
vector<int> adj[n];
char c;
  
// start reading the lines
for(int i=0; i<n; i++)
{
// read node first
fin >> node;
// read the current line
getline(fin, edges);
// split the line into required data
for(int i=0; i<edges.size(); i++)
{
if(edges[i] == ' ')
edge = 0; // prepare for new number
else if(edges[i] == ',')
adj[node-1].push_back(edge-1); // end of the number
else
edge = edge * 10 + (int) (edges[i] - '0'); // add digit to number
}
// last edge
adj[node-1].push_back(edge-1);
}
  
// close file
fin.close();
  
// start the bfs
// Mark all the vertices as not visited
bool visited[n];
// also find the starting node
int s = 0;
for(int i = 0; i < n; i++)
{
visited[i] = false;
  
// starting node is the node with maximum degree
if(adj[i].size() >= adj[s].size())
s = i;
}
  
// Create a queue for BFS
list<int> queue;
  
// Mark the current node as visited and enqueue it
visited[s] = true;
queue.push_back(s);
  
cout << "BFS:";
while(!queue.empty())
{
// Dequeue a vertex from queue and print it
s = queue.front();
cout << " " << (s+1);
queue.pop_front();
  
// Get all adjacent vertices of the dequeued vertex s.
// visit the adjacency node in opposite order
// for the highest child has the most priority
// If a adjacent has not been visited, then mark it visited and enqueue it
for (int i = adj[s].size()-1; i >= 0; --i)
{
if (!visited[adj[s][i]])
{
visited[adj[s][i]] = true;
queue.push_back(adj[s][i]);
}
}
}
cout << endl;
return 0;
}

Sample output:

input

ол во ЈЕ л дw N Ел PPN NuA uw

output

BFS: 5 4 2 1 3

Code screenshot