Example 1: DFS in c++
#include <bits/stdc++.h>
using namespace std;
class Graph {
int V;
list<int>* adj;
void DFSUtil(int v, bool visited[]);
public:
Graph(int V);
void addEdge(int v, int w);
void DFS(int v);
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
}
void Graph::DFSUtil(int v, bool visited[])
{
visited[v] = true;
cout << v << " ";
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFSUtil(*i, visited);
}
void Graph::DFS(int v)
{
bool* visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
DFSUtil(v, visited);
}
int main()
{
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
cout << "Following is Depth First Traversal"
" (starting from vertex 2) \n";
g.DFS(2);
return 0;
}
Example 2: dfs python
###############
#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.
Example 3: 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) #