kruskal_mst.h File Reference

Go to the source code of this file.

Functions
template<typename OutputIter >
OutputIter	kruskal_mst (graph &G, OutputIter res)

Function Documentation

template<typename OutputIter >

OutputIter kruskal_mst	(	graph &	G,
		OutputIter	res
	)

                                                 { 

    /*
        The 
    */
    
    disjoint_sets<graph::vertex_t> sets;
    
    // vertex iterator
    for(graph::vertex_iter it = G.vbegin(); it != G.vend(); it++) {
        sets.make_set(*it);
    }
    
    std::list<Graph::edge_type> edges;
    
    // edge iterator
    for(graph::edge_iter it = G.ebegin(); it != G.eend(); it++)
        edges.push_back(*it);
        
    edges.sort();
    
    // expand and merge the components iteratively
    for(graph::edge_type edge : edges) {
    
        graph::vertex_type u = edge.either(), v = edge.other();
        
        if(sets.find(u) != sets.find(v)) {
            // Different component
            sets.unite(u, v);
            res++ = edge;
        }
    }
    
    return res;
}