COMP3040: Design and Analysis of Algorithms

Fall 2019

Assignment 2: Graphs

Due Date: Oct 24

Question 1: Given the following undirected graph G (V, E)

a) Represent the graph using an adjacency list.

b) Show the tree produced by depth-first search, using vertex s as the source vertex. If 

multiple neighbors are available, visit them using alphabetical order.

c) Show the back edges with dashed lines.

d) Find out all the articulation points.

Question 2: Below is a weighted undirected graph G(V, E).

b s a b

c 

e f d 6 10

5 7 1

11

4 3 2 s 2 a c 9 e f d

a) Draw an adjacency matrix to represent the graph.

b) Consider running Prim algorithm to generate its minimum spanning tree. Show 

different steps the minimum spanning tree produced using node s as the root. In 

particular, after each step, you need to indicate key[v], pred[v], color[v] for each 

vertex v and the content of Q. Please refer to Page 32 of Lecture 7 for the definition of 

key, pred, color and Q.

Step 0, which is the initialization step, has already been done for you.

Step 0:

V s a b c d e f

key[v] 0 ∞ ∞ ∞ ∞ ∞ ∞

Pred[v] nil

Color[v] W W W W W W W

c) Show its minimum spanning tree produced using Kruskal's algorithm. Draw a partial 

forest every time an edge is added into selection (i.e., you should draw 6 forests).

d) Does (b) and (c) produce the same MST? If every edge in a graph has a unique 

weight (as in our example), does the graph have a unique MST? If your answer is yes, 

prove it. Otherwise, give a counter-example (i.e., a graph with unique weights having 

at least two different MST’s).

Question 3: Let G = (V,E) be a connected undirected graph in which all edges have 

weight 1 or 2. Give an O(|V | + |E|) algorithm which computes a minimum spanning tree 

of G. Justify the running time of your algorithm. (Hint: Modify Prim’s algorithm).