Graphs
Graph traversal algorithms and techniques for connected networks.
Graph BFS (Breadth-First Search)
Level-by-level traversal of a graph using a queue.
How it works
BFS explores all neighbors at the current depth before moving to the next level. It uses a queue to track nodes to visit. BFS finds the shortest path in unweighted graphs and is useful for level-order traversals. It can detect connected components and bipartiteness.
Time Complexity
O(V + E)
Space Complexity
O(V)
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
result = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return resultGraph DFS (Depth-First Search)
Deep traversal of a graph using recursion or stack.
How it works
DFS explores as far as possible along each branch before backtracking. It can use recursion (call stack) or an explicit stack. DFS detects cycles, finds connected components, and topologically sorts DAGs. It's useful for puzzles and maze solving.
Time Complexity
O(V + E)
Space Complexity
O(V)
def dfs(graph, node, visited, result):
visited.add(node)
result.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(graph, neighbor, visited, result)
return result
visited = set()
result = dfs(graph, start, visited, [])