Prims Algorithm

Prims Algorithm
Runtime	V*Extract_min + V + E + E update Heap: O(E log V) Array: O(V^2)
Class	Minimum_Spanning_Tree Graph Algorithm Greedy Algorithm

Approach: Greedy

The approach is to try to add the smallest edges as long as they do not create a cycle; add an edge to the tree that is minimum across the cut of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} vs. $V-T$

Given the MST of $V_{n-m}=v_{1},v_{2},\ldots ,v_{n-m}$, the MST of $V$ should be that of $V_{n-1}$ plus the edge that connects to $v_{n}$ that is the shortest.

$OPT(n)=OPT(n-1)+min((v_{i},v_{n})\in E)$

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

Greeedy strategy: Let the greedy choice be the edge that is smallest that crosses the cut between $A$ and $V-A$.

Name greedy choice: let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r \rightarrow x} be the smallest edge that crosses the cut from Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A = r} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V - r} .

Given an optimal solution with (r,y), prove that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A = OPT - (r,y) + (r, x)} is still optimal.

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} is still a tree since there is no cycles created.

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w(r,y) \geq w(r,x)} due to its properties as the greedy choice.

Therefore, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} must be optimal.