When would you use BFS instead of DFS, and what are the costs of each?

Use BFS when you need the route with the fewest edges in an unweighted graph, or everything within k steps of a start node. BFS uses a queue and explores level by level. Use DFS when you need to explore everything, find cycles, order tasks, or solve a puzzle by trying one branch fully before backing up. DFS uses a stack or recursion. Both take O(V + E) time on an adjacency list. Memory is O(V) for the visited set in both, and BFS can hold a whole level in its queue while DFS holds the current path.

Given a grid of 1s (land) and 0s (water), count the islands. Land cells connect up, down, left and right.

Scan the grid. When you meet an unvisited land cell, add one to the count and run BFS or DFS from it, marking every connected land cell as visited (or sinking it to 0). Each cell is visited once, so time is O(R × C) for R rows and C columns. Memory is O(R × C) in the worst case for the stack or queue, when the whole grid is one island.

Given courses and prerequisite pairs, can you finish all of them? Return false if the prerequisites contain a cycle.

Build a directed graph and compute a topological order. With Kahn's algorithm, count each node's incoming edges, queue the nodes with zero, and repeatedly remove one, lowering the count of its neighbours. If you remove every node, there is no cycle and the answer is true. If some nodes never reach zero, they are on or behind a cycle, so the answer is false. Time is O(V + E) and memory is O(V + E) for the adjacency list and the counts. DFS with three states (unvisited, in progress, done) also works: reaching an in-progress node means a cycle.

Find the fewest steps from a start word to an end word, changing one letter at a time, where every step must be a word in a given list.

Model the words as an unweighted graph and run BFS from the start word. The first time BFS reaches the end word, the number of levels travelled is the fewest steps. Keep a visited set so no word is queued twice. With W words of length L, time is O(26 × W × L²): each word tries 26 letters at each of L positions, and building each candidate costs O(L). Memory is O(W × L).

Graphs

Nodes joined by edges. Graphs model networks, maps and dependencies, and breadth-first and depth-first search explore them.

intermediate30 minAsked oftenGraphsBfsDfsTraversalShortest path

Last reviewed 24 Oct 2026 · by TheLearningLoop Team

Read first: Data Structures & Algorithms: The Big Picture (blog post)

Progress is saved on this device. Create a free account to keep it everywhere.

On this page ▾

On this page

Key takeaways

A graph is nodes plus edges. Unlike a tree, it can have cycles and no root.
BFS and DFS both visit every node and edge once, so both take O(V + E) time.
BFS finds the route with the fewest edges. DFS does not.

When to use a graph

Use a graph when you have:

Things and relationships between them, where one thing can link to many others and back, such as friends, roads, links between web pages or tasks that depend on each other.
Questions about connection: "how are A and B linked?", "who is within 2 steps of me?", "are these two accounts in the same group?"
A need for the shortest or cheapest route, such as the fewest stops or the least travel time.
Ordering with rules, such as "what must happen before what?", or detecting a cycle that makes that impossible.

Use something else when:

Every item has exactly one parent and the data only goes downwards: use a tree.
You only look things up by a key: use a hash map.
Items are just a sequence: use an array or list.
The data is regular rows with fixed relationships: a database table with joins is usually simpler.

Write the simple parts yourself, borrow the heavy parts. An adjacency list and a BFS are short enough to write by hand. For weighted shortest paths, very large graphs or analysis such as finding communities, use a tested library (see the real-world section).

How a graph works

A graph is a set of things and the links between them. The things are called nodes (or vertices). The links are called edges. That is all a graph needs:

A graph is nodes plus edges. Every edge joins two nodes, and there is no root, no "left" or "right", and no rule against going round in circles.

Friends on a social network, junctions on a road map and steps in a build are all graphs. A binary search tree is a graph too, just a very tidy one: it has a root, one route between any two nodes, and no cycles. Graphs drop those restrictions, which is why they can describe so many real situations.

Words you will meet:

Neighbour: a node you can reach along one edge.
Degree: how many neighbours a node has.
Path: a list of nodes where each one is joined to the next. Its length is the number of edges.
Cycle: a path that comes back to where it started.
Connected: there is a path between every pair of nodes. A graph that is not connected has separate "islands".
Directed: edges have a direction, like "follows" on a social network. In an undirected graph, an edge works both ways, like friendship.
Weighted: edges carry a number, such as travel time.

Try it

Pick a method and run it. Watch which node is looked at next, and how the queue (BFS) or the path (DFS) changes.

Graph traversal

Step 1 of 38 · Press Space to play, arrow keys to step

Method:

Start atLook for

Graph:

Queue (front first): A

Start at A: put it in the queue.

visited:: 0
edgesChecked:: 0
queue:: 1

visited = nodes finished or in progress. edgesChecked = times an edge was looked at from one end.

Speed

Things to try:

Keep Friend network and BFS, start at A, and set Look for to H. BFS finds A → B → E → H, which is 3 edges.
Switch to DFS and look for H again. DFS finds A → B → D → G → E → C → F → H, which is 7 edges. It dives deep and takes the first route it finds, not the shortest.
Choose Two islands, start at A and visit everything. D, E and F are never visited, because no edge leads to them from A.

Graph operations: store, traverse and find a route

Store it. The usual choice is an adjacency list: for each node, keep the list of its neighbours. For an undirected edge, add each end to the other's list. It uses memory in proportion to the nodes and edges, and it makes "list the neighbours" fast.

Traverse it. To visit every node you can reach from a start node, keep a visited set so you never go round a cycle forever, and a to-do list of nodes still to explore. The two classic ways differ only in which node you take from the to-do list next:

	Breadth-first search (BFS)	Depth-first search (DFS)
To-do list	Queue: take the oldest node	Stack (or recursion): take the newest node
Order	Level by level: all neighbours, then their neighbours	Down one branch as far as it goes, then back up
Fewest-edges route	Always finds one	Not guaranteed
Memory	Can hold a whole level at once	Holds the current path
Good for	Shortest route, "within k steps"	Cycles, ordering tasks, exploring everything, puzzles

Find a route. Run BFS from the start and remember, for each node, which node you came from. When you reach the goal, follow those links back to the start. In an unweighted graph, that route has the fewest edges.

Two interview facts. Both BFS and DFS look at each node once and each edge a fixed number of times, so both are O(V + E). And if edges have different costs, BFS is not enough: you need Dijkstra's algorithm.

Graph time complexity

V is the number of nodes and E is the number of edges. This table assumes an adjacency list.

Operation	Typical graph	Worst case
Add a node	O(1)	O(1)
Add an edge	O(1)	O(1)
Is there an edge between A and B?	O(degree of A)	O(V)
List the neighbours of A	O(degree of A)	O(V)
BFS or DFS over the whole graph	O(V + E)	O(V + E)
Fewest-edges route (BFS)	O(V + E)	O(V + E)
Memory	O(V + E)	O(V²)

The worst case happens in a dense graph, where almost every node is joined to every other, so E grows like V². Most real graphs are sparse (each node has few neighbours compared with the total), which is why adjacency lists are the usual choice.

Graphs vs other data structures

The right choice depends on what you do most. Here is the same set of jobs done with a graph and with the structures you already know. V is the number of nodes and E the number of edges.

What you need	Graph	Tree	Hash map	Linked list
Items linked to many others, both ways	Yes	No, one parent each	Not by itself	No, one "next" each
Fewest-edges route between two items	BFS, O(V + E)	The only route, found in O(n)	Not possible	O(n) walk
What must come before what	Topological order, O(V + E)	Parents before children only	Not possible	The list order only
Cycles allowed	Yes	No	n/a, it has no links	Only if you break the rules
Find one item by its key	Needs a hash map beside it	O(log n) if ordered and balanced	O(1) average	O(n)

The bold cells show where each one wins. A tree is a graph with no cycles and exactly one route between any two nodes. A linked list is a graph where each node has one "next". The graph is the right choice once those limits get in the way, and the wrong one when all you need is a key lookup.

Three ways to store a graph

Once you choose a graph, there are three common ways to store it. This is the same job done three ways.

What you need	Adjacency list	Adjacency matrix	Edge list
Is there an edge between A and B?	O(degree of A)	O(1)	O(E)
List the neighbours of A	O(degree of A)	O(V)	O(E)
Add an edge	O(1)	O(1)	O(1)
Remove an edge	O(degree of A)	O(1)	O(E)
Walk the whole graph (BFS or DFS)	O(V + E)	O(V²)	O(V · E)
Memory	O(V + E)	O(V²)	O(E)

An adjacency matrix is a V by V grid where cell (A, B) says whether the edge exists. An edge list is just a list of pairs. The matrix is best when the graph is dense or you check single edges all the time. The edge list is best for simply storing or sorting edges. For everything else, use the adjacency list.

How to explain graphs in an interview

Start with the model: "nodes and edges, directed or undirected, weighted or not." Ask which one the question means.
Say how you will store it: "an adjacency list, so memory is O(V + E)."
State the complexity in terms of V and E, not n.
Say you will keep a visited set, because graphs can have cycles.
Name the choice: "BFS if I need the fewest edges, DFS if I just need to explore or order things, Dijkstra if edges have costs."

Where you meet graphs in real systems

You rarely draw a graph at work, but they sit underneath maps, social apps, build tools and operating systems. Here are three drawn out, the first with code you can run, then more examples.

Example 1: Social networks and "how are we connected?"

A social network is a graph: each person is a node and each friendship is an edge. "How many hops between me and this person?" and "people you may know" are graph questions. The first is a fewest-edges route, which is exactly what BFS finds. Open the example below to see the picture and the code.

Code: build a friend graph and find the shortest routeTime O(V + E)Memory O(V + E)

Each circle is a person and each line is a friendship. The green route is the shortest way to connect A to G: 3 hops. Person I has no friends yet, so no route can reach them.

from collections import deque

# Data: 9 people and 10 friendships. "I" has no friends yet.
PEOPLE = ["A", "B", "C", "D", "E", "F", "G", "H", "I"]
FRIENDSHIPS = [("A", "B"), ("A", "C"), ("B", "D"), ("B", "E"), ("C", "E"),
               ("C", "F"), ("D", "G"), ("E", "G"), ("E", "H"), ("F", "H")]


def build_graph(people, friendships):
    """Adjacency list: each person maps to the list of their friends.

    Time:   O(V + E), one pass over the people and one over the friendships.
    Memory: O(V + E), each friendship is stored twice (once per person).
    V = number of people, E = number of friendships.
    """
    graph = {person: [] for person in people}
    for a, b in friendships:
        graph[a].append(b)   # friendship works both ways,
        graph[b].append(a)   # so add it to both lists
    return graph


def shortest_path(graph, start, goal):
    """Fewest-hops route from start to goal using breadth-first search (BFS).

    Returns the list of people along the route, or None if they are not connected.

    Time:   O(V + E). Every person is queued at most once and every friendship
            is looked at at most twice (once from each end).
    Memory: O(V) for the queue and the parent map (not counting the graph itself).
    """
    parent = {start: None}          # who we came from; doubles as the "seen" set
    queue = deque([start])          # people waiting to be explored, oldest first
    while queue:
        person = queue.popleft()
        if person == goal:
            break                   # BFS reaches the goal by the fewest hops first
        for friend in graph[person]:
            if friend not in parent:        # not seen yet
                parent[friend] = person
                queue.append(friend)
    if goal not in parent:
        return None                 # the goal is in a different island
    route = []
    while goal is not None:         # walk the parent links back to the start
        route.append(goal)
        goal = parent[goal]
    return route[::-1]

Each version builds an adjacency list from the same nine people and ten friendships, then runs BFS with a parent map to rebuild the route. All five were compiled and run, and all found A → B → D → G and A → B → E → H, and reported no route to I, who has no friends. Every version uses only its language's standard library. Go prints an empty list where the others print None or null.

Example 2: Maps and navigation

A road map is a weighted graph: junctions are nodes, roads are edges, and each edge carries a number such as minutes of travel. Finding a good route means finding the path with the smallest total weight. That is not always the path with the fewest stops, so BFS is not enough and navigation software uses Dijkstra's algorithm or faster methods built on the same idea.

Numbers are minutes. Home to Shop to Work has the fewest stops but takes 9 minutes. The green route has more stops and takes only 8 (2 + 1 + 5). Dijkstra's algorithm finds this kind of route.

Example 3: Build tools and package managers

When a build tool decides what to run first, it uses a directed graph: an arrow from A to B means "A must finish before B". Putting the steps in an order that respects every arrow is called a topological sort. If the arrows form a cycle, no valid order exists, and the tool reports a circular dependency.

An arrow means 'must finish before'. Any order that respects every arrow works, for example the numbered one. This is called a topological order. It only exists when there are no cycles.

More real-world scenarios

4. Web crawling and links

Web pages are nodes and links are edges. A crawler starts from a few known pages and explores outwards, much like BFS, with a visited set so it never fetches the same page twice. The link structure is also one of the signals search engines use to judge pages.

5. Network routing

A router needs to know the best way to send data across a network of other routers. Link-state routing protocols such as OSPF have each router build a map of the network and run a shortest-path calculation on it to choose the next hop.

6. Version control history

In Git, every commit points to its parent commit or commits. A merge commit has two parents, so the history is a directed graph with no cycles. Commands that draw the history, or find the last commit two branches share, are walking that graph.

7. Garbage collection

In languages with a tracing garbage collector, objects are nodes and references are edges. The collector starts from the objects the program can still reach and marks everything reachable from them. Anything left unmarked is unreachable, so its memory can be freed.

8. Deadlock detection

A database can track which transaction is waiting for which as a wait-for graph: an arrow from A to B means A is waiting for B. If the arrows form a cycle, those transactions will wait forever, so the database picks one to cancel.

9. Pathfinding in games and robots

A grid map becomes a graph by treating each walkable cell as a node and joining it to its neighbours. BFS finds a fewest-steps route when every step costs the same. When terrain has different costs, games commonly use A*, which is Dijkstra's algorithm guided by a guess of the remaining distance.

10. Recommendations and fraud checks

"People you may know" suggestions often start from friends of friends, which means nodes two hops away. Fraud teams can look for groups of accounts linked by shared details such as the same device or card. Finding those groups is a connected components problem, solved with BFS or DFS.

Language standard libraries

Almost no language ships a general-purpose graph type. Most people store an adjacency list in the language's own map and list types, and use a package when they need heavier algorithms.

Language	Structure or class	What it is under the hood	Notes
Java	None built in	`Map<K, List<K>>` with `ArrayDeque` as the BFS queue	The JGraphT library is a popular full graph package.
C++	None built in	`vector<vector<int>>` or `unordered_map` of vectors, with `std::queue`	The Boost Graph Library is the usual full-featured option.
C#	None built in	`Dictionary<K, List<K>>` with `Queue<T>`	QuikGraph is a third-party graph library.
Rust	None built in	`Vec<Vec<usize>>` or `HashMap`, with `VecDeque`	The `petgraph` crate is the common choice.
Python	None for general graphs	A `dict` of lists, with `collections.deque`	`graphlib.TopologicalSorter` in the standard library orders tasks and detects cycles. NetworkX is the popular package.
Go	None built in	`map[K][]K` with a slice as the queue	The `gonum.org/v1/gonum/graph` packages provide graph types and algorithms.
JavaScript	None built in	`Map` of arrays	Packages such as Graphology provide a full graph type.
Kotlin	None built in	Same maps and lists as Java	JGraphT works from Kotlin too, since it runs on the JVM.

The pattern: the standard libraries give you the building blocks (maps, lists, queues), and you build the graph on top. Python's graphlib is the one standard-library exception, and it only covers ordering tasks.

The takeaway

Whenever a system has things linked to other things and needs to ask how they connect, what is nearest, or what must come first, look for a graph. When it only needs to look things up by key, it usually uses a hash map instead.

Interview questions

Try answering out loud before you reveal hints. Interviewers care about how you reason, not just the final answer.

1.
When would you use BFS instead of DFS, and what are the costs of each?
easy
2.
Given a grid of 1s (land) and 0s (water), count the islands. Land cells connect up, down, left and right.
medium
3.
Given courses and prerequisite pairs, can you finish all of them? Return false if the prerequisites contain a cycle.
medium
4.
Find the fewest steps from a start word to an end word, changing one letter at a time, where every step must be a word in a given list.
medium

← Previous

Binary Search Tree