Version vom 1. Juli 2013, 13:10 Uhr

Minimal Spanning Tree

General Information

The goal of Minimal Spanning Trees is to link all nodes directly or indirectly to minimize the length of all edges. This also implies the minimization of the costs. A direct link signifies the existence of an edge between two nodes. In contrast, an indirect link signifies the existence of a path, which links two nodes over another or more nodes. To find the optimal solution nodes have to get linked directly step by step.

Prim

The Prim is an algorithm that always leads to the optimal solution and therefore the Prim is one opportunity of creating a minimal spanning tree.

Process

1. Choose a random node and link it to the nearest other node. In this case nearest means the node with the shortest distance or the lowest costs etc.

2. Next, choose the unlinked node, which is the closest to the already linked ones.

3. Repeat Step 2 until all nodes are linked.

Note: If there are multiple options with the shortest distance choose the link randomly.

Example

Initial Problem:

Step 1:

Step 2:

Step 3:

Step 4:

Step 5:

Step 6:

Step 7:

Kruskal

Basis of the Kruskal algorithm is a coherent, undirected and loop free graph Graph G=[V,E,c] with n accounts and m edges.

Process

1: Sort and number up all edges ki of G in the row k1, k2,..., km with monotonic increasing importance c(ki), so that c(k1)<= c(k2)<=...<=c(km).

2: Repeat for all j, with j=1,...,m:

Choose the edge kj and check if the result of including kj in the graph is a circle. If no circle occurs, set E:=E'U{kj}.

3: Stop the process when E equals exactly n-1 edges.

The result of this process is the minimal spanning tree T= [V.E]

Example

Initial Problem:

Sort the edges:

Step 1:

Step 2:

Step 3:

Step 4:

Step 5:

Step 6:

Step 3:

Step 7:

Step 8:

Step 9:

Step 10:

Sources

http://en.wikipedia.org/wiki/Minimum_spanning_tree

http://delphiforfun.org/programs/Math_Topics/MinimalSpanningTrees.htm

http://compprog.wordpress.com/2007/11/09/minimal-spanning-trees-prims-algorithm/