 |
Business | Industries | Finance | Tax |
| Index: > A B C D E F G H I J K L M N O P Q R S T U V W X Y Z |
|
|||||
It works as follows:
Using a simple binary heap data structure, Prim's algorithm can be shown to run in time which is O((m + n) log n) where m is the number of edges and n is the number of vertices. Using a more sophisticated Fibonacci heap, this can be brought down to O(m + nlog n), which is significantly faster when the graph is dense enough that m is ω(nlog n).
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 to other vertices and edges of Y and at no iteration is a circuit created since each edge added connects two vertices in two disconnected sets. Also, Y includes all vertices from P because Y is a tree with n vertices, same as P. Therefore, Y is a spanning tree for P.
Let Y1 be any minimal spanning tree for P. If Y = Y1, then the proof is complete. If not, there is an edge in Y that is not in Y1. Let e be the first edge that was added when Y was constructed. Let V be the set of vertices of Y - e. Then one endpoint of e is in Y and another 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 tree obtained by removing f and adding e from Y1. It shows that Y2 is a tree that is more common with Y than with Y1. If Y2 equals Y, QED. If not, we can find a tree, Y3 with one more edge in common with Y than Y2 and so forth. Continuing this way produces a tree that is more in common with Y than with the preceding tree. Since there are finite number of edges in Y, the sequence is finite, so there will eventually be a tree, Yh, which is identical to Y. This shows Y is a minimal spanning tree.
Other algorithms for this problem include Kruskal's algorithm and Boruvka's algorithmTrees (structure) Boruvka's algorithm is an algorithm for finding minimum spanning trees. It was first published in 1926 by Otakar Boruvka as a method of efficiently electrifying Bohemia. Boruvka's algorithm, in pseudocode, given a graph G is: Copy the ve.
| Politics | Business | Finance |
 |
 |
 |
|