Depth-First Search Algorithm in Details in Python

Depth-First Search Algorithm in Details in Python

Image for post

Image for post

Image for post

Image for post

Image for post

Image for post

Image for post

Image for post

Image for post

Image for post

Image for post

Image for post

Image for post

g = {
'u': ['v', 'x'],
'v': ['y'],
'y': ['x'],
'x': ['v'],
'w': ['y', 'z'],
'z': ['z']
}
class depth_first:
def __init__(self):
self.visited = []
def dfs(self, graph):        
for ver in graph:
if ver not in self.visited:
self.dfs_visit(graph, ver)
return self.visited
def dfs_visit(self, graph, vertex):
if vertex not in self.visited:
self.visited.append(vertex)
for nb in g[vertex]:
self.dfs_visit(g, nb)
class depth_first:
def __init__(self):
self.visited = []
def dfs(self, graph):
for ver in graph:
if ver not in self.visited:
self.dfs_visit(graph, ver)
return self.visited

def dfs_visit(self, graph, vertex):
if vertex not in self.visited:
self.visited.append(vertex)
for nb in g[vertex]:
self.dfs_visit(g, nb)

d = depth_first()
print(d.dfs(g))
['u', 'v', 'y', 'x', 'w', 'z']
def dfs(graph, vertex, path=[]):
path += [vertex]
for n in graph[vertex]:
if n not in path:
path = dfs(graph, n, path)
return path
print(dfs(g, 'u'))
['u', 'v', 'y', 'x']

 

#programming #pythonprogramming #algorithms #graphalgorithm #depthfirstsearch #python

Leave a Reply

Close Menu