dfs python

1# left to right, pre-order depth first tree search, iterative. O(n) time/space
2def depthFirstSearch(root):
3    st = [root]
4    while st:
5        current = st.pop()
6        print(current)
7        if current.right is not None: st.append(current.right) 
8        if current.left is not None: st.append(current.left)

1###############
2#The Algorithm (In English):
3
4# 1) Pick any node. 
5# 2) If it is unvisited, mark it as visited and recur on all its 
6#    adjacent nodes. 
7# 3) Repeat until all the nodes are visited, or the node to be 
8#    searched is found.
9
10
11# The graph below (declared as a Python dictionary)
12# is from the linked website and is used for the sake of
13# testing the algorithm. Obviously, you will have your own
14# graph to iterate through.
15graph = {
16    'A' : ['B','C'],
17    'B' : ['D', 'E'],
18    'C' : ['F'],
19    'D' : [],
20    'E' : ['F'],
21    'F' : []
22}
23
24visited = set() # Set to keep track of visited nodes.
25
26
27##################
28# The Algorithm (In Code)
29
30def dfs(visited, graph, node):
31    if node not in visited:
32        print (node)
33        visited.add(node)
34        for neighbour in graph[node]:
35            dfs(visited, graph, neighbour)
36            
37# Driver Code to test in python yourself.
38# Note that when calling this, you need to
39# call the starting node. In this case it is 'A'.
40dfs(visited, graph, 'A')
41
42# NOTE: There are a few ways to do DFS, depending on what your
43# variables are and/or what you want returned. This specific
44# example is the most fleshed-out, yet still understandable,
45# explanation I could find.

1#include <bits/stdc++.h>
2using namespace std;
3 
4
5class Graph {
6    int V; 
7 
8 
9    list<int>* adj;
10 
11  
12    void DFSUtil(int v, bool visited[]);
13 
14public:
15    Graph(int V);
16 
17    void addEdge(int v, int w);
18 
19  
20    void DFS(int v);
21};
22 
23Graph::Graph(int V)
24{
25    this->V = V;
26    adj = new list<int>[V];
27}
28 
29void Graph::addEdge(int v, int w)
30{
31    adj[v].push_back(w); 
32}
33 
34void Graph::DFSUtil(int v, bool visited[])
35{
36   
37    visited[v] = true;
38    cout << v << " ";
39 
40   
41    list<int>::iterator i;
42    for (i = adj[v].begin(); i != adj[v].end(); ++i)
43        if (!visited[*i])
44            DFSUtil(*i, visited);
45}
46 
47
48void Graph::DFS(int v)
49{
50   
51    bool* visited = new bool[V];
52    for (int i = 0; i < V; i++)
53        visited[i] = false;
54 
55 
56    DFSUtil(v, visited);
57}
58 
59
60int main()
61{
62  
63    Graph g(4);
64    g.addEdge(0, 1);
65    g.addEdge(0, 2);
66    g.addEdge(1, 2);
67    g.addEdge(2, 0);
68    g.addEdge(2, 3);
69    g.addEdge(3, 3);
70 
71    cout << "Following is Depth First Traversal"
72            " (starting from vertex 2) \n";
73    g.DFS(2);
74 
75    return 0;
76}