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