Explore networks systematically, either by diving deep or rippling outward.
A Graph is just a set of Nodes (Vertices) and connections between them (Edges). To explore it, we have two main strategies:
Depth-First Search (DFS) acts like a maze solver: pick a path, go as deep as possible until you hit a dead end, then backtrack. It uses a Stack (or recursion) and is great for finding cycles or connected components.
Breadth-First Search (BFS) explores outward in layers, like a ripple in a pond. It uses a Queue and guarantees that the first time you reach a node, you found the shortest path to it (in unweighted graphs).
from collections import deque
def bfs(graph, start):
visited = set([start])
q = deque([start])
while q:
curr = q.popleft()
print(f"Visiting {curr}")
for neighbor in graph[curr]:
if neighbor not in visited:
visited.add(neighbor)
q.append(neighbor)