############### #The Algorithm (In English): # 1) Pick any node. # 2) If it is unvisited, mark it as visited and recur on all its # adjacent nodes. # 3) Repeat until all the nodes are visited, or the node to be # searched is found. # The graph below (declared as a Python dictionary) # is from the linked website and is used for the sake of # testing the algorithm. Obviously, you will have your own # graph to iterate through. graph = { 'A' : ['B','C'], 'B' : ['D', 'E'], 'C' : ['F'], 'D' : [], 'E' : ['F'], 'F' : [] } visited = set() # Set to keep track of visited nodes. ################## # The Algorithm (In Code) def dfs(visited, graph, node): if node not in visited: print (node) visited.add(node) for neighbour in graph[node]: dfs(visited, graph, neighbour) # Driver Code to test in python yourself. # Note that when calling this, you need to # call the starting node. In this case it is 'A'. dfs(visited, graph, 'A') # NOTE: There are a few ways to do DFS, depending on what your # variables are and/or what you want returned. This specific # example is the most fleshed-out, yet still understandable, # explanation I could find.

dfs python

// 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); } }

depth first search

# 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) #

depth first search

#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); }

depth first search graph

Similar Code Examples