In this assignment we want you to write simple graph algorithms for undirected

graphs. There are three algorithmic tasks. Each task should be coded up in a

separate program.

1. Determine the order of the largest component.

2. Convert to adjacency matrix representation.

3. Compute the diameter.

Input Format

Input for these problems consist of a sequence of one or more (undirected) graphs

taken from the keyboard (e.g. sys.stdin). Each graph is represented by an adjacency list. The first line is an integer n indicating the order of the graph. This is

followed by n white space separated lists of adjacencies for nodes labeled 0 to n - 1.

The input will be terminated by a line consisting of one zero (0). This line should

not be processed. Two sample input graphs are listed below.

4 1

0 3

1 5

1 4

0 2

1 3

2 4

0 3

0

G1 G2

0 1

3 2

0 1

2

3

4

Output Format

Output will be like the model answers given below to the console (e.g. sys.stdout).

Your program will only be correct if there is no difference between your output

and the model solution using an automated ’diff’ checker (think windiff, vim -d,

etc). That is, any other output besides a sequence of answers required is a wrong

program!

Output for Task 1

Graph 1 has a component of order 3.

Graph 2 has a component of order 5.

Output for Task 2

4

0 1 0 0

1 0 0 1

0 0 0 0

0 1 0 0

5

0 1 0 0 1

1 0 1 0 0

0 1 0 1 0

0 0 1 0 1

1 0 0 1 0

0

Output for Task 3

Graph 1 is disconnected.

Graph 2 has diameter 2.

Besides have a correct program your grade for this assignment will also be based

on how efficient (fast!) your program can handle the marker’s data. To get marks it

must complete with the correct answer within a few seconds on a reasonable sized

data set (e.g., expect more than two graphs with at least 1000 vertices).

Computer Science 220S2C (2019)

Assignment 3: Graph Algorithms

Please read the entire assignment before starting.

Goals