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 $T$ vs. $V-T$. Unlike Dijkstra's algorithm, the weight of the crossing edge is directly considered (as opposed to the distance from the source node).

Given the MST 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 V_{n - m} = v_1, v_2, \ldots, v_{ n - m} } , the MST 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 V} should be that 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 V_{n-1}} plus the edge that connects to 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_n} that is the shortest.

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 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

Initialization takes O(V). Walk through is O(V + E).

During the walk through, the minimum edge is extracted V times, and the edge priority queue is updated E times. Depending on the data structure used, the runtime is different.

• For an array, the extraction takes O(V) and the update takes O(1). The overall runtime is O(V^2)
• For a heap, the extraction takes O(logV) and the update takes O(logV). The overall runtime is O(E logV).

As such, priority queue is slower than array when the graph is dense (where E approaches V^2).

Proof: Greedy

Greeedy strategy: Let the greedy choice be the edge that is smallest that crosses the cut between 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} 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 - 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.