0.7 Graphs  (Page 8/21)

Pseudo-code

Min-heap

Initialization

inputs: A graph, a function returning edge weights weight-function, and an initial vertex

initial placement of all vertices in the 'not yet seen' set, set initial vertex to be added to the tree, and place all vertices in a min-heap to allow for removal of the min distance from the minimum graph.

for each vertex in graph

set min_distance of vertex to ∞

set parent of vertex to null

set minimum_adjacency_list of vertex to empty list

set is_in_Q of vertex to true

set distance of initial vertex to zero

add to minimum-heap Q all vertices in graph.

Algorithm

In the algorithm description above,

nearest vertex is Q[0], now latest addition

fringe is v in Q where distance of v<∞ after nearest vertex is removed

not seen is v in Q where distance of v = ∞ after nearest vertex is removed

The while loop will fail when remove minimum returns null. The adjacency list is set to allow a directional graph to be returned.

time complexity: V for loop, log(V) for the remove function

while latest_addition = remove minimum in Q

set is_in_Q of latest_addition to false

add latest_addition to (minimum_adjacency_list of (parent of latest_addition))

add (parent of latest_addition) to (minimum_adjacency_list of latest_addition)

time complexity: E/V, the average number of vertices

for each adjacent of latest_addition

if (is_in_Q of adjacent) and (weight-function(latest_addition, adjacent)<min_distance of adjacent)

set parent of adjacent to latest_addition

set min_distance of adjacent to weight-function(latest_addition, adjacent)

time complexity: log(V), the height of the heap

update adjacent in Q, order by min_distance

Proof of correctness

Let P be a connected, weighted graph. At every iteration of Prim's algorithm, an edge must be found that connects a vertex in a subgraph to a vertex outside the subgraph. Since P is connected, there will always be a path to every vertex. The output Y of Prim's algorithm is a tree, because the edge and vertex added to Y are connected. Let Y1 be a minimum spanning tree of P. If Y1=Y then Y is a minimum spanning tree. Otherwise, let e be the first edge added during the construction of Y that is not in Y1, and V be the set of vertices connected by the edges added before e. Then one endpoint of e is in V and the other is not. Since Y1 is a spanning tree of P, there is a path in Y1 joining the two endpoints. As one travels along the path, one must encounter an edge f joining a vertex in V to one that is not in V. Now, at the iteration when e was added to Y, f could also have been added and it would be added instead of e if its weight was less than e. Since f was not added, we conclude that

w(f) ≥ w(e).

Let Y2 be the graph obtained by removing f and adding e from Y1. It is easy to show that Y2 is connected, has the same number of edges as Y1, and the total weights of its edges is not larger than that of Y1, therefore it is also a minimum spanning tree of P and it contains e and all the edges added before it during the construction of V. Repeat the steps above and we will eventually obtain a minimum spanning tree of P that is identical to Y. This shows Y is a minimum spanning tree.