Description
Design and code an algorithm to do a breadth first search on an undirected graph, finding the shortest distances and determining if the graph is connected.
Details
Input to your program consists of an integer n representing the number of vertices followed an adjacency matrix of n rows, each row with n entries.
Each entry of the n x n adjacency matrix, will contain a 1 if there is an edge between the corresponding vertices or a 0 if there is no edge.
Use the iterative breadth first search algorithm, to traverse the graph and output each vertex and its shortest distance from the starting vertex, vertex 1. Once the BFS is finished, determine if the BFS has visited every vertex. If so, output “The graph is connected.” Otherwise output “The graph is not connected.”
EXAMPLE 1:
Input (Adjacency Matrix Representation)
-
5
// 5 vertices in graph. There will be 5 rows of the matrix, each with 5 entries.
0 0 1 0 0
// Row 1 of Adjacency Matrix, vertices adjacent to vertex 1
0 0 1 0 0
// Row 2 of Adjacency Matrix, vertices adjacent to vertex 2
1 1 0 1 1
// Row 3 of Adjacency Matrix, vertices adjacent to vertex 3
0 0 1 0 1
// Row 4 of Adjacency Matrix, vertices adjacent to vertex 4
0 0 1 1 0
// Row 5 of Adjacency Matrix, vertices adjacent to vertex 5
Output
BFS
Vertices & Distances:
-
0
-
1
-
2
-
2
-
2
The graph is connected.
Input (Adjacency Matrix Representation)
7
0 0 1 0 1 0 1
0 0 0 1 0 0 1
1 0 0 0 1 0 0
0 1 0 0 0 0 1
1 0 1 0 0 0 1
0 0 0 0 0 0 0
1 1 0 1 1 0 0
Output
BFS
Vertices & Distances:
-
0
-
1
-
1
-
1
-
2
-
2
The graph is not connected.
Notes:
The breadth first search should start at the first vertex of the graph which is represented by the
first row of the adjacency matrix. Each vertex should be output no more than once.
You may assume a max matrix of n = 20, that is a 20 x 20 matrix. The number of components
could be between 1 and n inclusive.
You may write your program in C, C++, or Java. Save your program in a file called lab2.* where * is the file extension. Do not use components, libraries, etc. for this program other than for I/O.
You must implement a queue.
This program must run on the CSE stdlinux environment, if you do not know your username
and/or password, please view information on the CSE website under Computing Services. Code that does not compile or has execution errors will be given a score of 0. It is your
responsibility to make sure that your code compiles and runs correctly in the CSE stdlinux
environment.
Your program should read from standard input. For instance, if your program is called lab2 you can run it on the file data1 by typing:
Lab2 < data2.
Use the submit command from the command line to submit your program, that is ,
‘submit c2321aj lab2 lab2.*’, where * is the file extension. It is your responsibility to confirm that your program submitted successfully.
Code should be commented and should contain a README header stating the student’s name,
email address, and instructions on how to compile and run the code.
Source code should be submitted electronically by 11:59 pm Monday, June 27th. A late penalty of 10% per hour will be assessed, for instance, if a lab is submitted at 12:00 am or 12:59 am there is a 10% penalty.
2
A printout of the source code along with screen shots of the output of the examples above along
with 3 other examples of your choosing should be turned in at the start of class on Tuesday,
June 28th.
This programming assignment is to be done individually. You may discuss the concepts of this
lab and/or any errors you may have with other students or on Piazza but do not look at or copy anyone else’s code or any code from the Internet or other references.
References:
Adjacency Matrix: GraphTheoryAlgorithm Lecture PowerPoint Slides,
also Textbook, pages 589-591
Breadth First Search: GraphTheoryAlgorithm Lecture PowerPoint Slides,
also Textbook, pages 594-602
2-Dimensional Array: Section 6.7 from Software I/II Java Reference book – free online at http://proquest.safaribooksonline.com.proxy.lib.ohio-state.edu/book/programming/java/9781118087886/chapter-6-arrays-and-array-lists/navpoint-54#X2ludGVybmFsX0h0bWxWaWV3P3htbGlkPTk3ODExMTgwODc4ODYlMkZuYXZwb2ludC02MC ZxdWVyeT0
3
