main.cpp

在boost基础上实现 对图的最小生成树实现

/*
 * filename: main.cpp
 * src: d:\vc71\boost-1_31_0\work\src\kruskal_mst\
 * date: 29/8 2004
 * function: demonstrate the use of the kruskal minimum spanning tree algorithm
 * kru_mst.hpp the implementation of the kruskal mst algorithm
 * output is: 
	g has 8 edges
	(0,2)'s weight is 1
	(3,4)'s weight is 1
	(4,0)'s weight is 1
	(1,3)'s weight is 1
	(4,1)'s weight is 1
	(1,4)'s weight is 2
	(2,3)'s weight is 3
	(2,1)'s weight is 7
	mst is
	(0,2)'s weight is 1
	(3,4)'s weight is 1
	(4,0)'s weight is 1
	(1,3)'s weight is 1
 * 
 * */
#include <boost/graph/adjacency_list.hpp>
#include "kru_mst.hpp"

using namespace std;
using namespace boost;

void main(){
	typedef pair<int, int> E;
 	E edge_array[] = { E(0, 2), E(1, 3), E(1, 4), E(2, 1), E(2, 3),
	    E(3, 4), E(4, 0), E(4, 1)
	  };
	int weights[] = { 1, 1, 2, 7, 3, 1, 1, 1 };
	int N = 5;
	typedef adjacency_list<vecS, vecS, undirectedS, no_property, property<edge_weight_t, int> > graph_t;
	graph_t g(N);
	typedef graph_traits<graph_t>::edge_descriptor Edge;
	/* key_type is Edge,value_type is int */
	property_map<graph_t, edge_weight_t>::type w_map = get(edge_weight, g); 
	/* now we have constructed the graph_t g */
	for(std::size_t j = 0; j < sizeof(edge_array)/sizeof(E); j++){
		Edge e;
		bool inserted;
		tie(e, inserted) = add_edge(edge_array[j].first, edge_array[j].second, g);
		w_map[e] = weights[j];
	}
	cout << "g has " << num_edges(g) << " edges" << endl;
	vector< Edge > spanning_tree_edges; 
	kru_mst(g, back_inserter(spanning_tree_edges));
	cout << "mst is " << endl;
	for(vector<Edge>::iterator i = spanning_tree_edges.begin(); i != spanning_tree_edges.end(); ++i)
		cout << "(" << source(*i, g) << "," << target(*i, g) << ")'s weight is " << get(edge_weight, g)[*i] << endl;
}