How to create a C++ Boost undirected graph and traverse it in depth first search (DFS) order?
On undirected graphs, DFS(u) visits all vertices in CC(u), and the DFS-tree obtained is a spanning tree of G. Analysis: DFS(s) runs in O(|Vc|+|Ec|), where Vc,Ec are the number of vertices and edges in CC(s) (reachable from s, for directed graphs).
Depth-first search is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.
DFS(Depth First Search) uses Stack data structure.
// Boost DFS example on an undirected graph. // Create a sample graph, traverse its nodes // in DFS order and print out their values. #include <boost/graph/adjacency_list.hpp> #include <boost/graph/depth_first_search.hpp> #include <iostream> using namespace std; typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS> MyGraph; typedef boost::graph_traits<MyGraph>::vertex_descriptor MyVertex; class MyVisitor : public boost::default_dfs_visitor { public: void discover_vertex(MyVertex v, const MyGraph& g) const { cerr << v << endl; return; } }; int main() { MyGraph g; boost::add_edge(0, 1, g); boost::add_edge(0, 2, g); boost::add_edge(1, 2, g); boost::add_edge(1, 3, g); MyVisitor vis; boost::depth_first_search(g, boost::visitor(vis)); return 0; }
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With