Released · improving
Algorithm
Graph traversal visits every reachable vertex with BFS or DFS, the basis for unweighted shortest paths, components, cycle detection and topological sorting.
Graph traversal is the process of visiting every vertex reachable from a starting vertex exactly once by following edges. The two fundamental strategies are breadth-first search (BFS), which uses a queue to expand outward one layer at a time, and depth-first search (DFS), which uses a stack or recursion to follow one branch as far as possible before backtracking. Graphs are usually stored as adjacency lists or adjacency matrices, and 2D grids such as mazes become graphs once each cell is treated as a vertex.
Road networks, social networks, task dependencies and web links are all graphs. BFS finds shortest paths when every edge has the same cost, while DFS underpins connected components, cycle detection and topological sorting. Build tools ordering their tasks, garbage collectors deciding what is still reachable and the paint-bucket tool in an image editor all rely on traversal, and it is one of the most common topics in coding interviews.
Start by drawing a small graph and tracing by hand how the BFS queue and the DFS call stack evolve. Then implement both yourself, paying attention to when vertices are marked as visited and how distances and parents are recorded. From there, move on to grid shortest paths, counting connected components and topological sorting with Kahn's algorithm.
Adjacency lists use O(V + E) memory and suit sparse graphs; adjacency matrices check edges in O(1) but need O(V^2) memory.
A queue visits the nearest vertices first, so in an unweighted graph the first distance BFS assigns is the shortest one.
Recursion or a stack dives deep and backtracks, forming the basis of components, cycle detection and backtracking.
In a directed acyclic graph, Kahn's algorithm or reversed DFS finish order yields an order that respects every dependency.
The program builds a six-vertex undirected graph as a dictionary-based adjacency list, then prints the fewest edges from A to every vertex using a deque-based BFS and the visiting order of a recursive DFS. Both functions keep a visited record so no vertex is processed twice.
graph_traversal.py
from collections import deque
graph = {
"A": ["B", "C"],
"B": ["A", "D"],
"C": ["A", "D", "E"],
"D": ["B", "C", "F"],
"E": ["C", "F"],
"F": ["D", "E"],
}
def bfs(start):
"""Shortest number of edges from start to every reachable vertex."""
dist = {start: 0}
queue = deque([start])
while queue:
node = queue.popleft()
for nxt in graph[node]:
if nxt not in dist:
dist[nxt] = dist[node] + 1
queue.append(nxt)
return dist
def dfs(start):
"""Vertices in depth-first visiting order."""
order, seen = [], set()
def visit(node):
seen.add(node)
order.append(node)
for nxt in graph[node]:
if nxt not in seen:
visit(nxt)
visit(start)
return order
print(bfs("A")) # {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 3}
print(dfs("A")) # ['A', 'B', 'D', 'C', 'E', 'F']
python graph_traversal.pySix chapters that take you from installation to the core ideas of Graph traversal.
Ask questions, share experience and trade opinions about Graph traversal.
No discussions yet. Start the first one.
0 comments
Sign in · Sign in to leave a comment.
Be the first to comment.