Introduction

Graph traversal algorithms are methods for visiting vertices and edges in a controlled order. They are foundational in search, connectivity analysis, shortest-path problems, dependency processing, and many interview questions. The two core traversal families are depth-first search and breadth-first search, but several named algorithms build on those ideas for different goals.

The Two Basic Traversals

The two names every programmer should know are:

• Depth-First Search, usually shortened to DFS.
• Breadth-First Search, usually shortened to BFS.

These are true traversal algorithms in the direct sense of “visit the graph.”

Depth-First Search

DFS explores one branch as deeply as possible before backtracking. It can be implemented recursively or with an explicit stack.

1def dfs(graph, start):
2    visited = set()
3    stack = [start]
4
5    while stack:
6        node = stack.pop()
7        if node in visited:
8            continue
9
10        visited.add(node)
11        print(node)
12
13        # reverse for a more predictable left-to-right demo order
14        for neighbor in reversed(graph.get(node, [])):
15            if neighbor not in visited:
16                stack.append(neighbor)
17
18graph = {
19    "A": ["B", "C"],
20    "B": ["D", "E"],
21    "C": ["F"],
22    "D": [],
23    "E": [],
24    "F": []
25}
26
27dfs(graph, "A")

DFS is useful for:

• Topological-style explorations.
• Connected-component searches.
• Cycle detection.
• Backtracking problems.

Breadth-First Search

BFS explores the graph level by level using a queue.

1from collections import deque
2
3def bfs(graph, start):
4    visited = {start}
5    queue = deque([start])
6
7    while queue:
8        node = queue.popleft()
9        print(node)
10
11        for neighbor in graph.get(node, []):
12            if neighbor not in visited:
13                visited.add(neighbor)
14                queue.append(neighbor)
15
16bfs(graph, "A")

BFS is especially useful for:

• Shortest path in unweighted graphs.
• Layered exploration.
• Reachability with minimum edge count.

Other Commonly Named Traversal-Related Algorithms

People often ask for “names of graph traversal algorithms” and receive a broader list that includes algorithms based on traversal rather than pure traversal primitives.

Common names include:

• DFS
• BFS
• Iterative Deepening DFS
• Dijkstra’s algorithm
• A star search
• Topological sort

Strictly speaking, Dijkstra and A star are shortest-path search algorithms, not just raw traversals. They still belong in the conversation because they visit graph nodes systematically.

Iterative Deepening DFS

Iterative deepening repeats DFS with increasing depth limits. It combines DFS-like memory usage with BFS-like shallow-solution discovery in some search spaces.

1def depth_limited_dfs(graph, node, limit, visited=None):
2    if visited is None:
3        visited = set()
4
5    if limit < 0 or node in visited:
6        return
7
8    visited.add(node)
9    print(node)
10
11    if limit == 0:
12        return
13
14    for neighbor in graph.get(node, []):
15        depth_limited_dfs(graph, neighbor, limit - 1, visited)

This is common in game search and puzzle search discussions.

Traversal Choice Depends on the Problem

Use DFS when:

• You need backtracking.
• You want a memory-light traversal on deep structures.
• You are checking connectivity, cycles, or components.

Use BFS when:

• You need the shortest unweighted path.
• Level order matters.
• Distance by edge count matters.

Do not choose an algorithm by name alone; choose it by the property you need from the visit order.

Directed Versus Undirected Graphs

The same traversal names apply to both directed and undirected graphs, but interpretation changes slightly:

• In directed graphs, edges have one-way reachability.
• In undirected graphs, traversal explores mutual connections.

For DFS and BFS, visited-node tracking is essential in both cases to avoid infinite revisits on cyclic graphs.

Common Pitfalls

• Treating Dijkstra or A star as the same thing as BFS or DFS. Fix by separating basic traversals from weighted-search algorithms.
• Forgetting a visited set in cyclic graphs. Fix by marking visited nodes explicitly.
• Using BFS when memory growth will be too large for the frontier. Fix by evaluating graph shape and problem constraints first.
• Using DFS when the goal is the shortest path in an unweighted graph. Fix by choosing BFS for minimum-edge path problems.
• Asking only for algorithm names without defining the task. Fix by mapping the problem requirement to the traversal property you need.

Summary

• The two primary graph traversal algorithms are DFS and BFS.
• DFS explores deeply before backtracking, while BFS explores level by level.
• Iterative deepening, Dijkstra, and A star are often discussed alongside traversal algorithms.
• The right choice depends on whether you need depth, breadth, or shortest-path behavior.
• Graph traversal names are useful only when tied to the problem you are actually solving.