Skip to main content
ProgrammersOS
Sign In
Algorithms•Last Updated : 23 Oct 2026
~55 min read

Graphs and Traversal: BFS and DFS

Model networks as graphs, store them as adjacency lists, and explore them with breadth-first and depth-first search. Learn which traversal finds shortest paths, which finds cycles and components, and how to search a grid maze.

Graphs are everywhere once you look for them

A friendship network, a road map, the links between web pages, the dependencies between software packages, the rooms of a dungeon: all are the same abstract thing. There are things and there are connections between them. A graph records exactly that and nothing more: a set of vertices (also called nodes) and a set of edges, each joining two vertices.

Two distinctions matter immediately. Edges can be undirected (friendship goes both ways) or directed (a hyperlink points from one page to another). They can also carry a weight (road length) or be plain. A path is a sequence of vertices where each consecutive pair is joined by an edge; a cycle is a path that returns to its start; a graph is connected if every vertex can reach every other.

Most graph questions reduce to a few moves on the same skeleton: Can I get from here to there? What is the fewest steps? What is reachable? Is there a loop? Two traversals answer nearly all of them, and learning to pick the right one is the point of this lesson.

Definition: Graph

A pair G = (V, E): a set of vertices V and a set of edges E, where each edge connects two vertices. Edges may be directed or undirected, weighted or unweighted.

Storing a graph: adjacency list or matrix

You must pick a representation before you can write any algorithm. The adjacency matrix is a V by V table where cell [i][j] says whether an edge i to j exists. Checking one specific edge is instant, but the table costs V squared memory even if the graph has almost no edges. The adjacency list keeps, for each vertex, just the list of its neighbours. Memory is proportional to V plus E, and iterating over a vertex's neighbours (which is what traversals do constantly) touches only real edges.

Most real graphs are sparse (a person has hundreds of friends, not millions), so the adjacency list is the default. Reach for a matrix when the graph is small and dense, or when you must test arbitrary edge existence very often.

Adjacency list versus adjacency matrix

OperationAdjacency listAdjacency matrix
MemoryO(V + E)O(V^2)
Is there an edge u-v?O(degree of u)O(1)
List all neighbours of uO(degree of u)O(V)
Best forSparse graphs, traversalsSmall or dense graphs, frequent edge queries
PythonBuilding an adjacency list from edge pairs
1edges = [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D"), ("D", "E"), ("F", "G")]
2 
3graph = {}
4for u, v in edges:
5    graph.setdefault(u, []).append(v)
6    graph.setdefault(v, []).append(u)      # undirected: record both directions
7 
8for vertex in sorted(graph):
9    print(vertex, "->", sorted(graph[vertex]))
10print("vertices:", len(graph), "| edges:", len(edges))
Output
A -> ['B', 'C']
B -> ['A', 'D']
C -> ['A', 'D']
D -> ['B', 'C', 'E']
E -> ['D']
F -> ['G']
G -> ['F']
vertices: 7 | edges: 6

Breadth-first search: ripples in a pond

Drop a stone in water and the ripple reaches everything at distance 1, then everything at distance 2, then 3. Breadth-first search (BFS) explores a graph the same way: visit the start, then all its neighbours, then all their unvisited neighbours, level by level.

The tool that enforces this order is a queue (first in, first out). Put the start in the queue and mark it visited. Repeatedly remove the front vertex and append each unvisited neighbour, marking it visited at the moment you add it. Because the queue releases vertices in the order they were discovered, closer vertices are always processed before farther ones.

That gives BFS its superpower: on an unweighted graph, the first time BFS reaches a vertex is along a shortest path (fewest edges). Record each vertex's parent when you discover it, and you can walk the parents backwards to rebuild the route. The visited set is not optional decoration. Without it, a graph with a cycle sends BFS round and round forever.

BFS layers from A
        A            layer 0
       / \
      B   C          layer 1
       \ /
        D            layer 2
        |
        E            layer 3

queue: [A] -> [B C] -> [C D] -> [D] -> [E] -> []
The queue empties level by level; the layer number is the shortest distance in edges.
PythonBFS: shortest path and distances
1from collections import deque
2 
3graph = {"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D"],
4         "D": ["B", "C", "E"], "E": ["D"], "F": ["G"], "G": ["F"]}
5 
6def bfs_path(graph, start, goal):
7    parent = {start: None}
8    queue = deque([start])
9    while queue:
10        node = queue.popleft()
11        if node == goal:
12            path = []
13            while node is not None:
14                path.append(node)
15                node = parent[node]
16            return path[::-1]
17        for neighbour in graph[node]:
18            if neighbour not in parent:          # parent doubles as the visited set
19                parent[neighbour] = node
20                queue.append(neighbour)
21    return None                                  # goal not reachable
22 
23print(bfs_path(graph, "A", "E"))
24print(bfs_path(graph, "E", "A"))
25print(bfs_path(graph, "A", "G"))
Output
['A', 'B', 'D', 'E']
['E', 'D', 'B', 'A']
None

Depth-first search: follow a corridor to its end

Depth-first search (DFS) behaves like someone exploring a maze with a ball of string. Go down one corridor as far as it goes; at a dead end, back up to the last junction with an unexplored branch and try that. It dives deep before it looks wide.

The tool that enforces this is a stack, and you already have one for free: the recursion call stack. Visit a vertex, mark it, then recurse into each unvisited neighbour. When a call returns, you have backtracked to the previous junction. You can also write it with an explicit stack to avoid recursion limits on very deep graphs.

DFS does not find shortest paths, but it excels at questions about structure. It marks everything reachable from a start (connected components). It detects cycles. It produces a topological order of a directed acyclic graph, which is how build tools decide which package to compile first. All of these rely on the same idea: finishing a vertex tells you something about everything beneath it.

DFS discovery order on the same graph
        A(1)
       /    \
    B(2)    C(4)
       \    /
        D(3) ---- E(5)

A -> B -> D -> C  (C is a neighbour of D, reached before backing up)
               -> E
DFS goes A, B, D, then explores C and E before it backs all the way up. Numbers show the order of visiting.
PythonDFS two ways, and connected components
1graph = {"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D"],
2         "D": ["B", "C", "E"], "E": ["D"], "F": ["G"], "G": ["F"]}
3 
4def dfs_recursive(node, seen, order):
5    seen.add(node)
6    order.append(node)
7    for neighbour in graph[node]:
8        if neighbour not in seen:
9            dfs_recursive(neighbour, seen, order)
10    return order
11 
12def dfs_iterative(start):
13    seen, order, stack = set(), [], [start]
14    while stack:
15        node = stack.pop()
16        if node in seen:
17            continue
18        seen.add(node)
19        order.append(node)
20        for neighbour in reversed(graph[node]):   # reversed keeps the same visiting order
21            stack.append(neighbour)
22    return order
23 
24print("recursive:", dfs_recursive("A", set(), []))
25print("iterative:", dfs_iterative("A"))
26 
27components, seen = [], set()
28for vertex in sorted(graph):
29    if vertex not in seen:
30        group = dfs_recursive(vertex, seen, [])
31        components.append(sorted(group))
32print("components:", components)
Output
recursive: ['A', 'B', 'D', 'C', 'E']
iterative: ['A', 'B', 'D', 'C', 'E']
components: [['A', 'B', 'C', 'D', 'E'], ['F', 'G']]

BFS or DFS: choosing the right one

Both visit every reachable vertex exactly once, so both cost O(V + E) with an adjacency list: each vertex enters the structure once and each edge is examined a constant number of times. The difference is the order, and the order is what you choose between.

If the question contains "fewest", "shortest", "minimum number of moves" or "nearest", you want BFS, because its layers are distances. If the question is about structure, such as "is there any path", "how many groups", "does this contain a cycle", "in what order must tasks run", DFS is the natural fit and its recursive form is short. Memory also differs: BFS holds an entire layer in its queue (potentially most of the graph), while DFS holds only the current path.

BFS versus DFS

BFSDFS
Data structureQueueStack or recursion
Shortest path (unweighted)YesNo
Connected components, cycle detectionPossibleNatural
Topological orderingVia in-degree countingVia finish order
MemoryWidest layerDeepest path
TimeO(V + E)O(V + E)

A graph in disguise: searching a grid

You often will not be handed a graph. A maze, a game board, a map of islands: each cell is a vertex, and its neighbours are the cells directly above, below, left and right, if they are open. There is no adjacency list stored anywhere; you compute neighbours on the fly with four direction offsets. Everything you just learned applies unchanged, so the shortest route through a maze is BFS.

The habit worth building is to recognise the hidden graph. "Minimum number of moves" on a grid, a word ladder, a puzzle with states (a 3-digit lock), all mean BFS over an implicit graph whose vertices are configurations.

PythonShortest path through a maze with BFS
1from collections import deque
2 
3maze = ["S.#.....",
4        ".##.###.",
5        "....#...",
6        "##.##.#.",
7        "...#..#E"]
8 
9rows, cols = len(maze), len(maze[0])
10start = next((r, c) for r in range(rows) for c in range(cols) if maze[r][c] == "S")
11goal = next((r, c) for r in range(rows) for c in range(cols) if maze[r][c] == "E")
12 
13dist = {start: 0}
14queue = deque([start])
15while queue:
16    r, c = queue.popleft()
17    if (r, c) == goal:
18        break
19    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
20        nr, nc = r + dr, c + dc
21        if 0 <= nr < rows and 0 <= nc < cols and maze[nr][nc] != "#" and (nr, nc) not in dist:
22            dist[(nr, nc)] = dist[(r, c)] + 1
23            queue.append((nr, nc))
24 
25print("fewest moves from S to E:", dist.get(goal, "unreachable"))
26print("cells explored:", len(dist))
Output
fewest moves from S to E: 15
cells explored: 23

Where traversals go wrong

Marking visited too late in BFS. If you mark a vertex only when you pop it from the queue, the same vertex can be pushed many times before it is processed. The answer stays correct but the queue and the time balloon. Mark when you push.

Forgetting the visited set on cyclic graphs. A tree needs none, because there is only one way to each node. Any graph with a cycle will loop forever without one.

Using DFS for shortest paths. DFS reaches a vertex by whichever route it tried first, not the shortest. On the diamond A-B-D and A-C-D it is only luck which side it picks.

Recursive DFS on huge inputs. A path graph of 100,000 vertices overflows Python's default recursion limit. Use the explicit stack version.

Mixing up directed and undirected. When building an undirected graph from edge pairs, add both directions (as in the first example), or half your edges will be one-way.

Tip

To count connected components, loop over all vertices and start a DFS or BFS only from those not yet visited. The number of starts is the number of components.

Check your understanding

Pay attention to why each wrong option is tempting.

Suggested Quiz
Question 1 of 4

A game asks for the minimum number of moves to turn word X into word Y, changing one letter at a time. Which approach fits best?

Quick Syntax & Reference Sheet

Concept / RuleSyntax / Usage
Adjacency listgraph = {u: [v1, v2, ...]} # undirected: add both directions
BFS templatequeue = deque([s]); seen = {s} while queue: u = queue.popleft() for v in graph[u]: if v not in seen: seen.add(v); queue.append(v)
DFS templatedef dfs(u): seen.add(u) for v in graph[u]: if v not in seen: dfs(v)
Grid neighboursfor dr, dc in ((1,0),(-1,0),(0,1),(0,-1)): ...

Common Pitfalls & Developer Mistakes

✕ Mistake 1:

Not tracking visited vertices

Why it happens: Cycles make the traversal revisit vertices endlessly.

Correction: Keep a set of seen vertices and check it before enqueueing or recursing.
✕ Mistake 2:

Using DFS when the problem asks for the fewest steps

Why it happens: DFS finds some path, not the shortest.

Correction: Use BFS on unweighted graphs; use Dijkstra when edges have weights.
✕ Mistake 3:

Adding only one direction for undirected edges

Why it happens: Traversal from the other endpoint would never see the edge.

Correction: Append v to u's list and u to v's list.

Frequently Asked Questions

Can BFS find shortest paths when edges have different weights?

No. BFS counts edges, not total weight. For non-negative weights use Dijkstra's algorithm, covered in the shortest paths lesson.

Which is easier to write in an interview?

Recursive DFS is the shortest. BFS needs a queue but is just as mechanical. State the data structure out loud and the visited-set rule; those are the details interviewers listen for.
Next: Greedy Algorithms →
Article Tags:#Graphs#BFS#DFS#Adjacency List#Shortest Path#Connected Components
Previous TopicDynamic Programming Patterns
Next TopicGreedy Algorithms
Was this lesson clear and helpful?

Discussion (0)

Sign in to ask questions and reply.
Loading discussion

Related discussions

Discuss in community