🕸️ Graph

A graph is a set of vertices ($V$) connected by edges ($E$) — the general case, with no hierarchy or root. Edges may be directed or undirected, weighted or not.

flowchart LR
    A --- B
    A --- C
    B --- D
    C --- D
    D --- E

Every other non-linear structure in this series — trees included — is really a graph with an extra constraint bolted on (a tree is a connected, acyclic graph with a designated root). A plain graph drops all of those constraints, which is exactly why it's the most general and the most common shape for representing real-world relationships: social networks, road maps, dependency graphs, call graphs.

---

Adjacency List vs Matrix

There's no single Big O for a graph because it isn't one structure — the representation is the design decision:

Representation	Space	Edge lookup	Best when
Adjacency list	$O(V+E)$	$O(\deg v)$	Sparse graphs (most real graphs)
Adjacency matrix	$O(V^2)$	$O(1)$	Dense graphs, frequent edge checks

flowchart LR
    subgraph Matrix["Adjacency Matrix — O(V^2) space"]
        direction TB
        M["    A B C<br/>A [ 0 1 1 ]<br/>B [ 1 0 0 ]<br/>C [ 1 0 0 ]"]
    end

    subgraph List["Adjacency List — O(V+E) space"]
        direction TB
        LA["A → [B, C]"]
        LB["B → [A]"]
        LC["C → [A]"]
    end

An adjacency matrix answers "are A and B connected?" in $O(1)$ — just index into the grid — at the cost of $O(V^2)$ space even if the graph barely has any edges. An adjacency list only stores edges that actually exist, so it's $O(V+E)$ space, but checking a specific edge means scanning that node's neighbor list. This is the exact same space-vs-lookup tradeoff a hash table's chaining makes at the bucket level, just applied at the whole-graph level: dense connectivity favors the matrix, sparse connectivity favors the list — and most real-world graphs are sparse, which is why adjacency lists dominate in practice.

---

Traversal: BFS and DFS

Traversal is where the actual work lives — BFS and DFS both visit every vertex and edge once, so they run in $O(V+E)$ on a list and $O(V^2)$ on a matrix.

	Breadth-First Search (BFS)	Depth-First Search (DFS)
Explores	Level by level, all neighbors before going deeper	One path fully before backtracking
Data structure	Queue	Stack (or recursion)
Finds	Shortest path in an unweighted graph	Any path; good for exhaustive exploration
Typical use	Shortest path, level-order processing	Cycle detection, topological sort, connected components

Everything downstream builds on these two walks: shortest paths, connectivity, topological sort, and cycle detection are all BFS or DFS with extra bookkeeping layered on top — there is no graph algorithm that avoids visiting vertices and edges at least once, so $O(V+E)$ (or $O(V^2)$ on a matrix) is the practical floor for anything that needs to reason about the whole graph.

---

Key Takeaways

Concept	Summary
No single Big O	A graph's complexity depends entirely on its representation, not the abstract structure
Adjacency list	$O(V+E)$ space, $O(\deg v)$ edge lookup — wins for sparse graphs (most real ones)
Adjacency matrix	$O(V^2)$ space, $O(1)$ edge lookup — wins for dense graphs or frequent edge checks
BFS / DFS	Both visit every vertex and edge once — $O(V+E)$ on a list, $O(V^2)$ on a matrix — the floor every graph algorithm builds on
Trees are graphs	A tree is just a connected, acyclic graph with a root — every tree structure in this series is a constrained special case of a graph

The representation choice isn't a detail — it's the entire performance profile of every algorithm that runs on the graph afterward. Picking adjacency list vs matrix before writing a single traversal is the graph equivalent of picking the right data structure before writing the rest of the program.

---

Related Posts

• 🧱 Data Structures — linear structures and the Heap/Hash Table/Trie that round out the non-tree, non-graph structures
• 🌲 Non-Linear Data Structures — trees are graphs with a root and no cycles; see how BST/AVL/Red-Black build on that constraint
• 🔢 Algorithmic Complexity — the Big O notation used throughout this post