fork(3) download
copy 
  1. #include <unordered_map>
  2. #include <unordered_set>
  3. #include <stack>
  4. #include <queue>
  5. #include <iostream>
  6. #include <string>
  7. #include <sstream>
  8.  
  9. template< typename T, typename REF = T >
  10. using adjacency_list_t = std::unordered_map< T, std::unordered_set<REF> > ;
  11.  
  12. using adjacency_list = adjacency_list_t<int> ;
  13.  
  14. // input of pairs of adjacent vertices of a directed graph
  15. // 1 7 => edge from 1 -------> 7
  16. // 2 7 => edge from 2 -------> 7
  17. // 1 5 => edge from 1 -------> 5
  18. // etc.
  19.  
  20. adjacency_list make_adjacency_list( std::istream& stm )
  21. {
  22.     adjacency_list graph ;
  23.     int a, b ;
  24.     while( stm >> a >> b ) { graph[a].insert(b) ; graph[b] ; }
  25.     return graph ;
  26. }
  27.  
  28. template< typename STACK_OR_QUEUE, typename FN_NEXT >
  29. bool graph_search( const adjacency_list& graph, int start, int target, FN_NEXT next )
  30. {
  31.     STACK_OR_QUEUE stk_or_queue ;
  32.     std::unordered_set<int> visited ;
  33.     stk_or_queue.push(start) ;
  34.     while( !stk_or_queue.empty() )
  35.     {
  36.         int id =  next(stk_or_queue) ;
  37.         std::cout << id << ' ' ;
  38.         visited.insert(id) ;
  39.         if( id == target ) { std::cout << " <= target\n" ; return true ; }
  40.         else
  41.         {
  42.             stk_or_queue.pop() ;
  43.             auto iter = graph.find(id) ;
  44.             if( iter != graph.end() )
  45.                 for( auto& n : iter->second )
  46.                     if( visited.find(n) == visited.end() ) stk_or_queue.push(n) ;
  47.         }
  48.     }
  49.     std::cout << "  could not find target\n" ;
  50.     return false ;
  51. }
  52.  
  53. bool depth_first_search( const adjacency_list& graph, int start, int target )
  54. {
  55.     using stack = std::stack<int> ;
  56.     return graph_search<stack>( graph, start, target, []( stack& s ) { return s.top() ; } ) ;
  57. }
  58.  
  59. bool breadth_first_search( const adjacency_list& graph, int start, int target )
  60. {
  61.     using queue = std::queue<int> ;
  62.     return graph_search<queue>( graph, start, target, []( queue& q ) { return q.front() ; } ) ;
  63. }
  64.  
  65. int main()
  66. {
  67.     const std::string str = "1 2   1 7   1 8   2 3   2 6   2 10  3 4   3 5   3 11   "
  68.                             "6 10   6 12  8 9   8 12   9 10   9 11   11 7   12 5" ;
  69.     std::istringstream stm(str) ;
  70.     const adjacency_list graph = make_adjacency_list(stm) ;
  71.  
  72.     std::cout << "DFS 1 to 5 => " ; depth_first_search( graph, 1, 5 ) ;
  73.     std::cout << "BFS 1 to 5 => " ; breadth_first_search( graph, 1, 5 ) ;
  74.     std::cout << "DFS 1 to 12 => " ; depth_first_search( graph, 1, 12 ) ;
  75.     std::cout << "BFS 1 to 12 => " ; breadth_first_search( graph, 1, 12 ) ;
  76. }
  77.  
Success #stdin #stdout 0s 2996KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
DFS 1 to 5 => 1 2 3 4 5  <= target
BFS 1 to 5 => 1 8 7 2 12 9 10 6 3 5  <= target
DFS 1 to 12 => 1 2 3 4 5 11 7 6 10 12  <= target
BFS 1 to 12 => 1 8 7 2 12  <= target
https://ideone.com/vcUBkM
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!