fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. // data structure to store graph edges
  6. struct Edge {
  7.     int src, dest;
  8. };
  9.  
  10. // class to represent a graph object
  11. class Graph
  12. {
  13. public:
  14.     // construct a vector of vectors to represent adjacency list in C++
  15.     vector<vector<int>> adjList;
  16.  
  17.     // Graph Constructor
  18.     Graph(const vector<Edge> &edges, int N)
  19.     {
  20.         // resize the vector to N elements of type vector<int>
  21.         adjList.resize(N);
  22.  
  23.         // add edges to the directed graph
  24.         for (auto &edge: edges) {
  25.             adjList[edge.src].push_back(edge.dest);
  26.         }
  27.     }
  28. };
  29.  
  30. // Utility function to print a vector
  31. void printPath(const vector<int> &path)
  32. {
  33.     for (int i: path)
  34.         cout << i << ' ';
  35.     cout << endl;
  36. }
  37.  
  38. // Function to perform DFS traversal in a directed graph to find the
  39. // complete path between source and destination vertices
  40. void printAllPaths(const Graph &graph, int src, int dest,
  41.         vector<bool> &discovered, vector<int> &path)
  42. {
  43.     // mark current node as discovered
  44.     discovered[src] = true;
  45.  
  46.     // include current node in the path
  47.     path.push_back(src);
  48.  
  49.     // print the complete path if destination vertex is found
  50.     if (src == dest) {
  51.         printPath(path);
  52.     }
  53.  
  54.     // do for every edge (src -> i)
  55.     for (int i: graph.adjList[src])
  56.     {
  57.         // proceed if u is not discovered
  58.         if (!discovered[i]) {
  59.             printAllPaths(graph, i, dest, discovered, path);
  60.         }
  61.     }
  62.  
  63.     // backtrack: remove current node from the path & mark it as not discovered
  64.     path.pop_back();
  65.     discovered[src] = false;
  66. }
  67.  
  68. int main()
  69. {
  70.     // vector of graph edges as per above diagram
  71.     vector<Edge> edges = {
  72.         {0, 3}, {1, 0}, {1, 2}, {1, 4}, {2, 7}, {3, 4},
  73.         {3, 5}, {4, 3}, {4, 6}, {5, 6}, {6, 7}
  74.     };
  75.  
  76.     // Number of nodes in the graph (labelled from 0 to N-1)
  77.     int N = 8;
  78.  
  79.     // create a graph from given edges
  80.     Graph graph(edges, N);
  81.  
  82.     // stores vertex is discovered or not
  83.     vector<bool> discovered(N);
  84.  
  85.     // source and destination vertex
  86.     int src = 0, dest = 7;
  87.  
  88.     // vector to store the complete path between source and destination
  89.     vector<int> path;
  90.  
  91.     // perform DFS traversal from the source vertex to check the connectivity
  92.     // and print all paths from the source vertex to the destination vertex
  93.     printAllPaths(graph, src, dest, discovered, path);
  94.  
  95.     return 0;
  96. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 3 4 6 7 
0 3 5 6 7
https://ideone.com/RfcWg8
Print all paths between given vertices in a directed graph
language:
C++ 4.3.2 (gcc-4.3.2)
created:
5 years ago
visibility:
secret

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!