Heuristics: Minimal Spanning Tree 3
Inhaltsverzeichnis
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/
