Skip to content

Graph Terms & Representations

In one sentence

Most graph questions are asked in a small set of words (path, cycle, component, degree, tree, bipartite…); learn what each one means on a picture, then pick one of three ways to store the graph: adjacency list, adjacency matrix or edge list.

This page is the lesson of 19 September. It goes over the words once more, adds weights to every way of storing a graph, and ends with the 20-question quiz from class. For the first introduction (May) see Graph Basics. Slides: Basics of Graphs (.pptx).

1. The words, one picture at a time

The pictures in this section are the ones from our slides Basics of Graphs.

This graph has \(n = 5\) nodes and \(m = 7\) edges.

Word What it means In the picture
path a walk along edges from one node to another the red path \(1 \to 3 \to 4 \to 5\)
length of a path how many edges it uses (not nodes) \(1 \to 3 \to 4 \to 5\) uses 3 edges, so length 3
cycle a path whose first and last node are the same \(1 \to 3 \to 4 \to 1\)
simple path no node appears twice \(1 \to 3 \to 4 \to 5\) is simple
neighbours of \(u\) the nodes joined to \(u\) by an edge neighbours of 2 are \(\{1, 4, 5\}\)
degree of \(u\) how many neighbours \(u\) has degree of 2 is 3

Degree sum. Add up all the degrees of the graph above: node 1 has 3, node 2 has 3, node 3 has 2, node 4 has 4, node 5 has 2. That is \(3 + 3 + 2 + 4 + 2 = 14 = 2 \times 7\). Every edge touches two nodes and adds 1 to each of them, so the degree sum is always \(2m\), and therefore always even.

1.1 Connected graphs and components

A graph is connected if there is a path between every pair of nodes. The left graph is connected. The right one is not: node 4 cannot reach anyone.

When a graph is not connected, it falls apart into pieces. Each piece is a connected component.

Here the pieces are \(\{1, 2, 3\}\), \(\{4, 5, 6, 7\}\) and \(\{8\}\): 3 components. Node 8 has no edges at all, but it is still a node and a component on its own.

1.2 Trees

A tree is a connected graph with \(n\) nodes and exactly \(n - 1\) edges. This one has 5 nodes and 4 edges:

Why \(n - 1\)? Start with node 1 alone. Each edge you add brings in exactly one new node. To bring in the other \(n - 1\) nodes you need \(n - 1\) edges; one more edge would join two nodes that are already connected and close a cycle. That is also why, in a tree, there is exactly one path between any two nodes.

1.3 Directed graphs

In a directed graph each edge is a one-way arrow. Below, \(3 \to 1 \to 2 \to 5\) is a path, but there is no path from 5 to 3.

A node now has an indegree (arrows that end at it) and an outdegree (arrows that start at it). Below, node 2 has indegree 2 (from 1 and from 5) and outdegree 1 (to 4). Every arrow adds 1 to one outdegree and 1 to one indegree, so both sums equal \(m\).

1.4 Weighted graphs

In a weighted graph each edge carries a number (a length, a cost, a time). The length of a path is the sum of its weights.

\(1 \to 2 \to 5\) costs \(5 + 7 = 12\), while \(1 \to 3 \to 4 \to 5\) costs \(1 + 7 + 3 = 11\). The path with more edges is the shorter one.

1.5 Simple graphs

A graph is simple when it has no self-loop (an edge from a node to itself) and no multiple edges (two edges between the same pair). The graph below is not simple: there is a self-loop at 4 and two edges between 2 and 3.

Most problems say this in words: "no road connects a city to itself", "no two roads join the same pair of cities".

1.6 Colouring and bipartite graphs

Colouring a graph means giving each node a colour so that the two ends of every edge have different colours. A graph is bipartite if two colours are enough. This one is:

This one is not:

Follow the red cycle \(1 \to 2 \to 5 \to 1\). Colour 1 blue, then 2 must be red, then 5 must be blue, but 5 is also next to 1, which is blue. Any cycle with an odd number of edges gets stuck the same way: going around, the colours must alternate, and after an odd number of steps you arrive back at the start with the wrong colour. On an even cycle the alternation closes up fine. So:

a graph is bipartite exactly when it has no odd cycle.

2. Three ways to store a graph

The running example is the directed, weighted graph from the slides:

2.1 Adjacency list

For every node, keep the list of nodes its arrows point to. With weights, store the pair (where it goes, weight):

vector<vector<pair<int, int>>> adj(n + 1);
adj[1].push_back({2, 5});
adj[2].push_back({3, 7});
adj[2].push_back({4, 6});
adj[3].push_back({4, 5});
adj[4].push_back({1, 2});

Going over all edges out of a node s is one loop:

for (auto [v, w] : adj[s]) {
    // edge s -> v with weight w
}

For an undirected graph, push every edge both ways.

From the lesson of 3 October. The unweighted list, read from the usual input, with the two questions we asked in class:

    // if we use u,v then it's the node index(name)
    // if we use i,j.. then it's the array index(place)
    // nodes are 1,2,3,...,n
    // adj[0], adj[1], ..., adj[n]
    vector<vector<int> > adj(n + 1); // 1-indexed -> size at least n+1
    // Q1: type of adj[u]? type of adj[u][0]?
    // A1: vector<int> and int.
    // we use adj[u][j] to store a neighbor of u
    // int v = adj[u][j];
    // Q2: meaning for adj[u]?
    // A2: it's a list of neighbors of node u


    // n nodes, m edges
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        // there's an edge between node u and node v
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // T1: print all the neighbors of node u in a line;
    int u = 10;
    for (auto v: adj[u]) {
        cout << v << " ";
    }

What the two structures look like before and after reading the edges:

at the start after reading the edges
vector<vector<int> > adj_list(maxn); n empty lists, adj_list[1].size() is 0 n lists, each one can have a different size
vector<vector<int> > adj_matrix(maxn, vector<int>(maxn)); n lists, each with n integers (all 0) still n lists with n integers, some 0 became 1

2.2 Adjacency matrix

An \(n \times n\) table: row \(a\), column \(b\) holds the weight of the edge \(a \to b\), or 0 if there is none (without weights, just 1 or 0).

1 2 3 4
1 0 5 0 0
2 0 0 7 6
3 0 0 0 5
4 2 0 0 0

Reading it:

  • Row \(a\) lists the arrows leaving \(a\). Row 2 has two non-zero cells (to 3 and to 4), so the outdegree of 2 is 2.
  • Column \(b\) lists the arrows arriving at \(b\). Column 4 has two non-zero cells (from 2 and from 3), so the indegree of 4 is 2.
  • The path \(1 \to 2 \to 3 \to 4\) costs adj[1][2] + adj[2][3] + adj[3][4] \(= 5 + 7 + 5 = 17\).
  • For an undirected graph each edge is written twice, adj[a][b] and adj[b][a], so the table is a mirror image across its diagonal.

Two things to watch:

  • Nodes numbered \(1 \dots n\) need a table of size \((n + 1) \times (n + 1)\). With adj(n, vector<int>(n)) the last valid index is \(n - 1\), and adj[n][n] is out of range.
  • If an edge may have weight 0, then "0" can no longer mean "no edge". Use a huge number (or a separate true/false table) for "no edge" instead.

2.3 Edge list

Just keep every edge in one vector, in the order you read them:

vector<tuple<int, int, int>> edges;   // (from, to, weight)
edges.push_back({1, 2, 5});
edges.push_back({2, 3, 7});
edges.push_back({2, 4, 6});
edges.push_back({3, 4, 5});
edges.push_back({4, 1, 2});

This is the right choice when the algorithm simply goes through all edges (for example, sorting them by weight). It is the wrong choice when you need "the neighbours of \(u\)": you would scan the whole list every time.

2.4 Which one?

You mostly need to… Use Memory
walk from a node to its neighbours (BFS, DFS, shortest paths) adjacency list \(n + m\)
ask "is there an edge from \(a\) to \(b\)?" many times, and \(n\) is small adjacency matrix \(n^2\)
go through every edge, maybe after sorting edge list \(m\)

Check the size before choosing the matrix: with \(n = 100\,000\) it has \(10^{10}\) cells, about 40 GB, even if the graph has only \(200\,000\) edges.

3. Quiz (19 September)

This is also problem D of problem set 8: print one answer per line. Try each question first, then open the answer.

1. Nodes and edges. What are \(n\) and \(m\) for the graph below?

A. \(n = 5, m = 4\) · B. \(n = 6, m = 8\) · C. \(n = 6, m = 4\) · D. \(n = 5, m = 8\)

Answer: C

Node 6 has no edges, but it is still a node, so \(n = 6\). Counting lines: 3 in the triangle plus the edge 4–5 gives \(m = 4\).

2. Path length. In the graph below, what is the length of the path \(1 \to 4 \to 2 \to 5\)?

A. 4 · B. 3 · C. 5 · D. 2

Answer: B

Length counts edges, not nodes: 1→4, 4→2, 2→5 is 3 edges.

3. Find the cycle. Which of these is a cycle in the same graph?

A. \(1 \to 2 \to 5 \to 1\) · B. \(1 \to 3 \to 5 \to 1\) · C. \(2 \to 3 \to 4 \to 2\) · D. \(1 \to 2 \to 4 \to 1\)

Answer: D

D uses 1–2, 2–4 and 4–1, which all exist, and it returns to 1. A needs 5–1, B needs 3–5, C needs 2–3; none of those edges exist.

4. Connected components. How many components does the graph of question 1 have?

A. 3 · B. 2 · C. 1 · D. 4

Answer: A

\(\{1, 2, 3\}\), \(\{4, 5\}\) and node 6 by itself.

5. Degree. In the graph of question 2, what is the degree of node 4?

A. 3 · B. 4 · C. 5 · D. 2

Answer: B

Edges at 4: 1–4, 2–4, 3–4, 4–5. The neighbours are \(\{1, 2, 3, 5\}\), so the degree is 4.

6. Degree sum. A graph has 5 nodes with degrees \(3, 2, 2, 2, 1\). How many edges does it have?

A. 10 · B. 4 · C. 5 · D. 20

Answer: C

\(3 + 2 + 2 + 2 + 1 = 10\). Each edge adds 1 to both of its ends, so \(10 = 2m\) and \(m = 5\).

7. Indegree and outdegree. In the directed graph below, what are the indegree and outdegree of node 2?

A. in 1, out 3 · B. in 3, out 0 · C. in 4, out 4 · D. in 3, out 1

Answer: D

Arrows into 2: 1→2, 3→2, 4→2, so the indegree is 3. Arrows out of 2: only 2→5, so the outdegree is 1.

8. Shortest path. In the weighted graph below, how long is the shortest path from 1 to 4?

A. 7 · B. 8 · C. 10 · D. 6

Answer: A

Three ways: straight 1–4 costs 10; 1–2–4 costs \(4 + 4 = 8\); 1–3–4 costs \(2 + 5 = 7\). Fewer edges does not mean shorter.

9. Bipartite. Which graph is not bipartite?

A. Graph A · B. Graph B · C. Graph C · D. Graph D

Answer: D

The diagonal in D makes a triangle, an odd cycle, and a triangle cannot be coloured with two colours (§1.6). A is a cycle of 6 (even), B is a tree and C is a grid; all of them can alternate red and blue.

10. Reading an adjacency matrix. Below is the matrix of a directed graph; row \(a\), column \(b\) is adj[a][b]. Which statement is true?

A. \(2 \to 1\) is an edge · B. the graph has 6 edges · C. adj[4][1] = 1 means there is an edge \(4 \to 1\) · D. the outdegree of 2 is 1

Answer: C

adj[4][1] = 1 is exactly "there is an arrow from 4 to 1". A: adj[2][1] is 0. B: counting the 1s row by row gives \(1 + 2 + 1 + 1 = 5\). D: row 2 has two 1s, so the outdegree is 2.

11. Weighted adjacency matrix. Below is a weighted matrix (0 = no edge). What is the total weight of \(1 \to 2 \to 3 \to 4\)?

A. 11 · B. 17 · C. 16 · D. 18

Answer: B

1→2 is 5, 2→3 is 7, 3→4 is 5: \(5 + 7 + 5 = 17\). (11 would be \(1 \to 2 \to 4 = 5 + 6\).)

12. Storing an undirected edge. We read an undirected edge between \(a\) and \(b\). Which code stores it correctly in a matrix?

A. adj[a][b] = 1; · B. adj[a][b] = 1; adj[b][a] = 1; · C. adj[a][a] = 1; adj[b][b] = 1; · D. adj[b][a] = 1;

Answer: B

An undirected edge can be walked both ways, so both \(a \to b\) and \(b \to a\) are recorded. That is why the matrix of an undirected graph is symmetric.

13. Too big for a matrix. A graph has \(n = 100\,000\) and \(m = 200\,000\). Why is a matrix a bad idea?

A. it needs \(n^2 = 10^{10}\) cells, far too much memory · B. it cannot store undirected edges · C. it cannot check whether \(a\)–\(b\) is an edge · D. an int cannot hold \(100\,000\)

Answer: A

The matrix always has \(n \times n\) cells, however few edges there are. \(10^{10}\) ints is about 40 GB, and almost all of them would be 0.

14. True or false: some undirected graph has degrees adding up to 15.

Answer: False

The degree sum is \(2m\), always even.

15. True or false: every connected graph with \(n\) nodes and \(n - 1\) edges is a tree.

Answer: True

That is the definition of a tree (§1.2).

16. True or false: the graph below is not a simple graph.

Answer: True

Node 4 has a self-loop, which a simple graph does not allow.

17. True or false: the graph below can be coloured with 2 colours.

Answer: False

1, 2, 3 form a triangle: 1 red, 2 blue, and 3 is next to both, so no colour is left for it.

18. True or false: in the matrix of a directed graph, adding up column \(x\) gives the indegree of \(x\).

Answer: True

Column \(x\) holds every arrow that ends at \(x\). Adding up row \(x\) gives the outdegree.

19. True or false: nodes are numbered \(1 \dots n\); after vector<vector<int>> adj(n, vector<int>(n)); it is safe to use adj[n][n].

Answer: False

The indices go from 0 to \(n - 1\), so adj[n] is out of range. Use size \(n + 1\).

20. True or false: if a weighted matrix uses 0 for "no edge" and edges may have weight 0, the matrix can no longer tell the two apart.

Answer: True

Both cases show 0. Use a huge value (or a separate true/false table) for "no edge".

Credits & licenses
  • Terms, representations, running examples and all figures in §1–§2 are from our 19 September slides Basics of Graphs; the explanations and quiz are ours.
  • The adjacency-list code with the Q&A comments in §2.1 is from the lesson of 3 October, unchanged.