Depth-First Search
Explore a graph as deep as possible before backtracking.
Controls
Select a start node and run DFS.
Analysis
TimeO(V + E)
SpaceO(V)
Nodes Visited0
Edges Checked0
Order—
Visited: Current: Stack:
Current Step
Click Run DFS to start.
Python
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start)
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
return visited