Prims Algorithm: Difference between revisions

From Rice Wiki
No edit summary
No edit summary
Line 36: Line 36:
minimum, and the tree is spanning.
minimum, and the tree is spanning.


Let <math>(x,y)</math> be a leaf edge in the tree.
Consider <math>(x,y)</math>, where X is a leaf node.
 
Prove that <math>A = OPT - (x, y)</math> is a MST for the subproblem
<math>G - X</math>




[[Category:Algorithms]]
[[Category:Algorithms]]

Revision as of 01:18, 8 March 2024

Approach: Greedy

See Minimum_Spanning_Tree

Implementation

for each u in V:
    key[u] = infinity   // cost array
    pi[u] = infinity    // from array
Q = new PriorityQueue(V)
key[root] = 0
while Q is not empty:
    u = extractMin(Q)
    # Reduce nodes
    for v in adj[u]:
        if v in Q and w[u,v] < key[v]:
            key[v] = w[u,v]

Analysis

Priority queue is slower than array when the graph is dense, so sometimes it's better to use Dijsktra's algorithm.

Proof: Greedy

Suboptimality

Given MST tree for the graph G

where the number of edges is , the weight of edges is minimum, and the tree is spanning.

Consider , where X is a leaf node.

Prove that is a MST for the subproblem