12. Graphs and Representations

Why Graphs?#

A list gives each item a next item. A rooted tree gives each node children. But a road junction can connect to several other junctions, and following roads may bring us back to where we started. We need a structure that allows arbitrary relationships.

A graph $G=(\mathcal V,\mathcal E)$ consists of a set of vertices $\mathcal V$ and a set of edges $\mathcal E$ connecting pairs of vertices. A vertex represents an item; an edge represents a relationship. We write $V=|\mathcal V|$ for the number of vertices and $E=|\mathcal E|$ for the number of edges. These counts, rather than just one $n$, determine graph costs.

Read each city as a vertex and each road as an edge. The line's length on the page is irrelevant: the number on it is the distance. PER–ADL is one edge; PER–ADL–MEL is a route of two edges with cost $2716+732=3448$. Whether that route is cheapest requires considering alternatives.

The same abstraction represents webpages and hyperlinks, people and friendships, game states and legal moves, or tasks and prerequisites. Choosing what the vertices and edges mean comes before choosing an algorithm. In a maze, vertices might be open tiles and edges legal moves between adjacent tiles. Walls are then absent vertices or absent edges, rather than expensive moves.

Graph Types and Vocabulary#

An undirected edge joins two vertices symmetrically: $\{v,w\}$ allows travel either way. A directed edge $(v,w)$ allows travel from its source $v$ to its destination $w$. A weighted edge has a number such as cost, distance or travel time. An unweighted graph treats all edges equally.

A loop connects a vertex to itself. A multigraph permits multiple distinct edges between the same pair of vertices. The introductory lecture algorithms use simple graphs: undirected, with no loops or multiple edges. Later directed examples can contain loops. Do not carry the simple-graph assumptions into every representation automatically.

For a simple graph, every unordered pair of different vertices can contribute at most one edge. Vertex 0 has $V-1$ possible partners, but counting that for every vertex counts each pair twice. Therefore

$$0\leq E\leq \frac{V(V-1)}{2}.$$

A complete graph contains every possible edge; $K_V$ denotes the complete graph on $V$ vertices. A clique is a complete subgraph: a selected group of vertices all joined to one another. The slides call a clique of at least three vertices non-trivial. Searching every triple for a triangle takes polynomial time; finding a largest clique is a much harder problem.

Two vertices are adjacent when there is an edge between them. An edge is incident on its endpoints. The degree $\deg(v)$ counts edges incident on $v$. In a simple undirected graph,

$$\sum_{v\in\mathcal V}\deg(v)=2E,$$

because each edge contributes once at each endpoint. This identity will explain why scanning every adjacency list costs $O(E)$, rather than $O(VE)$.

A graph is sparse when its number of edges is on the scale of its vertices, and dense when it is on the scale of $V^2$. These are descriptions of graph families rather than a fixed percentage threshold. A chain on $V$ vertices has $V-1$ edges and is sparse. A complete graph has $V(V-1)/2$ edges and is dense.

Practice. A simple graph has 6 vertices and degrees $3,2,2,1,1,1$. How many edges does it have? Could every vertex instead have degree 6?

Paths, Cycles and Connectivity#

Following the lecture's terminology, a path is a sequence of vertices with an edge between consecutive vertices. Its length in an unweighted graph is the number of edges, not the number of vertices. A simple path repeats no vertex. A cycle closes back to its starting vertex, with no other repeated vertex and no repeated edge. In a simple undirected graph it therefore contains at least three edges: going out and back along one edge is excluded. Some texts use “walk” for the general sequence and reserve “path” for a simple path; read definitions rather than assuming the naming convention.

For instance, $0,1,3,4,5$ is a simple path of length 4. The sequence $0,1,2,0$ is a cycle of length 3. Going $0,1,0$ merely goes out and back along one undirected edge; it is not a cycle in this simple graph. A vertex is reachable from itself using the empty path, of length zero, unless a particular operation explicitly asks for positive-length paths.

An undirected graph is connected when every pair of vertices is joined by a path. A subgraph uses some original vertices and some original edges between them. A connected component is a maximally connected subgraph: no additional original vertex can be included while keeping that group connected. “Maximal” does not mean “largest”; there can be several components of different sizes.

The left group $\{0,1,2,3,4\}$ is one component even though vertex 3 has just one neighbour. The middle group $\{5,6,7,8,9\}$ is another, and $\{10,11\}$ is the third. An isolated vertex also counts as a component.

A tree is connected and contains no cycles. There is exactly one simple path between every pair of its vertices. If there were two different paths, their divergence and reunion would create a cycle. A tree on $V\geq1$ vertices has $V-1$ edges: each new vertex can be attached by one edge without creating a cycle.

A spanning tree of a connected graph keeps all its vertices and enough edges to form one tree. A spanning forest of a possibly disconnected graph keeps one tree per component. If there are $C$ components, the forest has $V-C$ edges: sum $V_i-1$ over its component sizes $V_i$. Traversals construct such forests in 13. Graph Traversal. We minimise their weight in 16. Minimum Spanning Trees.

Practice. Does a graph with $V-1$ edges have to be a tree?

The Graph ADT#

Recall 08. Abstract Data Types: an ADT describes available operations without exposing its representation. The lecture Graph ADT numbers vertices $0,\ldots,V-1$ and fixes the vertex set when constructed. We insert and remove edges, rather than renumbering vertices whenever the graph changes.

A typical interface supplies GraphNew, GraphFree, GraphNumVertices, GraphNumEdges, GraphIsAdjacent, GraphInsertEdge, and GraphRemoveEdge. typedef struct graph *Graph means clients hold a pointer to an opaque graph object. Only its implementation knows how edges are stored.

The ADT does not make every implementation equally fast. An algorithm that calls GraphIsAdjacent(g,v,w) for every possible $w$ scans $V$ possibilities, even if only two real neighbours exist. To obtain adjacency-list traversal bounds, the implementation must actually iterate over list entries.

Adjacency Matrices#

An adjacency matrix is a $V\times V$ table. edges[v][w] is true exactly when an edge exists. For a simple undirected graph the matrix is symmetric, and its diagonal is false. We store an edge twice, but count it once in nE.

Notice the two levels of pointers: edges points to an array of row pointers, and each row pointer points to an array of booleans. In the example, row 3 contains 1,1,1,0, so vertex 3 has neighbours 0, 1 and 2. The matrix contains eight true cells but four undirected edges.

Here is a complete small implementation matching that representation. It rejects invalid vertices with assertions, keeps duplicate insertion harmless, and terminates on allocation failure. It supports at most 10,000 vertices so its example allocation sizes remain bounded; the quadratic storage still makes large choices expensive.

#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

typedef int Vertex;
typedef struct graph *Graph;
struct graph {
    int nV, nE;
    bool **edges;
};

static void *checkedCalloc(size_t count, size_t size) {
    void *p = calloc(count, size);
    if (p == NULL) {
        fprintf(stderr, "out of memory\n");
        exit(EXIT_FAILURE);
    }
    return p;
}

Graph GraphNew(int nV) {
    assert(nV > 0 && nV <= 10000);
    Graph g = checkedCalloc(1, sizeof *g);
    g->nV = nV;
    g->edges = checkedCalloc((size_t)nV, sizeof *g->edges);
    for (int v = 0; v < nV; v++)
        g->edges[v] = checkedCalloc((size_t)nV, sizeof *g->edges[v]);
    return g;
}

static void checkVertex(Graph g, Vertex v) {
    assert(g != NULL && v >= 0 && v < g->nV);
}
int GraphNumVertices(Graph g) { return g->nV; }
int GraphNumEdges(Graph g) { return g->nE; }
bool GraphIsAdjacent(Graph g, Vertex v, Vertex w) {
    checkVertex(g, v); checkVertex(g, w);
    return g->edges[v][w];
}
void GraphInsertEdge(Graph g, Vertex v, Vertex w) {
    checkVertex(g, v); checkVertex(g, w);
    assert(v != w);
    if (!g->edges[v][w]) {
        g->edges[v][w] = g->edges[w][v] = true;
        g->nE++;
    }
}
void GraphRemoveEdge(Graph g, Vertex v, Vertex w) {
    checkVertex(g, v); checkVertex(g, w);
    if (g->edges[v][w]) {
        g->edges[v][w] = g->edges[w][v] = false;
        g->nE--;
    }
}
void GraphFree(Graph g) {
    if (g == NULL) return;
    for (int v = 0; v < g->nV; v++) free(g->edges[v]);
    free(g->edges);
    free(g);
}

calloc sets each bool cell to zero, giving an initially empty graph. The graph owns all rows, the row-pointer array, and the wrapper. Freeing just g leaks the other allocations. The reverse ownership order in GraphFree avoids reading a freed wrapper.

Adjacency checks and edge updates access a constant number of cells, so take $O(1)$. Creating and clearing $V^2$ cells costs $\Theta(V^2)$ time and storage. Finding neighbours or degree scans one full row, costing $\Theta(V)$ even for an isolated vertex. Destruction makes $V+2$ calls to free, counted as $O(V)$ under the lecture's allocator model; that is not a claim that every real allocator's internal work is constant.

Practice. Why does insertion increment nE inside the if?

Adjacency Lists#

An adjacency list stores an array of $V$ list heads. List $v$ contains exactly the neighbours of $v$.

The same graph uses lists 0: 1,3, 1: 0,3, 2: 3, 3: 0,1,2. Its eight list nodes represent four undirected edges. A typical node contains a neighbour number and a next pointer, as in 01. C and Linked Lists. No list node owns the actual neighbouring vertex: the number refers to an entry in the graph's vertex set.

Storage is $\Theta(V+E)$: $V$ head pointers plus $2E$ nodes. Initialising the empty head array costs $\Theta(V)$, and freeing it with all nodes costs $\Theta(V+E)$. Iterating over neighbours costs $\Theta(\deg(v))$; summing across all vertices gives $2E$ list-node visits.

An adjacency check searches $v$'s list, costing $O(\deg(v))$. If duplicates must be prevented, insertion first searches the list and therefore has the same bound, even though linking a newly allocated node at the head is $O(1)$. For an undirected removal, we search and unlink entries in both endpoint lists, costing $O(\deg(v)+\deg(w))$. The slides summarise these as $O(V)$ worst-case bounds. On a sparse graph the local degrees are usually much smaller, so the more precise degree-based costs help explain the choice.

If input is guaranteed duplicate-free and insertion is allowed to put entries at the head without checking, insertion can be $O(1)$. That is a different contract. Sorted lists allow predictable traversal order but do not give binary search: following a linked list still requires walking through nodes.

Practice. A graph has one million vertices and two million undirected edges. Why are lists likely preferable to a matrix?

Arrays of Edges#

An edge array explicitly stores pairs (v,w) and, later, weights. For an undirected graph we can store each edge once, conventionally with v < w.

The wrapper separates nE, the occupied entries, from maxE, the allocated capacity. Empty capacity is not extra edges. nV must remain available because isolated vertices have no edge entry from which to infer their existence.

An unsorted edge array uses $O(E)$ storage, apart from vertex metadata, and scans up to $E$ entries for adjacency, neighbour enumeration or degree. Appending into spare capacity is constant time, but checking for duplicates first costs $O(E)$. Deleting can swap the last occupied entry into the gap after locating the edge; preserving sorted order instead requires shifting.

If edges are sorted lexicographically by source then destination, binary search can find a particular directed edge in $O(\log E)$. For undirected neighbour queries, storing both orientations makes all outgoing entries for a vertex contiguous. Locating the range's ends takes $O(\log E)$, and enumerating it takes an additional $O(\deg(v))$. Without both orientations, edges incident on a vertex may be scattered. The lecture tables' logarithmic edge-array claims rely on this ordering; an arbitrary edge array does not obtain them automatically.

Edge arrays suit algorithms that sort or scan all edges, such as Kruskal. Adjacency lists suit algorithms that repeatedly ask for one vertex's neighbours, such as BFS.

More exam-style practice#

Work each prompt before opening its answer. State the invariant or cost assumption that makes your reasoning valid.

Question 1. An undirected simple graph has 8 vertices and 12 edges. How many matrix cells and adjacency-list edge entries does its usual representation store?

Question 2. Vertices A,B,C have edges A→B and B→C. Is there a path from C to A? How would the answer change if edges were undirected?

Question 3. Why can an adjacency matrix test one edge in O(1) while listing all neighbours of a vertex takes O(V)?

Directed and Weighted Representations#

For a directed graph, store an edge only from source to destination. A matrix need not be symmetric; a list contains outgoing neighbours; an edge array stores ordered pairs. The out-degree counts outgoing edges and in-degree counts incoming edges. Their sums both equal $E$.

In this diagram, vertex 1 has an empty outgoing list even though arrows arrive there. Vertex 3's list contains 3 because it has a loop. You cannot find all incoming neighbours by inspecting only its outgoing list. With ordinary outgoing lists, computing all indegrees takes a scan of every edge, $O(V+E)$ including initialisation.

A weighted matrix stores a weight in each present cell. It needs an unambiguous “no edge” value: zero cannot serve that role if zero-weight edges are legal. An alternative is separate presence and weight matrices. A weighted list node adds a weight field, and a weighted edge array stores triples (source,destination,weight).

Read (1,0.2) in row 0 as the edge $0\to1$ of weight 0.2. It is not vertex 1's total distance from a source; shortest-path algorithms compute that separately. Direction and weight are independent choices: an undirected weighted edge still appears in both endpoint lists with the same weight.

Practice. For edges $0\to1$, $2\to1$, $2\to2$, give vertex 2's indegree and out-degree. Does the loop add two to either count?