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// performs a depth first search (DFS)
2// nodes are number from 1 to n, inclusive
3#include <bits/stdc++.h>
4using namespace std;
5
6
7vector<vector<int>> adj; // adjacency list
8// visited[v] = true if v has been visited by dfs
9vector<bool> visited;
10
11bool all_edges_are_directed = true;
12
13void dfs(int v) {
14 // determines if dfs has been done on v
15 if(visited[v])
16 return;
17 visited[v] = true;
18
19 // write code here to do stuff with node v
20
21 // traverse nodes that are adjacent to v
22 for (int u: adj[v]){
23 dfs(u);
24 }
25}
26
27int main() {
28 int n; // number of vertices
29 int m; // number of edges
30 cin >> n >> m;
31 adj = vector<vector<int>>(n+1, vector<int>());
32 visited = vector<bool>(n+1, false);
33
34 for(int i = 0; i < m; ++i) {
35 // nodes a and b have an edge between them
36 int a, b;
37 cin >> a >> b;
38
39 if(all_edges_are_directed)
40 adj[a].push_back(b);
41 else {
42 adj[a].push_back(b);
43 adj[b].push_back(a);
44 }
45 }
46
47 // do depth first search on all nodes
48 for(int i = 1; i <= n; ++i){
49 dfs(i);
50 }
51}
1#include<bits/stdc++.h>
2using namespace std;
3void addedge(vector<int>adj[],int u,int v)
4{
5 adj[u].push_back(v);
6 adj[v].push_back(u);
7}
8void dfs_u(int u,vector<int>adj[],vector<bool>& visited)
9{
10 visited[u]=true;
11 cout<<u<<" ";
12 int n=adj[u].size();
13 for(int i=0;i<n;i++)
14 {
15 if(visited[adj[u][i]]==false)
16 {
17 dfs_u(adj[u][i],adj,visited);
18 }
19 }
20}
21void dfs(vector<int>adj[],int v)
22{
23 vector<bool> visited(v,false);
24 for(int i=0;i<v;i++)
25 {
26 if(visited[i]==false)
27 {
28 dfs_u(i,adj,visited);
29 }
30 }
31}
32int main()
33{
34 int vertix;
35 cout<<"Enter the number of vertex :"<<endl;
36 cin>>vertix;
37 int edges;
38 cout<<"Enter the number of edges:"<<endl;
39 cin>>edges;
40 vector<int>graph_dfs[vertix];
41 int a,b;
42 cout<<"enter all the vertex pair that are connected:"<<endl;
43 for(int i=0;i<edges;i++)
44 {
45 cin>>a>>b;
46 addedge(graph_dfs,a,b);
47 }
48 cout<<"Depth first search view:"<<endl;
49 dfs(graph_dfs,vertix);
50}
51
1 DFS-iterative (G, s): //Where G is graph and s is source vertex
2 let S be stack
3 S.push( s ) //Inserting s in stack
4 mark s as visited.
5 while ( S is not empty):
6 //Pop a vertex from stack to visit next
7 v = S.top( )
8 S.pop( )
9 //Push all the neighbours of v in stack that are not visited
10 for all neighbours w of v in Graph G:
11 if w is not visited :
12 S.push( w )
13 mark w as visited
14
15
16 DFS-recursive(G, s):
17 mark s as visited
18 for all neighbours w of s in Graph G:
19 if w is not visited:
20 DFS-recursive(G, w)
1# HAVE USED ADJACENY LIST
2class Graph:
3 def __init__(self,lst=None):
4 self.lst=dict()
5 if lst is None:
6 pass
7 else:
8 self.lst=lst
9 def find_path(self,start,end):
10 self.checklist={}
11 for i in self.lst.keys():
12 self.checklist[i]=False
13 self.checklist[start]=True
14 store,extra=(self.explore(start,end))
15 if store==False:
16 print('No Path Found')
17 else:
18 print(extra)
19 def explore(self,start,end):
20 while True:
21 q=[]
22 #print(self.checklist,q)
23 q.append(start)
24 flag=False
25 for i in self.lst[start]:
26 if i==end:
27 q.append(i)
28 return True,q
29 if self.checklist[i]:
30 pass
31 else:
32 flag=True
33 self.checklist[i]=True
34 q.append(i)
35 break
36 if flag:
37 store,extra=self.explore(q[-1],end)
38 if store==False:
39 q.pop()
40 if len(q)==0:return False
41 return self.explore(q[-1],end)
42 elif store==None:
43 pass
44 elif store==True:
45 q.pop()
46 q.extend(extra)
47 return True,q
48 else:
49 return False,None
50 def __str__(self):return str(self.lst)
51if __name__=='__main__':
52 store={1: [2, 3, 4], 2: [3, 1], 3: [2, 1], 4: [5, 8, 1], 5: [4, 6, 7], 6: [5, 7, 9, 8], 7: [5, 6], 8: [4, 6, 9], 9: [6, 8, 10], 10: [9],11:[12,13]}
53 a=Graph(store)
54 a.find_path(1,11) # No Path Found
55 a.find_path(1,6)# [1, 4, 5, 6]
56 a.find_path(3,10) # [3, 2, 1, 4, 5, 6, 9, 10]
57 a.find_path(4,10)# [4, 5, 6, 9, 10]
58 print(a) #