0.7 Graphs  (Page 7/21)

Pseudocode

1 function Kruskal(G)

2 for each vertex v in G do

3 Define an elementary cluster C(v) ← {v}.

4 Initialize a priority queue Q to contain all edges in G, using the weights as keys.

5 Define a tree T ← Ø //T will ultimately contain the edges of the MST

6 // n is total number of vertices

7 while T has fewer than n-1 edges do

8 // edge u,v is the minimum weighted route from/to v

9 (u,v) ← Q.removeMin()

10 // prevent cycles in T. add u,v only if T does not already contain an edge consisting of u and v.

11 // Note that the cluster contains more than one vertex only if an edge containing a pair of

12 // the vertices has been added to the tree.

13 Let C(v) be the cluster containing v, and let C(u) be the cluster containing u.

14 if C(v) ≠ C(u) then

15 Add edge (v,u) to T.

16 Merge C(v) and C(u) into one cluster, that is, union C(v) and C(u).

17 return tree T

7.2.3. jarnik-prim’s algorithms

(From Wikipedia, the free encyclopedia)

Prim's algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The algorithm was discovered in 1930 by mathematician Vojtěch Jarník and later independently by computer scientist Robert C. Prim in 1957 and rediscovered by Dijkstra in 1959. Therefore it is sometimes called the DJP algorithm or Jarnik algorithm.

Description

The algorithm continuously increases the size of a tree starting with a single vertex until it spans all the vertices.

• Input: A connected weighted graph G(V,E)
• Initialize: V' = {x}, where x is an arbitrary node from V, E'= {}
• repeat until V'=V:
  • Choose edge (u,v) from E with minimal weight such that u is in V' and v is not in V' (if there are multiple edges with the same weight, choose arbitrarily)
  • Add v to V', add (u,v) to E'
• Output: G(V',E') is the minimal spanning tree

Time complexity

A simple implementation using an adjacency matrix graph representation and searching an array of weights to find the minimum weight edge to add requires O(V^2) running time. Using a simple binary heap data structure and an adjacency list representation, Prim's algorithm can be shown to run in time which is O(Elog V) where E is the number of edges and V is the number of vertices. Using a more sophisticated Fibonacci heap, this can be brought down to O(E + Vlog V), which is significantly faster when the graph is dense enough that E is Ω(Vlog V).

Example

Image	Description	Not seen	Fringe	Solution set
	This is our original weighted graph. This is not a tree because the definition of a tree requires that there are no circuits and this diagram contains circuits. A more correct name for this diagram would be a graph or a network. The numbers near the arcs indicate their weight. None of the arcs are highlighted, and vertex D has been arbitrarily chosen as a starting point.	C, G	A, B, E, F	D
	The second chosen vertex is the vertex nearest to D: A is 5 away, B is 9, E is 15, and F is 6. Of these, 5 is the smallest, so we highlight the vertex A and the arc DA.	C, G	B, E, F	A, D
	The next vertex chosen is the vertex nearest to either D or A. B is 9 away from D and 7 away from A, E is 15, and F is 6. 6 is the smallest, so we highlight the vertex F and the arc DF.	C	B, E, G	A, D, F
	The algorithm carries on as above. Vertex B, which is 7 away from A, is highlighted. Here, the arc DB is highlighted in red, because both vertex B and vertex D have been highlighted, so it cannot be used.	null	C, E, G	A, D, F, B
	In this case, we can choose between C, E, and G. C is 8 away from B, E is 7 away from B, and G is 11 away from F. E is nearest, so we highlight the vertex E and the arc EB. Two other arcs have been highlighted in red, as both their joining vertices have been used.	null	C, G	A, D, F, B, E
	Here, the only vertices available are C and G. C is 5 away from E, and G is 9 away from E. C is chosen, so it is highlighted along with the arc EC. The arc BC is also highlighted in red.	null	G	A, D, F, B, E, C
	Vertex G is the only remaining vertex. It is 11 away from F, and 9 away from E. E is nearer, so we highlight it and the arc EG. Now all the vertices have been highlighted, the minimum spanning tree is shown in green. In this case, it has weight 39.	null	null	A, D, F, B, E, C, G