Aktuelle Version vom 1. Juli 2013, 13:34 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: Choose randomly node "2" and connect it to the closest node "1".

Step 2: Choose the unlinked node, which is closest to the already linked nodes. In this case there are two options. Either node "5" or node "3". Choose randomly one of those options (here: node "5").

Step 3: Repeat this with the next unlinked node, which is closes to the already linked nodes (here: node "3").

Step 4: Repeat this with the next unlinked node, which is closes to the already linked nodes (here: node "6").

Step 5: Repeat this with the next unlinked node, which is closes to the already linked nodes (here: node "7").

Step 6: Repeat this with the next unlinked node, which is closes to the already linked nodes (here: node "2").

Step 7: Repeat this with the next unlinked node, which is closes to the already linked nodes (here: node "8").

All nodes are linked. There is no cycle. The solution is optimal.

Kruskal

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

Process

1: Sort and number up all edges ki of the graph 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.

Example

Initial Problem: Count of nodes n = 8

Sort the edges:

Step 1:

Step 2: Count of edges 1 < n - 1

Step 3: Count of edges 2 < n - 1

Step 4:Count of edges 3 < n - 1

Step 5: Count of edges 4 < n - 1

Step 6: Count of edges 5 < n - 1

Step 7: Count of edges 6 < n - 1

Step 8: Adding edge k7 leads to a cycle, therefore k7 is not added.

Step 9: Adding edge k8 leads to a cycle, therefore k8 is not added.

Step 10: Count of edges 7 = n - 1. The optimal solution is reached.

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/