$\mathrm{minimize}w(T)=\sum _{(u,v)\in E\text{'}}w(u,v),\mathrm{where}E\text{'}\subseteq E$ |
GENERIC-MST $(G,w)$Evidently, the gist of the MST algorithm is finding an edge $\u27e8u,v\u27e9\in E-A$ that has the minimum weight and that adding this edge to $A$ does not result in a cycle in $A$. To describe how this is done, the following concepts are introduced (see Figure 1):
1 $A$ $\leftarrow $ $\varnothing $
2 while the edges in $A$ do not form an MST
3 do find an edge $(u,v)\in E-A$ that has the
. minimum weight and this edge, along with the
. edges in $A$, does not form a cycle.
4 $A$ $\leftarrow $ $A\cup \{(u,v)\}$
5 return $A$
KRUSKAL-MST $(G,w)$The sorting of edges will take $O(|E|\mathrm{log}|E|)$ time. Next for each edge, disjoint-set functions are called. This requires $O(|E|\mathrm{log}|V|)$ time. Since $|E|$ is at most $|V{|}^{2}$ and $\mathrm{log}|V{|}^{2}=2\mathrm{log}|V|$, $O(|E|\mathrm{log}|E|)=O(|E|\mathrm{log}|V|)$. The running time for Kruskal's algorithm is thus $O(|E|\mathrm{log}|V|)$. One heuristic that can be used to improve Kruskal's runtime is to maintain a count of the number of edges in $A$. The reason for this is that a tree spanning all the vertices in $V$ will have $|V|-1$ edges. Thus, if $|A|=|V|-1$, the algorithm can safely terminate. This heuristic will tend to be more effective the denser a graph gets. Figure 2 illustrates the running of Kruskal's algorithm.
1 $A$ $\leftarrow $ $\varnothing $
2 for each vertex $v\in V$
3 do MAKE-SET $(v)$
4 Sort the edges of $E$ by nondecreasing weight $w$
5 for each edge $(u,v)\in E$ in order by nondecreading weight
6 do if FIND-SET $(u)$ $\ne $ FIND-SET $(v)$
7 then $A$ $\leftarrow $ $A\cup \{(u,v)\}$
8 UNION $(u,v)$
9 return $A$
PRIM-MST $(G,w,r)$The performance of Prim's algorithm depends on how the priority queue $Q$ is implemented.
1 $Q$ $\leftarrow $ $V$
2 for each $u\in Q$
3 do $\text{key}[u]$ $\leftarrow $ $\infty $
4 $\text{key}[r]$ $\leftarrow $ $0$
5 $p[r]$ $\leftarrow $ NIL
6 while $Q\ne \varnothing $
7 do $u$ $\leftarrow $ EXTRACT-MIN $(Q)$
8 for each $v\in \text{Adj}[u]$
9 do if $v\in Q$ and $w(u,v)<\text{key}[v]$
10 then $p[v]$ $\leftarrow $ $u$
11 $\text{key}[v]$ $\leftarrow $ $w(u,v)$