Graphs

Basics

• A graph is a set of nodes (vertices, $V$) and edges ($E$) connecting them. A node can point to itself, and $E \le V^2$.
• Types:
  • Directed: edges have a direction (A to B is not B to A). Undirected: edges go both ways, so store each edge twice.
  • Weighted: edges carry a cost. Unweighted: all edges cost the same.
  • Cyclic or acyclic. A directed acyclic graph is a DAG.
  • Connected or disconnected: loop over all nodes when starting a traversal, since one start may not reach everything.
• A tree is a connected, undirected graph with no cycles and exactly $V - 1$ edges.

Representations

• Matrix (grid): each cell is a node and its neighbors are the adjacent cells. Values such as 0 or 1 usually mean open or blocked. Use a directions array ([0,1], [0,-1], [1,0], [-1,0]) and bounds checks. See Matrix DFS and Matrix BFS.
• Adjacency matrix: a $V \times V$ array where m[i][j] is 1 (or the weight) if there is an edge from i to j. For undirected graphs it is symmetric (m[j][i] is set too). It takes the same space even for sparse graphs.
• Adjacency list: a hash map from each node to the list of its neighbors, built from an edge list. In the worst case a graph has about $V^2/2$ edges, which makes it $O(V^2)$ too. See Adjacency List.
• Inputs arrive as an edge list ([[a, b], ...]); convert it to an adjacency list first. Remember to add the reverse edge for undirected graphs.

BFS vs DFS

• BFS layer by layer: loop len(queue) times per level and increment the distance after each level. Mark nodes visited when they are pushed, not when popped, to avoid duplicates in the queue.
• Multi-source BFS: push all sources first (for example all rotten oranges) and run a single BFS.
• Counting all paths with backtracking requires removing the node from visited after exploring it. This is exponential: up to $O(4^{n \cdot m})$ on a grid, versus $O(n \cdot m)$ for plain DFS with a permanent visited set.
• Plain adjacency list BFS is $O(V + E)$ time and $O(V)$ space.
• Do not reset visited inside the recursive call; it must be shared across calls (create it once).

Cycle detection

• Undirected graph: DFS with a visited set; reaching a visited node that is not the parent means a cycle. Union-Find also works: an edge whose endpoints already share a root closes a cycle (see Union-Find).
• Directed graph: DFS with two sets.
  • Add the node to the path (in-progress) set before recursing into its neighbors and remove it afterwards.
  • Meeting a node that is currently in path means a cycle.
  • After finishing a node, add it to a completed set (or keep it in visited) so that it is not explored again.
• Alternatively run Topological Sort (Kahn’s algorithm): if fewer than $V$ nodes are output, there is a cycle.

Shortest path

• Unweighted: BFS, $O(V + E)$.
• Non-negative weights: Dijkstra’s, single source to all nodes. BFS is not enough on weighted graphs.
  • Greedy: always expand the unvisited node with the smallest known distance (min heap of (distance, node)). The first time a node is popped, its distance is final.
  • Skip nodes already finalized when popping (stale heap entries).
  • Time $O(E \log V)$ ($O(E \log E)$ is equivalent), space $O(V + E)$.
  • Does not work with negative edge weights; use Bellman-Ford instead ($O(V \cdot E)$).
  • Unreachable nodes remain without a distance; decide on a sentinel such as -1 or infinity.
• Variants: the “weight” can be a different cost, for example the maximum height along a path (Swim in Rising Water) or a probability multiplied along edges (Path with Maximum Probability, using a max heap).

Minimum spanning tree (MST)

A spanning tree connects all $V$ vertices of a connected, undirected, weighted graph with $V - 1$ edges and no cycle; the MST has the minimum total weight.

• Both produce an MST with $V - 1$ edges for a connected graph; the tree may not be unique when weights tie.
• Kruskal: stop once $V - 1$ edges have been added. If the graph is disconnected, the result is a minimum spanning forest.
• Prim: a node popped that is already visited is skipped, which is what avoids cycles.

Union-Find (disjoint set)

• Tracks connected components with find(x) (root of the component) and union(a, b) (merge two components, returning false if already connected).
• With path compression and union by rank or size, each operation is nearly $O(1)$ (inverse Ackermann).
• Use it for: dynamic connectivity, counting components, detecting the edge that creates a cycle, grouping (accounts merge), Kruskal’s. See Union-Find.

Topological sort

• A linear ordering of a DAG’s nodes such that for every edge A to B, A comes before B. Only possible if the graph has no cycle. Time $O(V + E)$.
• DFS version: run DFS from every unvisited node, append a node to the result after all its neighbors are done (postorder), then reverse the result. A node that finishes last goes first.
• Kahn’s (BFS) version: compute in-degrees, start from nodes with in-degree 0, and when removing a node decrement its neighbors’ in-degrees, queueing those that reach 0. If the output has fewer than $V$ nodes, the graph has a cycle.
• Recognition: “prerequisites”, “dependencies”, “order of tasks”, “build order”, “alien dictionary”.

See Topological Sort.

Problem signal to algorithm

Templates

• Matrix DFS: grid DFS, counting paths with backtracking.
• Matrix BFS: grid BFS for the shortest path.
• Adjacency List: building an adjacency list, then DFS path counting and BFS shortest path.
• Dijkstra’s: shortest paths from a source with a min heap.
• Prim’s: minimum spanning tree grown from a start node.
• Kruskal’s: minimum spanning tree by sorted edges and Union-Find.
• Union-Find: disjoint set with path compression and union by rank.
• Topological Sort: ordering of a DAG.

Problems