Graphs

Also Known As

TL;DR

Explanation

A graph G = (V, E) has vertices V and edges E. Directed graphs have one-way edges; undirected have two-way. Weighted graphs assign costs to edges. Representations: adjacency matrix (O(V²) space, O(1) edge lookup), adjacency list (O(V+E) space, better for sparse graphs). Cycles: DAGs (Directed Acyclic Graphs) have no cycles — used for dependency resolution (Composer), build systems, and topological sorting. Trees are DAGs with one path between any two nodes.

Common Misconception

Why It Matters

Common Mistakes

• Adjacency matrix for sparse graphs — wastes O(V²) memory when most edges don't exist.
• Not detecting cycles before topological sort — Kahn's algorithm or DFS detects cycles.
• Treating directed edges as undirected — in a dependency graph, A depends on B is not the same as B depends on A.
• Infinite loops without a visited set in BFS/DFS on cyclic graphs.

Code Examples

// Adjacency matrix for sparse social graph — 1M users = 1TB memory:
$matrix = array_fill(0, 1000000, array_fill(0, 1000000, 0));
// 10^12 entries for a graph with ~1 billion edges

// Adjacency list — O(V+E) space:
$graph = [
    'A' => ['B', 'C'],
    'B' => ['D'],
    'C' => ['D', 'E'],
    'D' => [],
    'E' => [],
];
// Only stores actual edges — efficient for sparse graphs
// 5 vertices, 5 edges — exactly 10 entries total

References

• ↗ https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)

Tags

Related Terms