GRAP H S

1. Consider the adjacency matrix of a graph below:

0	1	1	0	0
0	0	1	0	0
0	0	0	1	0
0	0	0	0	0
1	0	1	1	0

A =

(a) Draw the graph

(b) Write the adjacency list for the graph

(c) Discuss the suitability of using an adjacency matrix and the adjacency list for the graph. Justify your answer.

2. Using the adjacency matrix approach, write a program to store a simple graph and display the graph.

Example 4.23

Store and Display a simple graph

-------------------------

1. Store a graph

2. Display a graph

0. Quit

Please input your choice (0-2) >

Hint An easy approach may be:

(a) define a data structure for the graph

(b) decide a means to input the graph, for example, you may

i. type the entries of the adjacency matrix on the keyboard ii. read the entries of the adjacency matrix from a text file iii. generate a random adjacency matrix by a program.3

3

Use a random generator to generate

a 0 or 1 uniformly at random for each entry of the matrix.

(c) write the main program or method with interfaces of the

sub-methods or procedures

(d) develop each part of the program.

3. Implement the graphs in question 1 using the adjacency list

approach.

I WANT THE SECAND PART