Graphs
16 min
A graph is nodes plus edges between them — more general than a tree (which is just a graph with no cycles and exactly one path between any two nodes). The most common representation in code is an adjacency list: a dict mapping each node to the list of nodes it connects to.
graph = {
"A": ["B", "C"],
"B": ["D"],
"C": ["D"],
"D": [],
}
BFS (breadth-first search) explores level by level using a queue —
first all of start's direct neighbors, then their neighbors, and so on.
It's what you want for "shortest path in an unweighted graph."
Marking a node visited the moment it's enqueued (not when it's dequeued) is what prevents the same node from being added to the queue twice.
DFS (depth-first search) explores as deep as possible down one branch before backtracking — using a stack (or recursion, which uses the call stack implicitly). It's the natural fit for "does a path exist at all," cycle detection, and topological sort (you'll build one in the Algorithms course).
def has_path(graph, start, end):
visited = set()
def dfs(node):
if node == end:
return True
visited.add(node)
return any(
neighbor not in visited and dfs(neighbor)
for neighbor in graph[node]
)
return dfs(start)
Write a function `bfs_order(graph, start)` that returns the nodes reachable from `start`, in breadth-first order. `graph` is a dict mapping each node to a list of its neighbors.
Write a function `has_path(graph, start, end)` that returns True if there is a path from `start` to `end` in `graph`, False otherwise.
Which traversal visits nodes level-by-level, using a queue rather than a stack?
You can represent a graph as an adjacency list and implement both BFS and DFS traversals.