Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| courses:cs211:winter2018:journals:holmesr:section_4.5 [2018/03/05 03:20] – holmesr | courses:cs211:winter2018:journals:holmesr:section_4.5 [2018/03/05 03:55] (current) – holmesr |
|---|
| |
| Additionally, the cut and cycle properties are treated by this section. The cut property says that S is any subset of nodes and e is the minimum cost edge with exactly one endpoint in S. Then the MST must contain e. The cycle property on the other hand says that C is any cycle and f is the max cost edge in C. Then the MST can not contain f. | Additionally, the cut and cycle properties are treated by this section. The cut property says that S is any subset of nodes and e is the minimum cost edge with exactly one endpoint in S. Then the MST must contain e. The cycle property on the other hand says that C is any cycle and f is the max cost edge in C. Then the MST can not contain f. |
| | |
| | having the cut property, we can now say that Kruskal's and Prim's Algorithms produce minimum spanning trees of their graphs. Prim's algorithm works simply by starting at any node in the graph and applying the cut property, adding the cheapest edge in the cutset of explores set s then adding the newly explored node to s. Kruskal's employs both properties; each edge falls into one of the two cases. Once the edges are ordered from smallest to largest, they will either complete a cycle or not. If the current edge being examined does complete a cycle, then it will be discarded because of the cycle property. If it does not, then it will be added to the MST by the cut property. |
| | |
| | The cycle property gives us insight into why the reverse delete algorithm must be true. When an edge e is deleted, it lies on a cycle c and since the edges are ordered and e is the first edge on the cycle that is encountered, then e must be the most costly edge on c and by the cycle property, it does not belong in a minimum spanning tree. |
| | |
| | Prim's algorithm can be implemented so that it runs in O(m log n) time for m edges and n nodes. This is plain due to its similarities with Dijkstra's algorithm which runs in the same time. Basically, using a heap-based priority queue gives O(log n) time for ExtractMin and ChangeKey, both of which run inside a m-time loop yielding a total run time of O(m log n). |
| | |
| | This section was quite dense to cut through due to the lengthy and notation-dependent proofs. The pictures helped somewhat but I did have to resort to class notes to demystify some of what was trying to be conveyed in the proofs. |
