LAB 2 Solution

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.



















EXAMPLE 2:




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