• API
• FAQ
• Tools
• Trends
• Archive
daily pastebin goal
52%
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. */
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;
32.     }
33.
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--;
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++) {