April 11, 2010
Douglas Holmes
COMP510
Spring 2011
Assignment 5
19.2) Chapter 23 presents two algorithms to solve the problem of finding a minimum spanning tree of an undirected graph. Here, we shall see how binomial heaps can be used to devise a different minimum-spanning-tree algorithm.
We are given a connected, undirected graph G = (V, E) with a weight function w : E → R. We call w(u, v) the weight of edge (u, v). We wish to find a minimum spanning tree for G: an acyclic subset T E that connects all the vertices in V and whose total weight
w(T) = (u,v) ∈ T∑ w(u,v))
is minimized.
The following pseudocode, which can be proven correct using techniques from Section 23.1, constructs a minimum spanning tree T . It maintains a partition {Vi} of the vertices of V and, with each set Vi, a set
Ei (u,v):u Vi or v Vi} of edges incident on vertices in VI.
MST(G)
T ← Ø
for each vertex vi V[G] do Vi ← {vi}
Ei ← {(vi, v) E[G]} while there is more than one set Vi
do choose any set Vi extract the minimum-weight edge (u, v) from Ei assume without loss of generality that u Vi and v Vj if i ≠ j
then T ← T {(u, v)} Vi ← Vi Vj, destroying Vj Ei ← Ei Ej
Describe how to implement this algorithm using binomial heaps to manage the vertex and edge sets. Do you need to change the representation of a binomial heap? Do you need to add operations beyond the mergeable-heap operations given in Figure 19.1? Give the running time of your implementation.
Start by creating a binomial heap Hi for each set of edges Ei. Weight will serve as the key for each node. From there, assign each vector Vi corresponding to each binomial heap Hi. From there, iterate through each vector and extract the minimum vector in each binomial heap, adding any resulting vectors not already in the existing list of vectors to T, then add it to the list of processed vectors as well. The resulting tree will have the minimum-spanning tree edges. Since a heap can have a maximum of n-1 edges, with n vertices, and we will have to execute an extract operation for each heap value. This extraction takes 2n time to execute, so the time taken will be approximately 2n * O(lg(n-1)), or O(n lg n).
22.1-1) Given an adjacency-list representation of a directed graph, how long does it take to compute the out-degree of every vertex? How long does it take to compute the in-degrees?
The out-degree of a vertex is the number of edges leaving it. To compute the out-degree, we will require O(V+E) time. The in-degree, on the other hand, requires us going through the entire list of vertices, requiring us to to make O(V2+E) operations.
22.1-2) Give an adjacency-list representation for a complete binary tree on 7 vertices. Give an equivalent adjacency-matrix representation. Assume that vertices are numbered from 1 to 7 as in a binary heap.
Adjacency list
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|
| 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 2 | 1 | 0 | 0 | 1 | 1 | 0 | 0 |
| 3 | 1 | 0 | 0 | 0 | 0 | 1 | 1 |
| 4 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 5 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 6 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 7 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
22.1-3) The transpose of a directed graph G = (V, E) is the graph GT = (V, ET), where ET = {(v, u) V × V : (u, v) E}. Thus, GT is G with all its edges reversed. Describe efficient algorithms for computing GT from G, for both the adjacency-list and adjacency-matrix representations of G. Analyze the running times of your algorithms.
We're looking at a directed graph, which means the adjacency matrix will not be symmetric as it was in the prior problem. Thus, we will have to swap every element (u,v) to (v,u). The resulting time to swap all elements of a matrix is O(V2). As for an adjacency list, we'll have to create a new adjacency list while traversing the existing one, costing less time overall at O(V+E).
22.1-4) Given an adjacency-list representation of a multigraph G = (V, E), describe an O(V + E)-time algorithm to compute the adjacency-list representation of the "equivalent" undirected graph G′ = (V, E′), where E′ consists of the edges in E with all multiple edges between two vertices replaced by a single edge and with all self-loops removed.
Iterate through every vertex in G. For every vertex vi, if there exists an adjacent vertex vj that is greater, then add vi to the adjacency list of j in G'. From here, we do the same for G', but in reverse, putting vi in vj's list if vi is greater. This gives us the requested graph, and with each step taking O(V+E) since we only iterated through the lists in both cases, the overall time is also O(V+E).
References:
- Course Textbook: T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms, Second Edition.
- Course Textbook: T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms, Third Edition.