1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162 |
- //=======================================================================
- // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
- // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
- //
- // Distributed under the Boost Software License, Version 1.0. (See
- // accompanying file LICENSE_1_0.txt or copy at
- // http://www.boost.org/LICENSE_1_0.txt)
- //=======================================================================
- #include <boost/config.hpp>
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <utility>
- #include <boost/graph/adjacency_list.hpp>
- #include <boost/graph/connected_components.hpp>
- /*
- This example demonstrates the usage of the connected_components
- algorithm on a undirected graph. The example graphs come from
- "Introduction to Algorithms", Cormen, Leiserson, and Rivest p. 87
- (though we number the vertices from zero instead of one).
- Sample output:
- Total number of components: 3
- Vertex 0 is in component 0
- Vertex 1 is in component 0
- Vertex 2 is in component 1
- Vertex 3 is in component 2
- Vertex 4 is in component 0
- Vertex 5 is in component 1
- */
- using namespace std;
- int main(int , char* [])
- {
- using namespace boost;
- {
- typedef adjacency_list <vecS, vecS, undirectedS> Graph;
- Graph G;
- add_edge(0, 1, G);
- add_edge(1, 4, G);
- add_edge(4, 0, G);
- add_edge(2, 5, G);
-
- std::vector<int> component(num_vertices(G));
- int num = connected_components(G, &component[0]);
-
- std::vector<int>::size_type i;
- cout << "Total number of components: " << num << endl;
- for (i = 0; i != component.size(); ++i)
- cout << "Vertex " << i <<" is in component " << component[i] << endl;
- cout << endl;
- }
- return 0;
- }
|