depth first search Algorithm
Depth First Search (DFS) is a graph traversal algorithm that explores the vertices of a graph by traversing as deep as possible along each branch before backtracking. The basic idea behind the algorithm is to visit a vertex, mark it as visited, and recursively explore its adjacent unvisited vertices. The process continues until all the vertices in the graph have been visited. DFS can be implemented using recursion or an explicit stack data structure, making it highly versatile for solving a range of problems, from finding connected components in a graph to solving puzzles and games.
The DFS algorithm starts at an initial vertex and marks it as visited. It then selects an adjacent unvisited vertex and moves to that vertex, marking it as visited as well. This process is repeated until there are no more unvisited adjacent vertices, at which point the algorithm backtracks to the previous vertex and continues to explore other adjacent vertices. The traversal continues until all vertices have been visited, ensuring that the entire graph has been explored. DFS is particularly useful in solving problems that require searching through a large solution space, as it can efficiently explore and eliminate possibilities until the desired solution is found.
"""The DFS function simply calls itself recursively for every unvisited child of
its argument. We can emulate that behaviour precisely using a stack of iterators.
Instead of recursively calling with a node, we'll push an iterator to the node's
children onto the iterator stack. When the iterator at the top of the stack
terminates, we'll pop it off the stack.
Pseudocode:
all nodes initially unexplored
mark s as explored
for every edge (s, v):
if v unexplored:
DFS(G, v)
"""
from typing import Set, Dict
def depth_first_search(graph: Dict, start: str) -> Set[int]:
"""Depth First Search on Graph
:param graph: directed graph in dictionary format
:param vertex: starting vectex as a string
:returns: the trace of the search
>>> G = { "A": ["B", "C", "D"], "B": ["A", "D", "E"],
... "C": ["A", "F"], "D": ["B", "D"], "E": ["B", "F"],
... "F": ["C", "E", "G"], "G": ["F"] }
>>> start = "A"
>>> output_G = list({'A', 'B', 'C', 'D', 'E', 'F', 'G'})
>>> all(x in output_G for x in list(depth_first_search(G, "A")))
True
>>> all(x in output_G for x in list(depth_first_search(G, "G")))
True
"""
explored, stack = set(start), [start]
while stack:
v = stack.pop()
# one difference from BFS is to pop last element here instead of first one
for w in graph[v]:
if w not in explored:
explored.add(w)
stack.append(w)
return explored
G = {
"A": ["B", "C", "D"],
"B": ["A", "D", "E"],
"C": ["A", "F"],
"D": ["B", "D"],
"E": ["B", "F"],
"F": ["C", "E", "G"],
"G": ["F"],
}
if __name__ == "__main__":
import doctest
doctest.testmod()
print(depth_first_search(G, "A"))
