[SOLVED] algorithm graph s

s
a
c

e
f
d
Fall 2019
Assignment 2: Graphs

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

b

Represent the graph using an adjacency list.
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.
Show the back edges with dashed lines.
Find out all the articulation points.
Question 2: Below is a weighted undirected graph G(V, E).

2
2
3
4
11
1
7
5
10
6
d
f
e
c
b
a
s

9

Draw an adjacency matrix to represent the graph.
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

Show its minimum spanning tree produced using Kruskals algorithm. Draw a partial forest every time an edge is added into selection (i.e., you should draw 6 forests).
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 MSTs).

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 Prims algorithm).