Depth First Search use case.
A graph is a data structure that includes a set of vertices and edges. Graph traversing means a visit to each vertex of the graph, going to all the vertices of the graph without going into a loop. Depth First Search (DFS) is one of the ways to traverse the graph visiting all the vertices and edges.
Python Knowledge Base: Make coding great again.
- Updated:
2024-11-20 by Andrey BRATUS, Senior Data Analyst.
Depth First Search Python code:
Depth First Search code result:
In depth-first search the LIFO (Last In First Out) principle stack data structure is used. The algorithm starts at the root node (some arbitrary node), then keeps on exploring or visiting vertices till we reach a dead-end. Visited nodes are marked, then traversing all the adjacent and unmarked nodes and calling the recursive function with the index of the adjacent node. Depth-first search is considered as a non-optimal solution. Originally a depth-first search was used as a strategy for solving mazes.
graph1 = {'0': set(['1', '2']),
'1': set(['0', '3', '4']),
'2': set(['0']),
'3': set(['1']),
'4': set(['2', '3'])}
def dfs(graph, node, visited):
if node not in visited:
visited.append(node)
for n in graph[node]:
dfs(graph,n, visited)
return visited
visited = dfs(graph1,'0', [])
print(visited)
OUT: ['0', '2', '1', '3', '4']