SHARE
TWEET

Depth-first Traversal with a Stack

a guest May 7th, 2017 2 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <stack>
  4. using namespace std;
  5.  
  6. /* The graphs used in the post's diagrams
  7.    have node indexing which starts at 1.
  8.    Since arrays and vectors in C++ use
  9.    0-based indexing, we subtract 1 from the
  10.    indices used in the input, and add 1
  11.    to the indices printed in the output. */
  12.  
  13. /* This graph can support 10000 nodes
  14.    numbered from 1 to 10000 inclusive. */
  15. bool visited[10000] = {false};
  16.  
  17. /* Each vector of integers represents
  18.    an individual node and the nodes it
  19.    is connected with. */
  20. vector< vector<int> > adjList;
  21.  
  22. int main () {
  23.     /* Take the number of nodes in the graph
  24.        and the number of edges in the graph as input. */
  25.     int nodeCount, edgeCount;
  26.     cin >> nodeCount >> edgeCount;
  27.  
  28.     /* Fill the adjacency list with unconnected nodes. */
  29.     for (int i = 0; i < nodeCount; i++) {
  30.         vector<int> node;
  31.         adjList.push_back (node);
  32.     }
  33.  
  34.     /* Add undirected edges to the adjacency list
  35.        using the input as a guide. */
  36.     for (int i = 0; i < edgeCount; i++) {
  37.         int n1, n2;
  38.         cin >> n1 >> n2;
  39.         n1--;
  40.         n2--;
  41.         adjList[n1].push_back (n2);
  42.         adjList[n2].push_back (n1);
  43.     }
  44.  
  45.     /* Take the index of the starting node. */
  46.     int startIndex;
  47.     cin >> startIndex;
  48.     startIndex--;
  49.  
  50.     /* First, push the index of the starting node
  51.        onto the traversal stack - this structure
  52.        holds the indices of the nodes which we
  53.        will go on to visit. */
  54.     stack<int> dfsStack;
  55.     dfsStack.push(startIndex);
  56.     while (!dfsStack.empty()) {
  57.         /* Take the index of the latest node which
  58.            was added to the stack, visit this node
  59.            and push the unvisited nodes adjacent
  60.            to this node onto the stack. */
  61.         int index = dfsStack.top();
  62.         dfsStack.pop();
  63.         visited[index] = true;
  64.         cout << index+1 << "\n";
  65.  
  66.         for (int i = 0; i < adjList[index].size(); i++) {
  67.             if (!visited[adjList[index][i]]) {
  68.                 dfsStack.push(adjList[index][i]);
  69.             }
  70.         }
  71.     }
  72.  
  73.     return 0;
  74. }
RAW Paste Data
Want to get better at C++?
Learn to code C++ in 2017
Pastebin PRO Summer Special!
Get 40% OFF on Pastebin PRO accounts!
Top