After this lesson, you will be able to: Represent graphs with adjacency lists and matrices, distinguish directed/undirected and weighted/unweighted graphs, and implement BFS and DFS from scratch.
A graph is the most general data structure: nodes connected by edges. Social networks, maps, dependencies, the web itself are all graphs. Mastering graph representation and traversal unlocks a huge class of real problems and interview questions.
A graph is a set of vertices (nodes) connected by edges (links). Edges can be directed (a one-way follow on social media) or undirected (a mutual friendship). They can be weighted (a road with a distance or cost) or unweighted (just connected or not). Trees and linked lists are actually special cases of graphs. Once you can model a problem as a graph, decades of graph algorithms become available to you.
Adjacency list (usually preferred) vs adjacency matrix.
# Adjacency list: for each node, a list of its neighbors.# Space O(V + E). Best for sparse graphs (most real graphs).graph = {"A": ["B", "C"],"B": ["D"],"C": ["D"],"D": [],}# Adjacency matrix: a V x V grid; matrix[i][j] = 1 if edge i->j.# Space O(V^2). Edge lookup is O(1) but wasteful for sparse graphs.# A B C D# A [ 0, 1, 1, 0 ]# B [ 0, 0, 0, 1 ]# C [ 0, 0, 0, 1 ]# D [ 0, 0, 0, 0 ]
The two fundamental traversals. BFS uses a queue; DFS uses a stack or recursion.
from collections import dequedef bfs(graph, start): # explores ring by ring (shortest path in edges)visited, q, order = {start}, deque([start]), []while q:node = q.popleft()order.append(node)for nbr in graph[node]:if nbr not in visited:visited.add(nbr)q.append(nbr)return orderdef dfs(graph, start, visited=None, order=None): # goes deep firstif visited is None: visited, order = set(), []visited.add(start)order.append(start)for nbr in graph[start]:if nbr not in visited:dfs(graph, nbr, visited, order)return order
Maps and navigation (shortest path). Social networks (friend suggestions, degrees of separation). Dependency resolution (npm, build systems, course prerequisites) which need topological sort. Web crawling and PageRank. Recommendation engines. Network routing. When a problem involves relationships, connections, or 'can I get from here to there,' it is almost certainly a graph problem.
Forgetting the visited set and looping forever on a cyclic graph. Using an adjacency matrix for a large sparse graph and wasting O(V squared) memory. Confusing BFS (queue, shortest unweighted path) with DFS (stack/recursion, deep exploration). Assuming BFS gives the shortest path on a weighted graph (it does not; you need Dijkstra). Recursing DFS on a graph with millions of nodes and overflowing the stack (use an explicit stack).
Sign in and purchase access to unlock this lesson.