Graphs

A graph is a set of nodes (vertices) connected by edges. Graphs model relationships: social networks, road maps, dependencies, the internet, and DNS resolution.

Why It Matters

Many real-world problems are graph problems in disguise. If you need to find the shortest path, detect cycles, or model connections, you need graphs. DFS, DP on graphs, and service dependency graphs all require this knowledge.

Types

Type	Edges	Example
Undirected	A — B (both ways)	Facebook friendships
Directed	A → B (one way)	Twitter follows
Weighted	Edges have costs	Road distances
Unweighted	All edges equal	Social connections
Cyclic	Contains loops	Road networks
Acyclic	No loops	DAGs, dependency trees

Representation

Adjacency List (most common)

# Dict of lists — good for sparse graphs
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C'],
}

Adjacency Matrix

# 2D array — good for dense graphs or when you need O(1) edge check
#     A  B  C  D
# A [[0, 1, 1, 0],
# B  [1, 0, 0, 1],
# C  [1, 0, 0, 1],
# D  [0, 1, 1, 0]]

	Adjacency List	Adjacency Matrix
Space	O(V + E)	O(V^2)
Check if edge exists	O(degree)	O(1)
Get neighbors	O(1)	O(V)
Best for	Sparse graphs	Dense graphs

Code Example

from collections import defaultdict, deque
 
class Graph:
    def __init__(self, directed=False):
        self.adj = defaultdict(list)
        self.directed = directed
 
    def add_edge(self, u, v, weight=1):
        self.adj[u].append((v, weight))
        if not self.directed:
            self.adj[v].append((u, weight))
 
    def bfs(self, start):
        """Breadth-first traversal — visits nodes level by level."""
        visited = {start}
        queue = deque([start])
        order = []
        while queue:
            node = queue.popleft()
            order.append(node)
            for neighbor, _ in self.adj[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        return order
 
    def dfs(self, start):
        """Depth-first traversal — goes deep before backtracking."""
        visited = set()
        order = []
        def _dfs(node):
            visited.add(node)
            order.append(node)
            for neighbor, _ in self.adj[node]:
                if neighbor not in visited:
                    _dfs(neighbor)
        _dfs(start)
        return order
 
g = Graph()
for u, v in [('A','B'), ('A','C'), ('B','D'), ('C','D')]:
    g.add_edge(u, v)
 
print(g.bfs('A'))  # ['A', 'B', 'C', 'D']
print(g.dfs('A'))  # ['A', 'B', 'D', 'C']

Common Graph Algorithms

Algorithm	Problem	Time
BFS	Shortest path (unweighted)	O(V + E)
DFS	Cycle detection, topological sort	O(V + E)
Dijkstra	Shortest path (weighted, no neg)	O((V+E) log V)
Bellman-Ford	Shortest path (negative weights)	O(V * E)
Kruskal/Prim	Minimum spanning tree	O(E log E)
Topological sort	Dependency ordering (DAG)	O(V + E)

Related

• Trees and Binary Search Trees — trees are acyclic connected graphs
• BFS and DFS — fundamental graph traversal
• Dynamic Programming — many graph problems use DP
• Microservices vs Monolith — service dependency graphs