SHARE
TWEET

Depth-first Traversal with Recursion

a guest May 7th, 2017 1 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. /* The graphs used in the post's diagrams
  6.    have node indexing which starts at 1.
  7.    Since arrays and vectors in C++ use
  8.    0-based indexing, we subtract 1 from the
  9.    indices used in the input, and add 1
  10.    to the indices printed in the output. */
  11.  
  12. /* This graph can support 10000 nodes
  13.    numbered from 1 to 10000 inclusive. */
  14. bool visited[10000] = {false};
  15.  
  16. /* Each vector of integers represents
  17.    an individual node and the nodes it
  18.    is connected with. */
  19. vector< vector<int> > adjList;
  20.  
  21. /* Every time 'Recur' is called, the node
  22.    at index is visited. We then recur for each
  23.    unvisited node which is connected
  24.    to the node at index. */
  25. void Recur (int index) {
  26.     cout << index+1 << "\n";
  27.     visited[index] = true;
  28.     for (int i = 0; i < adjList[index].size(); i++) {
  29.         if (!visited[adjList[index][i]]) {
  30.             Recur(adjList[index][i]);
  31.         }
  32.     }
  33. }
  34.  
  35. int main () {
  36.     /* Take the number of nodes in the graph
  37.        and the number of edges in the graph as input. */
  38.     int nodeCount, edgeCount;
  39.     cin >> nodeCount >> edgeCount;
  40.  
  41.     /* Fill the adjacency list with unconnected nodes. */
  42.     for (int i = 0; i < nodeCount; i++) {
  43.         vector<int> node;
  44.         adjList.push_back (node);
  45.     }
  46.  
  47.     /* Add undirected edges to the adjacency list
  48.        using the input as a guide. */
  49.     for (int i = 0; i < edgeCount; i++) {
  50.         int n1, n2;
  51.         cin >> n1 >> n2;
  52.         n1--;
  53.         n2--;
  54.         adjList[n1].push_back (n2);
  55.         adjList[n2].push_back (n1);
  56.     }
  57.  
  58.     /* Finally, take the index of the starting node,
  59.        and begin the depth-first traversal at this index. */
  60.     int startIndex;
  61.     cin >> startIndex;
  62.     startIndex--;
  63.     Recur (startIndex);
  64.  
  65.     return 0;
  66. }
RAW Paste Data
Top