depth first search 2 Algorithm
Depth First Search 2 (DFS-2) algorithm is a variation of the standard Depth First Search (DFS) algorithm used in graph traversal and tree data structures. The main idea behind DFS-2 is to explore as deep as possible along a branch before backtracking, while also keeping track of the depth of the nodes. DFS-2 is particularly useful when dealing with problems that require exploring all possible paths in a graph or tree, where the depth of the solution is crucial. This algorithm can be implemented using either recursion or an explicit stack data structure to manage the depth of traversal.
In the DFS-2 algorithm, the process starts from a source node, and it traverses the adjacent nodes in depth-first order, marking each visited node. During the traversal, the algorithm maintains a depth counter to keep track of the current depth of the search. When the traversal reaches a dead-end or a target node, the algorithm backtracks to the previous nodes and continues the exploration from other unvisited adjacent nodes. This backtracking maintains the depth counter to ensure that the depth information is accurate throughout the search. The DFS-2 algorithm is highly efficient in solving problems where the depth of the solution is important, such as finding the shortest path in a maze, detecting cycles in a graph, or solving combinatorial problems.
#!/usr/bin/python
""" Author: OMKAR PATHAK """
class Graph:
def __init__(self):
self.vertex = {}
# for printing the Graph vertices
def printGraph(self):
print(self.vertex)
for i in self.vertex.keys():
print(i, " -> ", " -> ".join([str(j) for j in self.vertex[i]]))
# for adding the edge between two vertices
def addEdge(self, fromVertex, toVertex):
# check if vertex is already present,
if fromVertex in self.vertex.keys():
self.vertex[fromVertex].append(toVertex)
else:
# else make a new vertex
self.vertex[fromVertex] = [toVertex]
def DFS(self):
# visited array for storing already visited nodes
visited = [False] * len(self.vertex)
# call the recursive helper function
for i in range(len(self.vertex)):
if visited[i] is False:
self.DFSRec(i, visited)
def DFSRec(self, startVertex, visited):
# mark start vertex as visited
visited[startVertex] = True
print(startVertex, end=" ")
# Recur for all the vertices that are adjacent to this node
for i in self.vertex.keys():
if visited[i] is False:
self.DFSRec(i, visited)
if __name__ == "__main__":
g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)
g.printGraph()
print("DFS:")
g.DFS()
# OUTPUT:
# 0 -> 1 -> 2
# 1 -> 2
# 2 -> 0 -> 3
# 3 -> 3
# DFS:
# 0 1 2 3
