🕸️ PHP Graph Basics

Graph Representations

Adjacency List (Most Common)

// Undirected graph
$graph = [
    0 => [1, 2],
    1 => [0, 3],
    2 => [0, 4],
    3 => [1],
    4 => [2],
];

// Directed graph (0→1, 1→2, 2→3)
$directed = [
    0 => [1],
    1 => [2],
    2 => [3],
    3 => [],
];

Adjacency Matrix

// n×n matrix; matrix[i][j] = 1 means edge from i to j
$n = 4;
$matrix = array_fill(0, $n, array_fill(0, $n, 0));
$matrix[0][1] = 1; // 0→1
$matrix[1][2] = 1; // 1→2

Adjacency list: O(V + E) space — preferred for sparse graphs. Adjacency matrix: O(V²) space — preferred for dense graphs or O(1) edge lookup.

---

Build Graph from Edge List

function buildGraph(int $n, array $edges): array {
    $graph = array_fill(0, $n, []);
    foreach ($edges as [$u, $v]) {
        $graph[$u][] = $v;
        $graph[$v][] = $u; // remove for directed
    }
    return $graph;
}

$graph = buildGraph(5, [[0,1],[0,2],[1,3],[2,4]]);

---

Graph Terminology

---

Union-Find (Disjoint Set Union)

Essential for connected components and cycle detection.

class UnionFind {
    private array $parent;
    private array $rank;

    public function __construct(int $n) {
        $this->parent = range(0, $n - 1);
        $this->rank   = array_fill(0, $n, 0);
    }

    public function find(int $x): int {
        if ($this->parent[$x] !== $x)
            $this->parent[$x] = $this->find($this->parent[$x]); // path compression
        return $this->parent[$x];
    }

    public function union(int $x, int $y): bool {
        $px = $this->find($x);
        $py = $this->find($y);
        if ($px === $py) return false; // already connected
        if ($this->rank[$px] < $this->rank[$py]) [$px, $py] = [$py, $px];
        $this->parent[$py] = $px;
        if ($this->rank[$px] === $this->rank[$py]) $this->rank[$px]++;
        return true;
    }

    public function connected(int $x, int $y): bool {
        return $this->find($x) === $this->find($y);
    }
}

Time: O(α(n)) ≈ O(1) per operation | Space: O(n)

---

Complexity Summary