
%\noindent \textbf{Minimum Spanning Tree}
\subsection{Minimum Spanning Tree}

Problem: Given a \textsl{connected, undirected} graph, $G$, find the
minimum spanning tree for $G$.  The minimal spanning tree, $T$,
is a connected graph with no cycles such that the vertices of $T$
is the same as $G$.  The vertices in $T$ are connected by exactly
one path.  

%Prim's algorithm:
%\begin{lstlisting}
%Input: graph G with vertices V and edges E
%Set E' = {}, V' = {n}, where n is arbitrary
%    vertex from V
%until V' = V
%  pick edge (u, v) from E such that u is in V'
%     and v is not in V', and edge (u, v) has
%     minimal weight
%  V' = V' + v
%  E' = E' + (u, v)
%
%Output: V', E' form the minimal spanning tree
%\end{lstlisting}


Kruskal's algorithm:

\lstset{language=C++}
\begin{lstlisting}
using namespace std;

typedef int node;
typedef vector<node> nodes;
typedef pair<node,node> edge;

nodes p; // union/find parents
nodes rank; // union/find rank

template<class K, class V>
pair<V,K> invert(pair<K,V>& p) {
    return make_pair(p.second, p.first);
}

// map to inverted vector
template<class K, class V>
vector<pair<V,K> > invert(map<K,V>& m) {
    vector< pair<V,K> > v;
    FOREACH(i, m)
        v.push_back(invert(*i));
    return v;
}

map<edge,int> G;

int find(int);
int find_union(int,int);

void Kruskal(int V, vector<edge>& T) {
    vector<pair<int,edge> > Q = invert(G);
    sort(ALL(Q));

    int i = 0;
    while(T.size() < V-1) {
        edge e = Q[i++].second;
        int Cv = find(e.first);
        int Cu = find(e.second);
        if(Cv != Cu) {
            T.push_back(e);
            find_union(Cv, Cu);
        }
    }
}

int main() {
    while(true) {
        int V,E,u,v,w;
        cin >> V >> E;
        if(V == 0) break;

        G.clear();
        p = nodes(V);
        rank = nodes(V,0);
        for(int i = 0; i < V; ++i) {
            p[i] = i;
        }

        for(int i=0; i < E; ++i) {
            cin >> u >> v >> w;
            G[edge(u,v)] = w;
        }

        vector<edge> T;
        Kruskal(V, T);

        // do something with MST T

        return 0;
    }
}

int find(int x) {
    if(p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}

int find_union(int x, int y) {
    int xr = find(x);
    int yr = find(y);
    int xrr = rank[xr];
    int yrr = rank[yr];
         if(xrr > yrr) p[yr] = xr;
    else if(xrr < yrr) p[xr] = yr;
    else if(xr != yr) {
        p[yr] = xr;
        rank[xr] = xrr + 1;
    }
}
\end{lstlisting}
\normalsize

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "../ref-doc"
%%% End:
