depth first search
# left to right, pre-order depth first tree search, iterative. O(n) time/space
def depthFirstSearch(root):
st = [root]
while st:
current = st.pop()
print(current)
if current.right is not None: st.append(current.right)
if current.left is not None: st.append(current.left)
3.83
6
DFS-iterative (G, s): //Where G is graph and s is source vertex
let S be stack
S.push( s ) //Inserting s in stack
mark s as visited.
while ( S is not empty):
//Pop a vertex from stack to visit next
v = S.top( )
S.pop( )
//Push all the neighbours of v in stack that are not visited
for all neighbours w of v in Graph G:
if w is not visited :
S.push( w )
mark w as visited
DFS-recursive(G, s):
mark s as visited
for all neighbours w of s in Graph G:
if w is not visited:
DFS-recursive(G, w)
Thank you!
6
0
3.57
7
// performs a depth first search (DFS)
// nodes are number from 1 to n, inclusive
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> adj; // adjacency list
// visited[v] = true if v has been visited by dfs
vector<bool> visited;
bool all_edges_are_directed = true;
void dfs(int v) {
// determines if dfs has been done on v
if(visited[v])
return;
visited[v] = true;
// write code here to do stuff with node v
// traverse nodes that are adjacent to v
for (int u: adj[v]){
dfs(u);
}
}
int main() {
int n; // number of vertices
int m; // number of edges
cin >> n >> m;
adj = vector<vector<int>>(n+1, vector<int>());
visited = vector<bool>(n+1, false);
for(int i = 0; i < m; ++i) {
// nodes a and b have an edge between them
int a, b;
cin >> a >> b;
if(all_edges_are_directed)
adj[a].push_back(b);
else {
adj[a].push_back(b);
adj[b].push_back(a);
}
}
// do depth first search on all nodes
for(int i = 1; i <= n; ++i){
dfs(i);
}
}
Thank you!
7
0
3.67
6
# HAVE USED ADJACENY LIST
class Graph:
def __init__(self,lst=None):
self.lst=dict()
if lst is None:
pass
else:
self.lst=lst
def find_path(self,start,end):
self.checklist={}
for i in self.lst.keys():
self.checklist[i]=False
self.checklist[start]=True
store,extra=(self.explore(start,end))
if store==False:
print('No Path Found')
else:
print(extra)
def explore(self,start,end):
while True:
q=[]
#print(self.checklist,q)
q.append(start)
flag=False
for i in self.lst[start]:
if i==end:
q.append(i)
return True,q
if self.checklist[i]:
pass
else:
flag=True
self.checklist[i]=True
q.append(i)
break
if flag:
store,extra=self.explore(q[-1],end)
if store==False:
q.pop()
if len(q)==0:return False
return self.explore(q[-1],end)
elif store==None:
pass
elif store==True:
q.pop()
q.extend(extra)
return True,q
else:
return False,None
def __str__(self):return str(self.lst)
if __name__=='__main__':
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]}
a=Graph(store)
a.find_path(1,11) # No Path Found
a.find_path(1,6)# [1, 4, 5, 6]
a.find_path(3,10) # [3, 2, 1, 4, 5, 6, 9, 10]
a.find_path(4,10)# [4, 5, 6, 9, 10]
print(a) #
Thank you!
6
0
4.11
9
#include<bits/stdc++.h>
using namespace std;
void addedge(vector<int>adj[],int u,int v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
void dfs_u(int u,vector<int>adj[],vector<bool>& visited)
{
visited[u]=true;
cout<<u<<" ";
int n=adj[u].size();
for(int i=0;i<n;i++)
{
if(visited[adj[u][i]]==false)
{
dfs_u(adj[u][i],adj,visited);
}
}
}
void dfs(vector<int>adj[],int v)
{
vector<bool> visited(v,false);
for(int i=0;i<v;i++)
{
if(visited[i]==false)
{
dfs_u(i,adj,visited);
}
}
}
int main()
{
int vertix;
cout<<"Enter the number of vertex :"<<endl;
cin>>vertix;
int edges;
cout<<"Enter the number of edges:"<<endl;
cin>>edges;
vector<int>graph_dfs[vertix];
int a,b;
cout<<"enter all the vertex pair that are connected:"<<endl;
for(int i=0;i<edges;i++)
{
cin>>a>>b;
addedge(graph_dfs,a,b);
}
cout<<"Depth first search view:"<<endl;
dfs(graph_dfs,vertix);
}
Thank you!
9
0
Are there any code examples left?
New code examples in category C++
-
C++ 2023-04-28 17:44:25
-
C++ 2022-03-27 19:20:39 lists occurrences of characters in the string c++
-
C++ 2022-03-27 18:00:14 variabili in c++
-
C++ 2022-03-27 17:10:08 repeat character n times c++
-
C++ 2022-03-27 15:50:07 delete an array c++
-
C++ 2022-03-27 15:40:12 C++ pointer to base class
-
C++ 2022-03-27 12:15:21 find the graph is minimal spanig tree or not
-
C++ 2022-03-27 11:30:15 multi variable assignment cpp
-
C++ 2022-03-27 11:05:17 c++ pi float
-
C++ 2022-03-27 10:20:12 why exceptions can lead to memory leaks