Write a C++ program called BFS.cpp that implements the Breadth-First Search (BFS

Question

Write a C++ program called BFS.cpp that implements the Breadth-First Search (BFS) algorithm. Your program should read an input file name and a starting node from a user. After that, your program should display the list of vertices visited. In the problem, you can assume that the number of vertices in the input file is less than or equal to 25.

[Hint: Since the maximum number of vertices is less than or equal to 25, you can use a simple array-based queue for the BFS algorithm.]

Input file format: This is a sample input file called t1.txt.

The first line (= 3 in the example) indicates that there are three vertices in the graph. For the homework, we can assume that the first vertex starts from the number 0. Thus, t1.txt describes a graph like below:

One blank space is used to delimiter the data. Note that there’s no blank space at the end of each line. If your program does not read the file properly, your program will get no credit.

The following presents a sample run of the program. Your program has to run exactly like this.

Enter filename:

Enter a start vertex: 0

BFS order: 0 -> 1 -> 2

In the program, your program has to follow our convention (= ascending order).

This is another sample input file called t2.txt.

This is a sample run:

Enter filename: C:\tmp\t2.txt

Enter a start vertex: 0

BFS order: 0 -> 2 -> 1 -> 3 -> 4

Explanation / Answer

Here is the code for the question. Please don't forget to rate the answer if it helped. Thank you very much.

#include <iostream>

#include <fstream>

using namespace std;

//inserts a vertex into queue if its not already present in the queue.

//increments the len (pass by reference) if vertex was added to queue

void insertInQueue(int queue[], int &len, int vertex)

{

//cout << "insert " << vertex << endl;

for(int i = 0; i < len; i++)

{

if(queue[i] == vertex)

return;

}

queue[len] = vertex;

len++;

}

int main()

{

string filename;

int start;

cout << "Enter filename: ";

cin >> filename;

cout << "Enter the start vertex: ";

cin >> start;

ifstream infile(filename);

if(infile.fail())

{

cout << "Error opening input file " << filename << endl;

exit(1);

}

int N;

infile >> N; //get the number of vertices;

//create an adjacency matrix and then fill it from the file

int adjacency[N][N];

for(int i = 0; i < N; i++)

{

for(int j = 0; j < N; j++)

infile >> adjacency[i][j];

}

infile.close();

cout << "adjacency matrix " <<endl;

for(int i = 0; i < N; i++)

{

cout << endl;

for(int j = 0; j < N; j++)

cout << adjacency[i][j] << " ";

}

int queue[N];//create a queue to store the order of BFS order

int queue_len = 0;

//put the start node in beginning

queue[0] = start;

queue_len++;

//for each node in the queue, add each adjacent node to the queue

// only if its not in queue already

int vertex;

for(int i = 0; i < queue_len; i++)

{

vertex = queue[i];

for(int j = 0; j < N; j++)

{

if(adjacency[vertex][j] != 0) //if the node j is adjancent to node i

insertInQueue(queue, queue_len, j);

}

}

cout << " The BFS traversal is " << endl;

cout << queue[0] ;

for( int i = 1; i < queue_len; i++)

cout << " -> " << queue[i] ;

cout << endl;

}

input file bfs1.txt

3
0 1 0
1 0 1
0 1 0

input file bfs2.txt

5
0 0 1 0 0
0 0 1 0 0
1 1 0 1 1
0 0 1 0 0
0 0 1 0 0

output

Enter filename: bfs1.txt
Enter the start vertex: 0
adjacency matrix

0 1 0
1 0 1
0 1 0
The BFS traversal is
0 -> 1 -> 2
======

Enter filename: bfs2.txt
Enter the start vertex: 0
adjacency matrix

0 0 1 0 0
0 0 1 0 0
1 1 0 1 1
0 0 1 0 0
0 0 1 0 0
The BFS traversal is
0 -> 2 -> 1 -> 3 -> 4

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.