Data Structures and Algorithms with C · Lecture Notes
Chapter 15: Graphs
A graph is the most general data structure for holding objects together with the connections between them; linked lists and trees are special cases. This chapter opens with Euler's Königsberg bridge problem. It then defines the basic notions of vertex, edge, path, degree and connectivity, and proves the degree-sum theorem. The core of the chapter is how to store a graph in memory: the adjacency matrix, the adjacency list and its reverse, a sequential representation in a single array, the orthogonal list and the multilist are all built in C, and their memory and operation costs are compared. Next comes the basic operation on a graph, traversal. Depth-first search is written recursively and breadth-first search with a dynamic queue, and both are traced step by step. The last part uses the two traversals to find connected components, to look for cycles and to test whether a graph is bipartite. Every routine comes with a line-by-line walkthrough, a trace table and a complexity analysis.
Learning outcomes
- Define
- Use G = (V, E), directed and undirected graph, adjacency, subgraph, path, degree and connectivity correctly.
- Prove
- Justify that the degrees sum to 2e and that a connected graph has at least n − 1 edges.
- Implement
- Build the adjacency matrix, adjacency list, sequential array, orthogonal list and multilist in C, and draw how each looks in memory.
- Traverse
- Code depth-first (DFS) and breadth-first (BFS) search, trace them by hand and analyze them as O(n + e).
- Apply
- Find connected components, cycles and bipartiteness with DFS or BFS.
- Choose
- Pick the right representation by looking at the operations the problem needs: data structure first, code second.
15.1Introduction: bridges, maps and networks
The data structures so far imposed a particular shape on the relationships between items. In an array or a linked list every item has at most one predecessor and one successor. In a tree every node has a single parent, and children never point back up. Many real-world relationships fit neither pattern. Many roads leave a city and tangle with one another before meeting again in other cities. A computer in a network connects to several others, and the connections can form loops. The structure that records such relationships without imposing any restriction is called a graph.
15.1.1The seven bridges of Königsberg
The history of graph theory is usually dated to 1736. The city of Königsberg in East Prussia lay on both banks of the river Pregel, and two islands sat in the middle of the river. In the sketch on the left of Figure 15.1, the islands are labeled A and D and the banks B (south) and C (north). Seven bridges connected these four pieces of land: two from A to C, two from A to B, one from A to D, one from D to C and one from D to B.
The townspeople asked: can one start from any piece of land, cross every bridge exactly once and return to the starting point? Trial and error produced no answer. Leonhard Euler (pronounced “Oiler”) put aside the details of the map to settle the question. He drew each piece of land as a point and each bridge as a line joining two points. Today the points are called vertices (or nodes) and the lines edges. The resulting drawing is the graph on the right of the figure. There are two separate edges between A and C, because there are two separate bridges.
The importance of this abstraction is the following. What decides the question is not the size of the land masses, the length of the bridges or the bends of the river. All that matters is which piece connects to which, and by how many bridges. The position of a vertex on the paper is irrelevant as well: vertex A may be drawn to the left or to the right. The same graph can be drawn in many different ways. A drawing is only a picture; the graph itself consists of nothing but the connections.
Euler tied the question to a number. The number of edges touching a vertex is the degree of that vertex. Every time the walk enters an intermediate vertex, it must also leave it, and the entry and exit must use different bridges. So every visit uses up two of the vertex's edges. The starting vertex is in the same situation: the walk leaves it and finally enters it again. In a closed walk that uses every bridge once, the edges at every vertex must therefore be used up in pairs. Such a walk can exist only if every vertex has even degree. In Königsberg the degrees are 5, 3, 3 and 3, all four odd. The walk does not exist.
Euler's result still carries his name. A closed walk that traverses every edge of a connected graph exactly once is called an Euler circuit. Such a circuit exists if and only if all degrees are even. Necessity follows from the counting argument above; the proof of sufficiency is longer and belongs to a graph theory course. What matters in this chapter is that a question about a city map can be answered purely in terms of numbers and connections.
15.1.2Where graphs are used
Since Königsberg, graphs have entered almost every field of engineering. Their use is so widespread that it is harder to find a field that does not use graphs than to list the ones that do. Table 15.1 collects the main examples.
| Area | Vertex | Edge | Typical question |
|---|---|---|---|
| Electric circuits | Junction | Circuit element | What are the currents and voltages? |
| Project planning (activity networks) | Event or task | Precedence relation | When is the earliest the project can finish? |
| Chemistry | Atom | Bond | Do two molecules have the same structure? |
| Road and computer networks | City, router | Road, link | Which path is the shortest? |
| Transport networks | Depot, pump | Pipe (with capacity) | How much flow can pass from the source to the sink at most? |
| Infrastructure design | Village | Possible cable route | How can all villages be connected with the least cable? |
| Formal languages | State | Transition | Does the finite automaton accept this word? |
| Network reliability | Computer | Link | Is the network disconnected, and into how many pieces? |
Some of the questions in the table are classic problems known by name. The shortest path problem asks for the cheapest route between two cities on a map. The maximum flow problem asks how much oil or water a pipe network can carry per unit time. The minimum spanning tree problem asks to join all villages with the smallest total cable length. Trees are themselves graphs; topological sorting and finite automata are also defined on graphs. All of these problems rest on the same foundation: how to store a graph in memory and how to move around in it. This chapter builds exactly that foundation.
15.2Definitions and terminology
Every routine that deals with graphs relies on a few basic notions. This section defines them precisely and introduces the example graphs used in the rest of the chapter.
15.2.1Definition of a graph
A graph G = (V, E) consists of two finite sets. V(G) is a nonempty set of vertices. E(G) is a possibly empty set of edges, each a pair of vertices. The number of vertices is written n = |V| and the number of edges e = |E|.
Requiring the vertex set to be nonempty is a necessity: no operation on a graph without vertices would mean anything. The edge set, however, may be empty. A graph made of a single vertex, or of vertices that are not connected to one another at all, is also valid. In the sparse graph example below, 7 of the 11 vertices touch no edge.
If the order of an edge's two endpoints matters, the graph is directed (a digraph); if not, it is undirected. The notation shows the difference through the shape of the brackets:
- In an undirected graph an edge is an unordered pair and is written with ordinary parentheses: (v0, v1) and (v1, v0) are the same edge.
- In a directed graph an edge is an ordered pair and is written with angle brackets: <v0, v1> ≠ <v1, v0>. The first vertex, where the arrow starts, is called the tail; the second, where the arrow points, is the head: <tail, head>.
The edge set is a subset of the Cartesian product V × V of the vertex set with itself. This product contains all ordered pairs; a graph selects only some of them. The selected pairs say which vertex is connected to which.
Four small example graphs are used throughout the chapter. Figure 15.2 draws them, and Table 15.2 lists their vertex and edge sets.
| Graph | V(G) | E(G) | n | e |
|---|---|---|---|---|
| G1 | {0, 1, 2, 3} | {(0,1), (0,2), (0,3), (1,2), (1,3), (2,3)} | 4 | 6 |
| G2 | {0, 1, …, 6} | {(0,1), (0,2), (1,3), (1,4), (2,5), (2,6)} | 7 | 6 |
| G3 | {0, 1, 2} | {<0,1>, <1,0>, <1,2>} | 3 | 3 |
| G4 | {0, 1, …, 7} | {(0,1), (0,2), (1,3), (2,3), (4,5), (5,6), (6,7)} | 8 | 7 |
In the edge set of G3, <0,1> and <1,0> are written separately. In a directed graph these are two different edges; the presence of one does not require the other. In an undirected graph it is enough to write (0,1); (1,0) is just another way of writing the same edge.
Unless stated otherwise, the graphs in this chapter are simple: there is at most one edge between two vertices, and no edge connects a vertex to itself. An edge that connects a vertex to itself is called a self-loop. The Königsberg graph is not simple, since there are two edges between A and C. Such graphs are called multigraphs.
Assuming that <v, u> exists whenever <u, v> is given in a directed graph. In G3, <1,2> exists but <2,1> does not: nothing can be reached from 2. In an undirected graph every edge can be used in both directions; in a directed graph, only in the direction of the arrow.
15.2.2Adjacent vertices and subgraphs
If (v0, v1) is an edge of an undirected graph, v0 and v1 are adjacent, and the edge is incident on these two vertices. In a directed graph, if <v0, v1> exists, then v0 is adjacent to v1, and v1 is adjacent from v0.
In G1 every vertex is adjacent to the other three. In G2 the neighbors of 0 are 1 and 2; 3 and 4 are not adjacent to each other, because there is no edge between them. Both are adjacent to 1, but that does not make them adjacent to each other.
A graph G′ is a subgraph of G if V(G′) ⊆ V(G) and E(G′) ⊆ E(G).
The definition has a hidden condition: G′ must be a graph in its own right. That is, both endpoints of every edge in E(G′) must lie in V(G′). An edge with an unselected endpoint cannot enter the subgraph. Since the edge set may be empty, a single vertex is also a valid subgraph.
The number of subgraphs of a graph grows quickly. For G1 alone there are 26 = 64 ways to choose the edges, and the choices of vertices add to that. The figure shows only a few of them.
15.2.3Paths, connectivity and degree
A path from vertex vp to vertex vq is a sequence of vertices vp, vi1, …, vin, vq such that each of the pairs (vp, vi1), (vi1, vi2), …, (vin, vq) is in E(G). The length of a path is the number of edges it contains. In a directed graph the pairs must have the form <·,·>, that is, follow the direction of the arrows.
In G2, the sequence 3, 1, 0, 2, 5 is a path of length 4 from 3 to 5. A path whose vertices are all distinct is a simple path. A path with the same first and last vertex, no other repeated vertex and at least one edge is a cycle. In G1, 0, 1, 2, 0 is a cycle. Since G2 is a tree, it contains no cycle at all. In an undirected simple graph a cycle has at least three edges; the sequence 0, 1, 0 goes along an edge and comes back along the same edge, so it does not count as a cycle.
In an undirected graph, two vertices are connected if there is a path from v0 to v1. A graph is itself connected if every pair of distinct vertices (vi, vj) is connected.
G1 and G2 are connected. G4 is not connected: there is no path from 0 to 5. G4 consists of two separate parts. These parts are called connected components; components are treated in detail in the last section of this chapter.
The degree d(v) of a vertex is the number of edges that have it as an endpoint. In a directed graph, the number of edges coming into a vertex is its in-degree and the number of edges leaving it is its out-degree. The degree of the vertex is the sum of the two.
Among undirected examples, d(0) = 2 in G2, d(1) = 3 in G1 and d(4) = 1 in G2. In the directed graph G3, the two numbers are computed separately for each vertex (Table 15.3).
| Vertex | Incoming edges | In | Outgoing edges | Out | Degree |
|---|---|---|---|---|---|
| 0 | <1,0> | 1 | <0,1> | 1 | 1 + 1 = 2 |
| 1 | <0,1> | 1 | <1,0>, <1,2> | 2 | 1 + 2 = 3 |
| 2 | <1,2> | 1 | — | 0 | 1 + 0 = 1 |
Degree is always stated for a particular vertex. A sentence such as “the degree of G3 is 2” is meaningless; the correct statement is “the degree of vertex 0 in G3 is 2”. What can be said about a graph as a whole is its maximum degree or the sum of its degrees.
15.2.4The sum of the degrees
There is a simple but much-used relation between degrees and the number of edges.
In a graph G with n vertices and e edges, if di denotes the degree of the i-th vertex, then
d0 + d1 + … + dn−1 = 2e
holds.
The sum of the degrees is obtained by counting, at each vertex, the edges that touch it and adding up these counts. How many times is each edge counted in this sum? An edge (u, v) is counted once in the degree of u and once in the degree of v. It contributes to no other vertex's degree. So every edge makes exactly 2 contributions to the sum, and the total is 2e. The same argument works for a directed graph: <u, v> contributes one to the out-degree of u and one to the in-degree of v. ∎
The proof counts edges one by one, so having several edges between two vertices changes nothing. The theorem therefore also holds for multigraphs. In the Königsberg graph, 5 + 3 + 3 + 3 = 14 = 2 · 7. If self-loops are allowed, such an edge is counted as contributing 2 to the degree of its vertex, and the theorem still holds.
Figure 15.5 shows the theorem step by step on G1. Edges are added one at a time to an empty graph. Each addition raises the degrees of the two endpoints by one, so the total grows by 2. After all six edges are added, the total reaches 12.
The theorem has an immediate corollary: in any graph, the number of vertices of odd degree is even. Since the total 2e is even, the number of odd terms cannot be odd. This gives a quick first answer to the question “is there a graph with these degrees?”.
Is there a simple undirected graph with degree sequence (3, 3, 2, 2, 1)? Add the degrees: 3 + 3 + 2 + 2 + 1 = 11. The sum is odd, but by the theorem it must equal 2e, an even number. No such graph exists, and the question about the number of edges loses its meaning. Had the sequence been (3, 3, 2, 2, 2), the sum would be 12 and the number of edges 6. In that case the theorem gives only a necessary condition; whether the graph really exists must be shown separately by construction. For example, if the edge (0,2) is added to the cycle 0–1–2–3–4–0, the degrees are (3, 2, 3, 2, 2), and renaming the vertices gives the sequence.
The theorem matters for data structures as well. In the adjacency list of an undirected graph every edge appears twice, once in the list of one endpoint and once in the list of the other. The total number of items in the lists is the sum of the degrees, that is, 2e. A routine that scans all the lists therefore costs O(n + e). This is a line of reasoning that returns in almost every analysis below.
15.3Implementing a graph in memory
Concepts are understood by drawing them on paper, but a program cannot see a drawing. To a program, a graph is nothing but numbers and pointers in memory. The subject of this section is not discrete mathematics; it is the question “how do we store a graph in memory?” There are many representations of the same graph, and the choice among them determines the speed of the operations we will perform on it. Five representations are covered here:
- the adjacency matrix,
- the adjacency list and its inverse,
- a sequential representation in a single array,
- the orthogonal list for directed graphs, and
- the multilist.
On top of these comes the weighted representation, which attaches a cost to each edge. Three questions are asked of every representation: How much memory does it need? How fast can the question “is there an edge between u and v?” be answered? How fast can all the neighbors of a vertex be found? The speed of algorithms such as traversal depends most on this last question.
15.3.1The adjacency matrix
The adjacency matrix of a graph G with n vertices is a two-dimensional n × n array a. We have a[i][j] = 1 if (i, j) ∈ E(G) in an undirected graph, or <i, j> ∈ E(G) in a directed graph, and a[i][j] = 0 otherwise.
In C the matrix is stored in an integer array sized for the maximum number of vertices: int a[MAX_V][MAX_V];. Table 15.4 shows the matrices of G1 and G3 side by side.
| 0 | 1 | 2 | 3 | G3 | 0 | 1 | 2 | ||
|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | |
| 2 | 1 | 1 | 0 | 1 | 2 | 0 | 0 | 0 | |
| 3 | 1 | 1 | 1 | 0 |
Since (0,2) is an edge of G1, both a[0][2] and a[2][0] are 1. Every edge of an undirected graph is written into the matrix twice, in two cells symmetric about the diagonal. So the matrix of an undirected graph is symmetric: a[i][j] = a[j][i] for all i, j. In a simple graph there are no self-loops, so the diagonal is all zeros. The matrix of G3, on the other hand, is not symmetric: a[1][2] = 1 but a[2][1] = 0.
Symmetry can be used to save space. If only the lower or upper triangle of the matrix is stored, the number of cells roughly halves. But memory is still proportional to n(n − 1)/2 cells, so asymptotically it stays O(n²). The memory of the matrix does not depend on the number of edges at all: a graph with no edges and a complete graph take the same space. A 50-vertex int matrix takes 10,000 bytes with 4-byte ints.
Two operations are very easy with a matrix. Whether the edge (u, v) exists is found in O(1) by looking at a single cell. Adding or deleting an edge is just writing 1 or 0 into one cell, again O(1). The other operations require scanning rows:
- Degree. In an undirected graph the degree of i is the number of 1s in row i (or, equivalently, in column i). Since a row has n cells, the cost is O(n). In a directed graph the row sum gives the out-degree and the column sum the in-degree; together they read 2n cells, and the cost is again O(n). In G3 the out-degree of 2 is 0 (row 2 is empty) and its in-degree is 1 (there is one 1 in column 2).
- Number of edges. Count all the 1s and divide by two (Theorem 15.1). G1 has twelve 1s, so it has 6 edges. By symmetry it is enough to look at the upper triangle, but that still means n(n − 1)/2 cells. The cost never drops below O(n²).
- Neighbors of a vertex. The n cells of the row are scanned: O(n). The whole row is read even if the vertex has a single neighbor.
The last item determines the cost of traversal algorithms and is the real weakness of the matrix. In a sparse graph most rows are mostly zeros, but there is no way to skip the zeros.
The matrix of G4 and a symmetry check
The most frequent mistake when writing a matrix by hand is to record an edge in one direction only. Figure 15.6 shows G4, and Table 15.5 gives its correct matrix.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 2 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 3 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 4 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 5 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
| 6 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 |
| 7 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
Writing row 1 of G4 as 1 0 1 0 0 0 0 0 and row 7 as … 0 0 1. The extra 1 in the first row adds the nonexistent edge (1,2), and the 1 in the seventh row connects 7 to itself. Both break symmetry: a[1][2] = 1 while a[2][1] = 0. The correct row 1 is 1 0 0 1 0 0 0 0 (neighbors 0 and 3), and the correct row 7 is 0 0 0 0 0 0 1 0 (the only neighbor is 6). Checking the written matrix with the comparison a[i][j] == a[j][i] catches this error immediately.
The matrix can also be used to find connected components. Starting from one vertex, mark every vertex that can be reached; then restart from the first unmarked vertex. But finding the neighbors of each vertex is a row scan, that is O(n), so the total cost is O(n²). The same job is much cheaper with an adjacency list.
Degree from the matrix: code and trace
The routine that computes the degree of a vertex in a directed graph sums the row and the column separately:
int degree(int a[][MAX_V], int n, int v)
{
int j, out = 0, in = 0;
for (j = 0; j < n; j++)
out += a[v][j]; /* row */
for (j = 0; j < n; j++)
in += a[j][v]; /* column */
return out + in;
}- Line 1. When a two-dimensional array is passed as a parameter, the second dimension must be written:
int a[][MAX_V]. The compiler computes the address of a[v][j] as v · MAX_V + j and so must know the row length. The first dimension may be left empty.nis the actual number of vertices; only the upper-left n × n part of the array is used. - Line 3. Both counters are zeroed. If the initial value is forgotten, local variables start with indeterminate values and the result is random.
- Lines 4–5. Row
vis scanned:a[v][j]is 1 if the edge <v, j> exists. The sum is the out-degree. - Lines 6–7. Column
vis scanned:a[j][v]is 1 if the edge <j, v> exists. The sum is the in-degree. - Line 8. The sum of the two is returned.
If the routine is applied to an undirected graph, row and column are the same, so every edge is counted twice and twice the degree is returned. In an undirected graph the first loop alone is enough. Table 15.6 traces the call degree(a, 3, 1) on the matrix of G3.
| Step | Line | j | Cell read | out | in |
|---|---|---|---|---|---|
| 1 | 3 | — | — | 0 | 0 |
| 2 | 4–5 | 0 | a[1][0] = 1 | 1 | 0 |
| 3 | 4–5 | 1 | a[1][1] = 0 | 1 | 0 |
| 4 | 4–5 | 2 | a[1][2] = 1 | 2 | 0 |
| 5 | 6–7 | 0 | a[0][1] = 1 | 2 | 1 |
| 6 | 6–7 | 1 | a[1][1] = 0 | 2 | 1 |
| 7 | 6–7 | 2 | a[2][1] = 0 | 2 | 1 |
| 8 | 8 | — | return 2 + 1 | result 3 | |
Each loop runs exactly n times, and 2n cells are read in total. The cost is O(2n) = O(n) and is independent of the vertex's actual degree. The same routine returns 2 for vertex 0 and 1 for vertex 2 of G3; these values agree with Table 15.3.
15.3.2The adjacency list
Each row of the matrix is mostly full of zeros. The adjacency list does not store those zeros at all. Instead of each row of the matrix there is a linked list, and the list holds only the numbers of the columns that contain a 1.
In the adjacency list representation there is a linked list for each vertex i; the items of the list are the numbers of the neighbors of i. The head pointers of the lists are kept in an array graph of n entries: graph[i] points to the first item of the neighbor list of i.
The C declaration uses a self-referential structure:
#define MAX_V 50 /* max number of vertices */
typedef struct node *node_ptr;
typedef struct node {
int vertex; /* the neighbor's number */
node_ptr link; /* next neighbor in list */
} node; /* don't forget ';' and the name */
node_ptr graph[MAX_V]; /* one list per vertex */- Line 1.
MAX_Vis the largest number of vertices the program can hold. The array sizes are determined by this constant. - Line 2.
node_ptris the pointer type that points tostruct node, whose definition has not been written yet. In C a pointer to a structure can be declared before the structure is defined; the size of the structure need not be known. This order makes it easy to use a field that points to the structure's own type inside the structure. - Lines 3–6. Each list item carries two fields: the neighbor's number
vertexandlink, which points to the next item in the list. The definition ends with;after the closing}and the type namenode. If the semicolon is forgotten, the compiler usually reports the error on the following line, and the location of the error looks surprising. - Line 7. The
grapharray reserves a list head for each vertex. Since it is a global array, all its elements areNULLwhen the program starts; that is, every list is initially empty.
graph array. Each item has two compartments: the neighbor's number and the link to the next item. A slash marks a NULL link.In Figure 15.8 every vertex has three neighbors and every list has three items. There are 12 items in total, while G1 has 6 edges. In an undirected graph every edge appears once in the list of each of its endpoints. This is a disadvantage of the representation: the same information is stored in two places, and deleting an edge requires updating both lists.
The memory and time costs of lists are as follows:
- Memory. n heads and, in an undirected graph, 2e items: O(n + e). On x86-64 a
nodetakes 16 bytes (a 4-byteint, 4 bytes of padding and an 8-byte pointer); a head takes 8 bytes. - Degree. In an undirected graph the items in the list of i are counted: O(di). Compared with O(n) in the matrix, this is a big gain when the degree is small.
- Number of edges. The items in all lists are counted and divided by two: one must look at n heads and count 2e items, for a total of O(n + e). This is far less than O(n²) in the matrix, because in most graphs e is much smaller than n².
- Is (u, v) present? v is searched for in the list of u: O(du). This question was O(1) in the matrix; it is the only place where the list loses.
This is why the complexity of graph algorithms is usually written in terms of both n and e. The expression “O(n + e)” describes an algorithm that touches each vertex and each edge a constant number of times.
Undirected and directed examples
If the lists of the undirected graph G4 are kept sorted, counting the edges gets a little shorter. Every edge (i, j) appears in the list of both i and j. If only items with j > i are counted, every edge is counted once and there is no need to divide by two. In a sorted list the items with j < i are gathered at the front, for example the 1 and 2 in the list of 3. These items are skipped quickly and the rest are counted. The number of scanned items decreases, but the asymptotic cost is still O(n + e).
The situation is different in the directed graph G3. Since <0,1> and <1,0> are separate edges, every item is an edge and all of them must be counted. The list holds only outgoing edges: the number of items in graph[i] is the out-degree of i and is found in O(d). The in-degree, however, is not written in the list directly. To find the edges coming into i, one must walk through all the lists and count the items that contain i: O(n + e). If the in-degree is asked for often, this cost is unacceptable. The solution is to keep the reverse of the list as well, that is, a list of incoming edges. This inverse adjacency list is built in the next subsection.
A sparse graph: G5
The difference between the matrix and the list is best shown by a sparse graph. G5 has 11 vertices and only 2 edges: (1, 4) and (7, 8).
The adjacency list holds four items: graph[1] → 4, graph[4] → 1, graph[7] → 8 and graph[8] → 7. The remaining seven heads are NULL. In total 11 heads and 2e = 4 items are stored. The matrix, on the other hand, needs 11 × 11 = 121 cells; only 4 of them are 1, and 117 cells are wasted.
A general rule follows: for a sparse graph (e small compared with n²) consider the list, and for a dense graph (e close to n²) the matrix. In a dense graph the pointers of the list take much more room than the bits of the matrix. But the decision is not made on density alone. The real criterion is the operations the program will perform on the graph. If the program constantly asks “are these two vertices adjacent?”, the matrix can be faster even for a sparse graph. If the program walks through the neighbors of every vertex, the list can be the better fit even for a dense graph.
15.3.3Building the list: adding an edge
In the examples, a person drew the lists by looking at the graph. A program cannot look at the graph. The edges reach it one at a time from a file or from the user, and each must be added to the structure the moment it arrives. The routine that does this is:
void add_edge(int u, int v) /* u -> v */
{
node_ptr p = malloc(sizeof(node));
if (p == NULL) exit(1); /* out of memory */
p->vertex = v;
p->link = graph[u]; /* at front: O(1) */
graph[u] = p;
}- Line 1. The routine adds a single edge in the direction u → v: it puts v into the list of u. For an undirected edge (u, v) the routine is called twice, as
add_edge(u, v)andadd_edge(v, u). - Line 3. Heap memory is allocated for the new item. The
void *returned bymalloccan be assigned tonode_ptrin C without a cast. Writingsizeof(node_ptr)instead ofsizeof(node)is a common mistake: only the size of a pointer (8 bytes) is allocated, whereas the item is 16 bytes, and later assignments write into unallocated memory. - Line 4. If
malloccannot find memory, it returnsNULL. Without the check, the next line writes through aNULLpointer and the program crashes. The simplest reaction is chosen here: the program terminates with an error code. - Line 5. The neighbor's number is written into the item.
- Line 6. The link of the new item points to the current first item of the list. If the list is empty this value is
NULL, and the new item is also the last item of the list. - Line 7. The list head points to the new item. The order of lines 6 and 7 matters: if line 7 were written first, the old list head would be lost and the rest of the list would be unreachable.
The routine does not scan the list; every edge is placed in a constant number of steps, O(1). An undirected graph with e edges is built with 2e calls; with the zeroing of the heads included, construction takes O(n + e).
Table 15.7 traces how the lists form when the edges arrive in the order (0,1), (0,2), (1,2). In the table, &node(k) denotes the address of the item whose neighbor number is k.
| Call | p->vertex | p->link | graph[0] | graph[1] | graph[2] |
|---|---|---|---|---|---|
add_edge(0, 1) | 1 | NULL | 1 | — | — |
add_edge(1, 0) | 0 | NULL | 1 | 0 | — |
add_edge(0, 2) | 2 | &node(1) | 2 → 1 | 0 | — |
add_edge(2, 0) | 0 | NULL | 2 → 1 | 0 | 0 |
add_edge(1, 2) | 2 | &node(0) | 2 → 1 | 2 → 0 | 0 |
add_edge(2, 1) | 1 | &node(0) | 2 → 1 | 2 → 0 | 1 → 0 |
graph[0] and 0 in graph[1]. Bottom: after all six calls. Since every new item enters at the front of its list, the lists are in the reverse of the arrival order.In the end the list of 0 is 2 → 1, although the edges arrived in the order 1, 2. Insertion at the front reverses the list relative to the arrival order. This is not a bug, but it affects the output of traversal algorithms, because a traversal visits neighbors in the order of the list. That a change in list order changes the traversal order is clearly visible in the examples in the traversal section.
Inserting at the front, at the end or in sorted order
An item can enter the list in three places. The choice depends on the desired order and cost (Table 15.8).
| Method | One insertion | List order | Note |
|---|---|---|---|
| Insert at front | O(1) | Reverse of arrival order | Construction O(n + e) |
| Insert at end (walking) | O(d) | Arrival order | Walk to NULL every time |
| Insert at end (with a tail pointer) | O(1) | Arrival order | Keep an extra last[i] for every list |
| Sorted insertion | O(d) | Ascending | Traversal order becomes predictable |
Sorted lists do not depend on the order in which the graph was built; the traversal output depends only on the graph. This is why the lists in the trace examples of this chapter are sorted. Sorted insertion is written compactly with the pointer-to-pointer technique familiar from linked lists:
void sorted_insert(int u, int v) /* v into list u, ascending */
{
node_ptr *pp = &graph[u]; /* pointer to pointer */
node_ptr p;
while (*pp && (*pp)->vertex < v)
pp = &(*pp)->link;
p = malloc(sizeof(node));
if (p == NULL) exit(1);
p->vertex = v;
p->link = *pp;
*pp = p;
}pp holds the address of the pointer field to be modified. Initially this field is graph[u]. While the loop skips items smaller than v, it advances pp to the link field of each item. When the loop ends, *pp points to the item in front of which the new item will go (or to NULL). The new item is written into the place of *pp. Insertion at the head, in the middle and at the end is done with the same two lines; special cases such as “is the list empty, or are we inserting at the head?” are not needed.
Giving the memory back
Every malloc call must be matched by a free call. At the end of the program, or when the graph is no longer needed, every list graph[i] is walked and its items are released:
void free_lists(node_ptr adj[], int n)
{
int i;
node_ptr p;
for (i = 0; i < n; i++) {
while (adj[i]) {
p = adj[i];
adj[i] = p->link; /* save link first */
free(p);
}
}
}The order inside the loop is the familiar rule for linked lists: the link is saved before the item is released. Reading p->link after free(p) accesses released memory and is undefined behavior. The routine touches each item once: O(n + e). All the C code in this chapter was run with a counting malloc/free wrapper; when the lists were released with this routine, the numbers of allocated and freed blocks were equal.
Not checking the result of malloc while building the list, and not freeing the lists at the end of the program. In a small test program these mistakes are invisible. In a long-running program that builds and tears down graphs again and again, the memory leak accumulates slowly, and eventually malloc really does return NULL.
15.3.4The inverse adjacency list
In a directed graph the adjacency list holds the outgoing edges. The inverse list holds the incoming edges: rev[j] is the list of vertices that send an edge to j. This is the adjacency list of the transpose graph, in which all the arrows are reversed. The inverse list is built by walking the existing lists once:
void transpose(node_ptr adj[], node_ptr rev[],
int n)
{
int i;
node_ptr p;
for (i = 0; i < n; i++) rev[i] = NULL;
for (i = 0; i < n; i++)
for (p = adj[i]; p; p = p->link)
insert(rev, p->vertex, i); /* <j,i> */
}The insert used by the routine is the form of add_edge that works on any array of heads:
void insert(node_ptr adj[], int u, int v) /* v into list adj[u] */
{
node_ptr p = malloc(sizeof(node));
if (p == NULL) exit(1);
p->vertex = v;
p->link = adj[u];
adj[u] = p;
}- Line 6. All heads of the inverse list are set to
NULL. - Lines 7–8. The list of each vertex i is walked from start to end. An item numbered j in the list means the edge <i, j>.
- Line 9. In the transpose graph this edge becomes <j, i>: i is added to the list
rev[j]. The comment<j,i>says exactly this.
| Line | i | p->vertex | Edge | Added |
|---|---|---|---|---|
| 6 | — | — | — | rev[0..2] = NULL |
| 8–9 | 0 | 1 | <0,1> | 0 to rev[1] |
| 8–9 | 1 | 0 | <1,0> | 1 to rev[0] |
| 8–9 | 1 | 2 | <1,2> | 1 to rev[2] |
| 7–8 | 2 | — | — | adj[2] empty, nothing to add |
| 7 | 3 | — | — | loop ends |
transpose (right). The 1 in rev[2] says that 2 is reached from 1.The outer loop runs n times; the inner loops look at each item once in total. Each insert call is O(1). The inverse list is therefore built in O(n + e). Once built, the in-degree is also found in O(d) by counting the items in rev[i]. The price is memory: every edge is stored twice, once in the out-list and once in the in-list.
15.3.5Sequential representation in an array
Each item of an adjacency list carries a pointer. On a 64-bit machine this pointer takes twice the space of the 4-byte neighbor number. If the graph will never change, it is possible to get rid of the pointers altogether: all the lists are written one after another into a single array.
The sequential representation of an undirected graph with n vertices and e edges is a single array int vertex[] of n + 2e + 1 entries. The first n + 1 cells hold starting indices. The neighbors of i are in the cells vertex[vertex[i]], …, vertex[vertex[i+1] − 1].
The array has two parts. The first n + 1 cells act like a table of contents: vertex[i] says where the neighbors of i begin in the array. The last 2e cells are the neighbor numbers themselves; the lists of the vertices are written in order, with no gaps between them. The neighbors of i end where the list of the next vertex begins. So that the last vertex also has an end boundary, one extra cell, vertex[n], is added. That is why the number of cells is n + 1 + 2e.
vertex[8] = 23 is the end boundary of the last vertex. The 14 cells with indices 9–22 hold the neighbor numbers.For G4, n = 8 and e = 7; the array has 8 + 14 + 1 = 23 cells. The neighbor entries start at index 9. The two neighbors of 0 are written into cells 9 and 10, the two neighbors of 1 into cells 11 and 12, and so on. Table 15.10 shows how to read the array, with examples.
| Vertex i | vertex[i] | vertex[i+1] | Indices read | Neighbors | Degree |
|---|---|---|---|---|---|
| 0 | 9 | 11 | 9, 10 | 1, 2 | 2 |
| 1 | 11 | 13 | 11, 12 | 0, 3 | 2 |
| 4 | 17 | 18 | 17 | 5 | 1 |
| 5 | 18 | 20 | 18, 19 | 4, 6 | 2 |
| 7 | 22 | 23 | 22 | 6 | 1 |
The routine that prints the neighbors of a vertex walks between the two bounds:
void print_adj(const int vertex[], int i)
{
int k;
for (k = vertex[i]; k < vertex[i + 1]; k++)
printf("%d ", vertex[k]);
printf("\n");
}The array is taken as const int vertex[]; the routine only reads it, and the compiler prevents accidental writes. The loop variable k starts at vertex[i] and stops before reaching vertex[i + 1]. Table 15.11 traces the call print_adj(vertex, 5).
| Line | k | Condition k < vertex[6] | vertex[k] | Output |
|---|---|---|---|---|
| 4–5 | 18 | 18 < 20 true | 4 | 4 |
| 4–5 | 19 | 19 < 20 true | 6 | 4 6 |
| 4, 6 | 20 | 20 < 20 false | — | 4 6 and a newline |
The loop runs as many times as the degree of the vertex: O(d). The degree itself is found without even a loop, as the difference vertex[i+1] − vertex[i], in O(1). Memory is n + 2e + 1 integers, with no pointers at all. For G4, 23 integers, that is 92 bytes, are enough. The adjacency list of the same graph needs 8 heads (64 bytes) and 14 items (224 bytes).
The array can be built from the existing lists in a single pass:
int build_sorted(int vertex[], int n) /* one array from the lists */
{
int i, k = n + 1; /* neighbors start at n+1 */
node_ptr p;
for (i = 0; i < n; i++) {
vertex[i] = k; /* where i's first neighbor is */
for (p = graph[i]; p; p = p->link)
vertex[k++] = p->vertex;
}
vertex[n] = k; /* end bound of the last vertex */
return k; /* cells used: n + 2e + 1 */
}For each vertex the routine first writes the starting index, then copies the neighbors in its list into the next free cells. When the loop ends, k equals the number of cells used, that is n + 2e + 1. Writing this value into vertex[n] sets the boundary of the last vertex. Applied to the sorted lists of G4, it produces exactly the array of Figure 15.13.
The price of this representation is change. Adding a new edge means opening one cell in each of two lists. This requires shifting all the cells behind and updating the starting indices of the shifted vertices: O(n + e). For a graph with many insertions and deletions this structure is not efficient. Storage is one matter; the efficiency of the algorithms that will work on the stored data is another. For example, the computer network in a building hardly ever changes. If the problem is only to hold this network and run queries on it, the sequential representation takes little space and is also read quickly because it is contiguous in memory. The compressed sparse row format (CSR) for sparse matrices is the same idea applied to a matrix.
15.3.6Orthogonal representation of directed graphs
If both out-degree and in-degree are asked for often in a directed graph, the adjacency list and its inverse must be kept together. Then each edge is stored with two items, 2e items in total. The orthogonal representation keeps each edge in a single item and links this item into two lists at the same time.
In the orthogonal list representation there is a single item for each edge <tail, head> of the directed graph. The item carries four fields: the tail, the head, a row link (the next edge leaving the same tail) and a column link (the next edge entering the same head). Each vertex has a row header (its out-list) and a column header (its in-list).
NULL links.The name of the representation comes from the look of the structure: the items are arranged in rows and columns like the filled cells of a matrix. Walking along the row of a vertex gives where one can go from that vertex, and walking along its column gives where one comes from into it. One item per edge is enough. In G3 the item <1,0> is in the row of 1 and in the column of 0.
This structure is very similar to the linked representation of sparse matrices. In a sparse matrix, too, each nonzero value is one item and is linked into its own row and column lists. As needed, the structure can be built with circular or doubly linked lists or with header nodes. Out-lists and in-lists are walked in O(d); insertion at the front is O(1).
The origin of this representation shows an instructive way of thinking. The solution that keeps the list together with its inverse is correct, but it uses 2e items. This waste is irritating and raises the question “can I do the same job in less space?” The first solution that comes to mind, and its first code, should never be trusted completely. Could the problem have been solved more efficiently if the underlying data structure were something else? Asking this question is the first step of good data structure design.
15.3.7The multilist
In the adjacency list of an undirected graph, too, each edge is stored with two items. If some information is to be attached to the edges (for example, a “this edge has been processed” mark), the two copies of this information must be kept consistent. The multilist removes this duplication.
In the adjacency multilist representation there is a single item for each edge (vi, vj) of an undirected graph. The item sits in the edge list of both vi and vj. The basic item is the edge, not the vertex.
typedef struct edge *edge_ptr;
typedef struct edge {
short marked; /* processed? */
int vertex1, vertex2; /* endpoints */
edge_ptr list1; /* next for vertex1 */
edge_ptr list2; /* next for vertex2 */
} edge;
edge_ptr graph[MAX_V];- Line 3.
markedrecords whether the edge has been processed. Because the edge appears in two lists, a traversal meets the same edge twice; the mark prevents the edge from being handled again at the second encounter. - Line 4.
vertex1andvertex2are the two endpoints of the edge. - Lines 5–6.
list1points to the next edge in the list ofvertex1;list2points to the next edge in the list ofvertex2. An item is in the chains of two separate lists at the same time. - Line 8.
graph[v]points to the first item in the edge list of v. The head of a vertex with no edges isNULL.
If data must be attached to vertices (for example a city name), a separate vertex array is added to the structure, or a field such as char label to the item. On x86-64 this edge structure is 32 bytes with padding. In an adjacency list the same edge takes 2 · 16 = 32 bytes with two items. The gain is not in memory but in the information living in a single place.
Table 15.12 gives the multilist of G1. The six edges are the items N0–N5.
| Item | vertex1 | vertex2 | list1 | list2 | In which lists |
|---|---|---|---|---|---|
| N0 | 0 | 1 | N1 | N3 | 0 and 1 |
| N1 | 0 | 2 | N2 | N3 | 0 and 2 |
| N2 | 0 | 3 | NULL | N4 | 0 and 3 |
| N3 | 1 | 2 | N4 | N5 | 1 and 2 |
| N4 | 1 | 3 | NULL | N5 | 1 and 3 |
| N5 | 2 | 3 | NULL | NULL | 2 and 3 |
To read the table, follow the list of a vertex. The list of 1 starts at graph[1] = N0. In N0, 1 is vertex2; the next edge is list2 = N3. In N3, 1 is vertex1; the next edge is list1 = N4. In N4, 1 is again vertex1, and the list ends with list1 = NULL. The edges of 1 are N0, N3, N4; its neighbors are 0, 2 and 3.
Traversing a multilist
The traversal rule is short: if v is in the item's vertex1 field, follow list1; if in vertex2, follow list2. When NULL is seen, the list ends.
void print_adj(int v)
{
edge_ptr p = graph[v];
while (p) {
if (p->vertex1 == v) { /* v: vertex1 */
printf("%d ", p->vertex2); p = p->list1;
} else { /* v: vertex2 */
printf("%d ", p->vertex1); p = p->list2;
}
}
}Two things are done at each item: the other endpoint is printed and the right link is chosen. Whichever endpoint v is, the other endpoint is the neighbor, and the link to follow is the one on v's side. Table 15.13 traces the call print_adj(2).
| Line | p | Item | which endpoint is 2 | Printed | Next p |
|---|---|---|---|---|---|
| 3 | N1 | (0,2) | — | — | — |
| 5, 8 | N1 | (0,2) | vertex2 | 0 | list2 = N3 |
| 5, 8 | N3 | (1,2) | vertex2 | 1 | list2 = N5 |
| 5–6 | N5 | (2,3) | vertex1 | 3 | list1 = NULL |
| 4 | NULL | — | — | loop ends; output 0 1 3 | |
vertex1, vertex2, list1, list2; the names beneath them are the items the links point to. In the trace, p has reached N3, the second edge of 2.The loop runs once for each edge of v: O(dv). Each edge is stored in memory only once, but it can be reached from the lists of both its endpoints.
Adding an edge to a multilist
A new edge enters two lists at once. Appending to the ends of the lists is possible, but it requires walking to NULL in both lists. Inserting at the front removes this cost:
void ml_add_edge(int u, int v)
{
edge_ptr p = malloc(sizeof(edge));
if (p == NULL) exit(1);
p->marked = 0;
p->vertex1 = u; p->vertex2 = v;
p->list1 = graph[u]; /* into u's list */
p->list2 = graph[v]; /* into v's list */
graph[u] = graph[v] = p; /* at the front of both */
}- Lines 3–4. Memory is allocated for the item and checked.
- Lines 5–6. The edge has not been processed yet; the endpoints are written.
- Line 7.
list1points to the old first edge of u. It does not matter which endpoint of that old edge u is; the traversal routine determines this itself at every item. - Line 8.
list2points to the old first edge of v. - Line 9. Both heads point to the new item. Lines 7 and 8 must be executed before this assignment; otherwise the old lists are lost.
Insertion is O(1). For an undirected graph a single array of heads is enough. For a directed graph one keeps, as in the orthogonal representation, a head array together with a tail array. If the edges of G1 are added with ml_add_edge in the order (0,1), (0,2), …, (2,3), the lists come out in the reverse of the arrival order, and this time print_adj(2) prints 3 1 0. Table 15.12, on the other hand, shows a layout in which edges are appended at the ends of the lists; in that layout the output is 0 1 3. Both structures are correct, but which code produces which drawing must be consistent. If the edges arrive in this order and each must be placed in O(1), they are inserted at the head of the list. Drawing the list as if it were appended at the end would then contradict what the code does.
15.3.8Application: four representations of the same graph
For the directed graph with four vertices and edges <0,1>, <0,3>, <1,2>, <2,0>, <3,2>, build the adjacency matrix, the adjacency list, the inverse list and the orthogonal (single-item) list.
Matrix. Write a[i][j] = 1 if <i, j> exists; the row shows the tail and the column the head (Table 15.14). The row sums give the out-degrees (2, 1, 1, 1) and the column sums the in-degrees (1, 1, 2, 1). Each of the two sums is 5; in a directed graph every edge contributes to one out-degree and one in-degree.
| 0 | 1 | 2 | 3 | out | |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 1 | 2 |
| 1 | 0 | 0 | 1 | 0 | 1 |
| 2 | 1 | 0 | 0 | 0 | 1 |
| 3 | 0 | 0 | 1 | 0 | 1 |
| in | 1 | 1 | 2 | 1 | 5 |
List and its inverse. Out-lists: 0 → 1, 3; 1 → 2; 2 → 0; 3 → 2. In-lists (transpose): 0 ← 2; 1 ← 0; 2 ← 1, 3; 3 ← 0. Each has 2e = 10 items in total.
Single-item representation. Each edge is a single item: N1 = <0,1>, N2 = <0,3>, N3 = <1,2>, N4 = <2,0>, N5 = <3,2>. Each item is in the out-list of its tail and the in-list of its head. The tail link points to the next edge leaving the same tail; the head link to the next edge entering the same head. Only e = 5 items are needed.
| Item | tail | head | tail link | head link | Vertex | out | in | |
|---|---|---|---|---|---|---|---|---|
| N1 | 0 | 1 | N2 | NULL | 0 | N1 | N4 | |
| N2 | 0 | 3 | NULL | NULL | 1 | N3 | N1 | |
| N3 | 1 | 2 | NULL | N5 | 2 | N4 | N3 | |
| N4 | 2 | 0 | NULL | NULL | 3 | N5 | N2 | |
| N5 | 3 | 2 | NULL | NULL |
As a check, follow the in-list of 2: the header is N3 (<1,2>), the head link of N3 is N5 (<3,2>), and the head link of N5 is NULL. 2 is entered from 1 and from 3; the in-degree is 2, which agrees with column 2 of the matrix. The out-list of 0 starts at N1, moves to N2 through the tail link and ends: from 0 one can go to 1 and to 3.
15.3.9Comparing the representations
Table 15.16 puts the five representations side by side under the same criteria. du is the degree of u.
| Representation | Memory | Is (u, v) present? | Neighbors of u | Insert / delete |
|---|---|---|---|---|
| Adjacency matrix | O(n²) | O(1) | O(n) | O(1) |
| Adjacency list | O(n + 2e) | O(du) | O(du) | O(1) at the front; O(d) search to delete |
| Sequential array | n + 2e + 1 integers | O(du) | O(du) | expensive: shifting O(n + e) |
| Orthogonal list (directed) | O(n + e) | O(d) | in and out O(d) | O(1) at the front |
| Multilist | O(n + e) | O(du) | O(du) | O(1) at the front |
No row of the table is best in every column. The matrix is unrivaled for edge queries but slow at scanning neighbors and in memory. Lists are fast for traversal but slow for edge queries. The sequential array takes the least space but cannot cope with change. The choice depends on which operation will be performed how many times in the problem.
The lesson of this section is a method: first think about how the data will be stored, then write the code. The first solution that comes to mind may not be a good method. If the data structure is well designed, even an algorithm with n³ steps can sometimes drop to n steps. The first example of this appears right below: the same traversal algorithm takes O(n²) with a matrix and O(n + e) with a list. Storing data is not as easy a job as it looks.
15.3.10Weighted graphs
In many problems it is not enough for an edge merely to exist; it also has a value. In a road network this value is distance, in a computer network latency, in a project plan duration, in cable laying cost. A graph whose edges have been assigned numbers is a weighted graph, and these numbers are called weights.
Both basic representations extend easily. In the matrix, the weight of the edge is written instead of 1; such a matrix is called a cost matrix. If there is no edge, a value meaning “infinity” is written into the cell. The diagonal is 0: going from a vertex to itself costs nothing. In the list, a weight field is added to each item.
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 4 | 2 | ∞ |
| B | 4 | 0 | 1 | 5 |
| C | 2 | 1 | 0 | 8 |
| D | ∞ | 5 | 8 | 0 |
#define INF 1000000 /* not INT_MAX: sums overflow */
int cost[MAX_V][MAX_V];
typedef struct wnode *wnode_ptr;
typedef struct wnode {
int vertex;
int weight; /* cost of the edge */
wnode_ptr link;
} wnode;
wnode_ptr wgraph[MAX_V];C has no integer called infinity; a large constant is chosen. The first thing that comes to mind is INT_MAX, but this is a dangerous choice. Shortest path algorithms constantly compute sums of the form d + w. If any positive w is added while d = INT_MAX, the signed integer overflows. Signed overflow is undefined behavior in C; in practice the result is usually a large negative number, and the algorithm takes the vertex “at infinite distance” for the nearest one. That is why INF is chosen with care. It is larger than all real weights, but even twice its value fits in an int. 2 · 1,000,000 is far below the limit of a 32-bit int (about 2.1 billion).
The list item wnode is node with an added int weight; on x86-64 two ints take 8 bytes and the pointer 8 bytes, with no padding needed: 16 bytes. All minimum spanning tree and shortest path algorithms use one of these two representations.
15.4Traversals
The most basic operation on a graph is traversal. Let an undirected graph G = (V, E) and a vertex v be given. We want to visit every vertex reachable from v exactly once. “Visiting” a vertex means doing the work associated with it; in this chapter it means printing the vertex's number. Many algorithms, such as finding components, looking for cycles, shortest paths and spanning trees, are built on top of a traversal.
Traversal is easy in trees, because a tree has no cycles and every vertex is reached from the root by a single path. In a graph, a vertex can be reached by many paths. So the first rule of graph traversal is this: a visited vertex is marked, and a marked vertex is never entered again. Without the marks, the traversal would go around a cycle forever.
There are two basic traversal methods:
- Depth-first search (DFS). Go to a neighbor and from there dive as deep as possible. It resembles preorder traversal in a tree.
- Breadth-first search (BFS). First visit all neighbors of the start, then their neighbors. It resembles level-order traversal in a tree.
In both methods the graph is implemented with adjacency lists, and the lists are sorted. An example graph with eight vertices is used (Figure 15.19).
15.4.1Depth-first search
The idea of DFS resembles paying out a thread while moving through a maze. v is visited. Then an unvisited w is chosen from the list of v, and the search continues through w. If w also has an unvisited neighbor, the search moves on to it. When the search arrives at a vertex u with no unvisited neighbor left, it steps back and continues in the list of the vertex from which u was reached, from the place where it left off.
For these returns, one has to remember where each vertex's list was left off. Because the last one in is the first one out, this information is kept on a stack: while going deeper, vertices are pushed onto the stack, and when there is nowhere left to go, one is popped and the search continues. DFS written with an explicit stack looks complicated. The recursive routine does the same job very briefly, because the compiler's call stack holds the stack. The local variable w of each call stores where the list of that vertex was left off.
First, the common declarations:
#include <stdio.h>
#include <stdbool.h>
#define TRUE true
#define FALSE false
bool visited[MAX_V]; /* don't forget ';' */stdbool.h has provided the type bool and the values true/false since C99. The macros TRUE and FALSE are there to keep the notation of the textbook. visited is a global array; all its elements are false when the program starts. If the traversal is to be restarted, the array must be cleared by hand.
void dfs(int v) /* depth-first search */
{
node_ptr w;
visited[v] = TRUE; /* visited */
printf("%d ", v);
for (w = graph[v]; w; w = w->link)
if (!visited[w->vertex])
dfs(w->vertex);
}- Line 3.
wis the pointer that moves along the list of v. Each recursive call has its ownw. - Line 4. v is marked. The mark is set before the vertex's list is scanned. That way, when v is seen in the list of one of its neighbors, it is not entered again.
- Line 5. Visit: the vertex number is printed.
- Line 6. The list of v is walked from start to end. The condition
win theforheader meansw != NULL. - Lines 7–8. If the neighbor is not marked, the search continues through it. When the recursive call returns, the loop continues from the place that the
wof this call points to, that is, from where it left off.
15.4.2Tracing DFS
The call dfs(0) is traced on the example graph. In Table 15.18 the call stack is written from dfs(0) at the bottom up to the active call at the top. In the rows marked “skipped”, the neighbor is already marked.
| Step | Event | Call stack | Output |
|---|---|---|---|
| 1 | dfs(0): 0 is marked and printed | 0 | 0 |
| 2 | 0 → 1 unmarked: dfs(1) | 0 1 | 0 1 |
| 3 | w → 0 in the list of 1: marked, skipped | 0 1 | 0 1 |
| 4 | 1 → 3 unmarked: dfs(3) | 0 1 3 | 0 1 3 |
| 5 | w → 1 in the list of 3: skipped | 0 1 3 | 0 1 3 |
| 6 | 3 → 7 unmarked: dfs(7) | 0 1 3 7 | 0 1 3 7 |
| 7 | w → 3 in the list of 7: skipped | 0 1 3 7 | 0 1 3 7 |
| 8 | 7 → 4 unmarked: dfs(4) | 0 1 3 7 4 | 0 1 3 7 4 |
| 9–10 | list of 4: 1 and 7 are marked; dfs(4) ends | 0 1 3 7 | 0 1 3 7 4 |
| 11 | 7 → 5 unmarked: dfs(5) | 0 1 3 7 5 | 0 1 3 7 4 5 |
| 12 | 5 → 2 unmarked: dfs(2) | 0 1 3 7 5 2 | 0 1 3 7 4 5 2 |
| 13–14 | 0 and 5 in the list of 2: skipped | 0 1 3 7 5 2 | 0 1 3 7 4 5 2 |
| 15 | 2 → 6 unmarked: dfs(6) | 0 1 3 7 5 2 6 | 0 1 3 7 4 5 2 6 |
| 16–17 | list of 6: 2 and 7 are marked; dfs(6) and dfs(2) end | 0 1 3 7 5 | same |
| 18 | resuming in 5: w → 7 skipped; dfs(5) ends | 0 1 3 7 | same |
| 19 | resuming in 7: w → 6 skipped; dfs(7) and dfs(3) end | 0 1 | same |
| 20 | resuming in 1: w → 4 skipped; dfs(1) ends | 0 | same |
| 21 | resuming in 0: w → 2 skipped; dfs(0) ends | — | 0 1 3 7 4 5 2 6 |
The most important moments of the trace are the returns. In step 12 the search moves from 5 to 2. There is a direct edge between 0 and 2. Still, 2 was reached by the long path 0 → 1 → 3 → 7 → 5 → 2. DFS tries depth first, not nearness. In step 18, dfs(5) resumes from the place where it was before descending to 2, with the second item in its list, 7. What makes this possible is the w kept in the frame of dfs(5). The deepest moment of the stack is step 15: seven calls are open at the same time.
dfs(2) has just been called; the thick red edges are the tree edges followed so far, and on the right the visited array and the list of 2 are shown. Bottom: the traversal is finished; the tree edges form the depth-first spanning tree.The edges through which a vertex is entered for the first time during the traversal form a tree: 0–1, 1–3, 3–7, 7–4, 7–5, 5–2, 2–6. The seven edges connect all eight vertices without a cycle. This tree is called the depth-first spanning tree. If one of the unused edges, for example 0–2, is added to the tree, a cycle forms and the structure stops being a tree.
15.4.3What the result of DFS depends on
Besides the graph itself, the order that DFS produces depends on two things.
The start vertex. The start does not have to be 0. On the same graph with the same lists, dfs(6) prints 6 2 0 1 3 7 4 5 and dfs(4) prints 4 1 0 2 5 7 3 6. The visited vertices are the same, but their order differs. In a connected graph every start reaches all the vertices.
The order of the lists. If the list of 0 were {2, 1} instead of {1, 2}, dfs(0) would descend to 2 first and the order would be 0 2 5 7 3 1 4 6. Whether the list was built by inserting at the front or at the end, or kept sorted, directly changes the traversal. For this reason a DFS output can be stated exactly only when the exact order of the lists is known.
On a graph with n vertices and e edges implemented with adjacency lists, the total running time of dfs is O(n + e). If it is implemented with an adjacency matrix, it is O(n²).
dfs(v) is called only while visited[v] is false, and its first action is to make this value true. So at most one call is made per vertex; the total number of calls is at most n. Each call scans the list of its own vertex once; the list of v has dv items. By Theorem 15.1, the total length of all the lists is 2e. The total work is O(n + 2e) = O(n + e). In a matrix, finding the neighbors of a vertex requires reading the whole row, that is n cells; each of the n calls takes O(n), and the total is O(n²). ∎
On the example graph, an instrumented dfs made 8 calls and looked at exactly 20 items in the lists; these values agree with n = 8 and 2e = 20. The number of edges can be at most n(n − 1)/2. In a complete graph e reaches the order of n², and the costs of the two representations become equal. In sparse graphs, however, the list does the traversal in linear time.
The extra memory must also be counted. The visited array has n entries. The depth of the call stack is n in the worst case: in a graph whose vertices are laid out like a chain, each call opens the next. In very large graphs this depth can overflow the call stack; in that case DFS is written with an explicit stack.
15.4.4Breadth-first search
BFS spreads like the rings made by a stone thrown into water. It starts from v and marks v. Then all the vertices in the list of v are visited. Next the unvisited neighbors of the first vertex in the list of v are visited, then those of the second, and so on. Every visited vertex is put into a queue. When the list of a vertex is finished, the vertex at the front of the queue is taken and its list is processed. When the queue becomes empty, the search ends.
By the nature of the method a queue is required, just as a stack is required in DFS. The neighbors of the vertex visited first must be visited first; “first in, first out” is exactly this rule.
void bfs(int v) /* breadth-first search */
{
node_ptr w;
queue_ptr front = NULL, rear = NULL;
printf("%d ", v);
visited[v] = TRUE;
addq(&front, &rear, v);
while (front) {
v = deleteq(&front, &rear);
for (w = graph[v]; w; w = w->link)
if (!visited[w->vertex]) {
printf("%d ", w->vertex);
addq(&front, &rear, w->vertex);
visited[w->vertex] = TRUE;
}
}
}- Line 4. The queue is implemented with a linked list;
frontandrearare initiallyNULL, that is, the queue is empty. - Lines 5–7. The start vertex is printed, marked and put into the queue.
- Line 8. The loop runs while the queue is not empty. In an empty queue
frontisNULL. - Line 9. The vertex at the front of the queue is taken. The parameter
vis reused here; its value at the start of the routine is no longer needed. - Lines 10–15. The list of
vis scanned. Every unmarked neighbor is printed, appended to the rear of the queue and marked.
The timing of the mark is important: a vertex is marked when it is added to the queue, not when it leaves the queue. That way, even if a vertex is seen again in the list of another vertex while it waits in the queue, it does not enter the queue a second time. The value of this detail becomes clear when one looks at the result of the faulty form.
The dynamic queue
The queue that BFS uses is a dynamic queue implemented with a linked list. Items are taken from the front and added at the rear; two pointers are kept for the two ends.
typedef struct queue *queue_ptr;
typedef struct queue {
int vertex;
queue_ptr link;
} queue;
void addq(queue_ptr *front,
queue_ptr *rear, int d)
{
queue_ptr p = malloc(sizeof(queue));
if (p == NULL) exit(1);
p->vertex = d; p->link = NULL;
if (*front) (*rear)->link = p; else *front = p;
*rear = p;
}addq takes the addresses of both pointers so that it can change them (queue_ptr *front). This is the only way in C to change a pointer from inside a function. The link of the new item is NULL, because it goes to the end of the queue. If the queue is not empty, the link of the old last item points to the new item; if it is empty, the new item is also the front item. In both cases the rear points to the new item. The operation is O(1).
int deleteq(queue_ptr *front,
queue_ptr *rear)
{
queue_ptr p = *front; /* front != NULL */
int d = p->vertex;
*front = p->link;
if (*front == NULL) *rear = NULL;
free(p);
return d;
}deleteq expects a nonempty queue; the comment states this precondition, and the BFS routine guarantees it with while (front). The value of the front item is saved, the front pointer moves to the next one and the item is freed. When the queue becomes empty, the rear must also be set to NULL. If it is not, rear keeps pointing at the item that was just freed. The next addq sees *front as empty and behaves correctly, but in the meantime rear is a dangling pointer. That is why a prototype taking only the front pointer, such as int deleteq(queue_ptr *), is not enough; the address of rear is passed as well. The operation is O(1).
15.4.5Tracing BFS
Table 15.19 traces the call bfs(0) on the example graph. In the queue column the left end is the front and the right end the rear.
| Step | v | Event | Queue (front … rear) | Output |
|---|---|---|---|---|
| 1 | 0 | 0 is printed, marked and enqueued | 0 | 0 |
| 2 | 0 | 0 is taken; its list is {1, 2} | — | 0 |
| 3–4 | 0 | 1 and 2 unmarked: printed, added, marked | 1 2 | 0 1 2 |
| 5 | 1 | 1 is taken; its list is {0, 3, 4}; 0 is marked | 2 | 0 1 2 |
| 6–7 | 1 | 3 and 4 are added | 2 3 4 | 0 1 2 3 4 |
| 8 | 2 | 2 is taken; its list is {0, 5, 6}; 0 is marked | 3 4 | 0 1 2 3 4 |
| 9–10 | 2 | 5 and 6 are added | 3 4 5 6 | 0 1 2 3 4 5 6 |
| 11 | 3 | 3 is taken; its list is {1, 7}; 1 is marked | 4 5 6 | 0 1 2 3 4 5 6 |
| 12 | 3 | 7 is added | 4 5 6 7 | 0 1 2 3 4 5 6 7 |
| 13 | 4 | 4 is taken; its list is {1, 7}: both are marked | 5 6 7 | same |
| 14 | 5 | 5 is taken; its list is {2, 7}: marked | 6 7 | same |
| 15 | 6 | 6 is taken; its list is {2, 7}: marked | 7 | same |
| 16 | 7 | 7 is taken; its list is {3, 4, 5, 6}: marked | — | same |
| 17 | — | queue empty: the search ends | — | 0 1 2 3 4 5 6 7 |
In step 12, 7 enters the queue and is marked. In step 13, 7 is seen again in the list of 4, but because it is marked it is not added a second time. The same happens in the lists of 5 and 6. 7 can be reached from four different vertices, but it enters the queue once.
The output is 0 1 2 3 4 5 6 7: the vertices are visited level by level, according to their number of edges from the start. 0 is at level 0; 1 and 2 at level 1; 3, 4, 5, 6 at level 2; 7 at level 3. The tree edges are 0–1, 0–2, 1–3, 1–4, 2–5, 2–6 and 3–7. In this breadth-first spanning tree the path from the root to each vertex is a path with the fewest edges in the graph.
Marking a vertex in BFS when it is taken out of the queue instead of when it is added. On the example graph, delete the line visited[w->vertex] = TRUE. In its place, write visited[v] = TRUE after v = deleteq(…). The output is then 0 1 2 3 4 5 6 7 7 7 7. Before it leaves the queue, 7 is seen once in each of the lists of 3, 4, 5 and 6, and it enters the queue four times. 11 insertions are made into the queue instead of 8, and 32 items are scanned in the lists instead of 20. Each duplicate scans its own list again when it leaves the queue. In denser graphs the work clearly exceeds the O(n + e) bound.
15.4.6Analysis of BFS and comparison with DFS
On a graph implemented with adjacency lists, bfs runs in O(n + e) time; with an adjacency matrix, in O(n²).
A vertex is added to the queue only while it is unmarked and is marked at the moment it is added. So each vertex enters the queue at most once, and the while loop runs at most n times. In each round the list of the vertex taken from the queue is scanned once. The total number of items scanned over all rounds is d0 + … + dn−1 = 2e. addq and deleteq are O(1). The total is O(n + e). In a matrix each round reads the n cells of a row; over n rounds that comes to O(n²). ∎
The extra memory of BFS is the visited array and the queue; at most n vertices are in the queue at once. The order that BFS produces is the order of the number of edges from the start. In an unweighted graph this means the order of the shortest paths; that is why BFS is the algorithm that finds paths with the fewest edges.
Depth-first and breadth-first search are two general search strategies that appear outside data structures too. In artificial intelligence, all the states of a problem form a search space, and this space is traversed as if it were a tree. Minimax search, B* search and branch and bound are built on these traversals. In a game problem, if one says “the possible moves are these” and expands every move one by one, the search is proceeding breadth-first.
| Property | DFS | BFS |
|---|---|---|
| Auxiliary structure | Stack (the call stack in recursion) | Queue |
| Progress | As deep as possible along one path | Layer by layer, from near to far |
| Counterpart in a tree | Preorder traversal | Level-order traversal |
(0) on the example graph | 0 1 3 7 4 5 2 6 | 0 1 2 3 4 5 6 7 |
(7) on the example graph | 7 3 1 0 2 5 6 4 | 7 3 4 5 6 1 2 0 |
| Cost (list / matrix) | O(n + e) / O(n²) | O(n + e) / O(n²) |
| Typical use | Components, cycle detection, topological sorting | Fewest-edge path, bipartiteness test |
15.5Components, cycles and bipartiteness
The traversal routines alone only print vertex numbers. Their real value lies in the algorithms built on top of them. This section uses DFS and BFS to answer three questions: How many pieces does the graph consist of? Is there a cycle in the graph? Can the vertices of the graph be split into two groups so that every edge goes between the groups?
15.5.1Connected components
A connected component of an undirected graph is one of the maximal connected subgraphs of the graph. “Maximal” means that if any other vertex of the graph is added to the component, the subgraph is no longer connected.
Every vertex belongs to exactly one component; the components partition the vertex set into disjoint parts. G4 has two components and G5 has nine. A connected graph has a single component, namely itself.
To find components, we use a property of traversal: dfs(v) marks all the vertices reachable from v, that is, the whole component of v. If an unmarked vertex remains when the traversal ends, it is in another component, and a new traversal is started from there.
void connected(int n)
{
int i;
for (i = 0; i < n; i++)
if (!visited[i]) { /* new */
dfs(i);
printf("\n");
}
}- Line 4. All vertices are tried in turn.
- Line 5. An unmarked vertex is the first vertex of a new component that no earlier traversal could reach.
- Line 6.
dfs(i)prints and marks all the vertices of this component. - Line 7. Each component is printed on a separate line. If a counter increment (
count++) is added at this line, the routine also gives the number of components; if the number is 1, the graph is connected.
The routine can be written in the same way with BFS instead of DFS. For the routine to work, the visited array must be entirely FALSE at the start.
0 1 3 2 / 4 5 6 / 7 8 9. Bottom: a graph with 11 vertices and four components; the output is 0 / 1 2 4 3 / 5 6 7 8 / 9 10.In the bottom example the output of the second line is 1 2 4 3. Since the list of 1 is {2, 3}, DFS goes first to 2, then to 4 in the list of 2, and from there to 3. 5 does not appear in this line; 5, 6, 7, 8 form another component. The component consisting of 0 alone has a single vertex; dfs(0) prints only 0, because its list is empty. Table 15.21 is the trace of the top example.
i | visited[i] | Event | Line printed | Component |
|---|---|---|---|---|
| 0 | F | new component: dfs(0) | 0 1 3 2 | 1 |
| 1, 2, 3 | T | the if is not entered, O(1) each | — | 1 |
| 4 | F | new component: dfs(4) | 4 5 6 | 2 |
| 5, 6 | T | the if is not entered | — | 2 |
| 7 | F | new component: dfs(7) | 7 8 9 | 3 |
| 8, 9 | T | the if is not entered | — | 3 |
| 10 | — | loop ends | 3 components | |
i = 4. The four vertices of the first component are marked (T); dfs(4) has traversed the second component.15.5.2Analysis: a sum, not a product
The cost of the routine is misleading at first sight. The outer for runs n times. The inner call dfs costs O(n + e). Can these two numbers be multiplied and the complexity stated as O(n(n + e))? No. The rule “find the loops and multiply their costs” gives a wrong result here, because the cost of the inner work is not the same in every round.
connected runs in O(n + e) time with adjacency lists and in O(n²) time with an adjacency matrix.
All the dfs calls share the same visited array. Once a vertex is marked, no call enters it again. Hence all the dfs calls made during the for loop together visit each vertex once and scan each list once: O(n + e) in total. Part of this total falls on the first component and part on the second; since the components are disjoint, no work is counted twice. To this are added the for loop's own n rounds; for marked vertices a round is O(1). The total is O(n) + O(n + e) = O(n + e). In a matrix every visit requires a row scan, so the total of the visits is O(n²). ∎
The extreme case shows this clearly. If the graph is connected, in the first round dfs(0) traverses the whole graph in O(n + e) and the whole visited array becomes TRUE. For the remaining n − 1 values of i, the if is never entered. The product would be right only if dfs traversed the whole graph again in every round; the marks prevent this. The same kind of reasoning applies to many algorithms in which loops are nested but the total work of the inner loop is bounded.
15.5.3Connectivity and the number of edges
How many edges does a graph need in order to be connected?
A connected graph with n vertices has at least n − 1 edges. In a simple graph the number of edges is at most n(n − 1)/2. So in a connected simple graph
n − 1 ≤ e ≤ n(n − 1)/2
holds.
For the lower bound, imagine starting from a graph with no edges and adding edges one at a time. At first every vertex is a component by itself; there are n components. When an edge is added, its two endpoints are either in the same component, and the number of components does not change, or in different components, and the two components merge. An edge reduces the number of components by at most 1. To go from n components down to one, at least n − 1 edges are needed. For the upper bound we use the fact that in a simple graph there is at most one edge between each pair of vertices. Vertex 0 can be connected to the other n − 1 vertices. Vertex 1 can be connected to the n − 2 vertices after it. Continuing in this way gives (n − 1) + (n − 2) + … + 1 = n(n − 1)/2. ∎
The theorem goes only one way. n − 1 edges are necessary for connectivity but not sufficient. In a graph with 5 vertices, 4 edges can form a chain; then the graph is connected. The same 4 edges can form a cycle among four vertices; then the fifth vertex is left alone and the graph is not connected. If the number of edges is less than n − 1, the graph is certainly not connected; in G5, e = 2 < 10.
The upper bound matters for complexity expressions. e can be a number of order n². So O(n + e) equals O(n²) in a complete graph; a list beats a matrix asymptotically only in sparse graphs. A connected graph with exactly n − 1 edges contains no cycle; such a graph is a tree. The spanning trees produced by traversals also have n − 1 edges.
Game problems show the practical importance of these bounds. In a game such as tic-tac-toe, each state is a vertex and each move is an edge. The question “how do I counter my opponent's move?” amounts to a search in this graph. The number of states grows quickly, and the cost of the search depends directly on the numbers of vertices and edges.
15.5.4Cycle detection in an undirected graph
A by-product of DFS is whether the graph has a cycle. While scanning the list of a vertex, DFS may meet a marked neighbor. In an undirected graph there can be two reasons. First, the neighbor was the vertex we just came from in the previous step; this is the other endpoint of the edge we arrived by and is not a sign of a cycle. Second, the neighbor was marked earlier through another path. In that case one can get from the vertex to that neighbor both along tree edges and along this edge: there is a cycle. Such edges are called back edges.
bool has_cycle(int v, int parent)
{
node_ptr w;
visited[v] = TRUE;
for (w = graph[v]; w; w = w->link)
if (!visited[w->vertex]) {
if (has_cycle(w->vertex, v)) return TRUE;
} else if (w->vertex != parent)
return TRUE; /* back edge */
return FALSE;
}- Line 1. Besides the vertex, the routine takes
parent, that is, the vertex from which this vertex was reached. In the first call there is no parent;-1is used in this sense because it is not the number of any vertex. - Line 4. The vertex is marked.
- Lines 6–7. The search descends into an unmarked neighbor; its parent is the current vertex. If the recursive call finds a cycle,
TRUEis carried up immediately along the chain of calls. - Lines 8–9. If the neighbor is marked and is not the parent, a back edge has been found. The
else ifbelongs to the outerif, not to the inner one; the braces make this explicit. If the braces are removed, theelseattaches to the nearestifand the meaning of the routine changes. - Line 10. All neighbors have been passed and no cycle was found.
In the graph with four vertices and edges 0–1, 1–2, 2–3 and 3–1, the sorted lists are 0: {1}, 1: {0, 2, 3}, 2: {1, 3}, 3: {1, 2}. Table 15.22 traces the call has_cycle(0, -1).
| Call | w | State | Result |
|---|---|---|---|
has_cycle(0, -1) | 1 | unmarked: enter | — |
has_cycle(1, 0) | 0 | marked, but it is the parent | not counted as a cycle |
has_cycle(1, 0) | 2 | unmarked: enter | — |
has_cycle(2, 1) | 1 | marked, but it is the parent | not counted as a cycle |
has_cycle(2, 1) | 3 | unmarked: enter | — |
has_cycle(3, 2) | 1 | marked and not the parent (2) | back edge (3,1): TRUE |
The value TRUE is carried from 3 to 2, from 2 to 1, from 1 to 0, and the routine ends early. If there is no cycle, the routine takes as long as DFS itself, O(n + e). If the graph has several components, the routine is restarted from every unmarked vertex, as in finding components. On G2, which is known to be a tree, the routine returns FALSE.
15.5.5Cycles in a directed graph
In a directed graph the parent check is not enough. An edge to a previously marked vertex need not close a cycle: that vertex may already have been finished in another branch. For example, with the edges 0 → 1, 0 → 2, 1 → 3, 2 → 3, DFS descends through 0, 1, 3, and then sees the edge from 2 to 3. 3 is marked, but there is no cycle. The distinguishing question is this: is the marked vertex on the stack right now? An edge to a vertex on the stack closes the path from that vertex down to the current vertex, and that is a cycle.
This distinction is made with three colors: white for a vertex not yet entered, gray for one that has been entered but not finished (it is on the stack), and black for one that is finished.
enum { WHITE, GRAY, BLACK };
int state[MAX_V]; /* all WHITE at the start */
bool directed_cycle(int v)
{
node_ptr w;
state[v] = GRAY; /* entered the stack */
for (w = graph[v]; w; w = w->link) {
if (state[w->vertex] == GRAY)
return TRUE; /* edge to a vertex on the stack */
if (state[w->vertex] == WHITE && directed_cycle(w->vertex))
return TRUE;
}
state[v] = BLACK; /* finished */
return FALSE;
}When a vertex is entered it is made gray. If a gray neighbor is seen, there is a cycle. A white neighbor is descended into. When all neighbors are done, the vertex becomes black and is no longer seen as part of any cycle. The routine returned TRUE on G3 (0 → 1 → 0) and on the application graph (0 → 1 → 2 → 0), and FALSE on the four-vertex example above. The cost is again O(n + e); with a matrix the same DFS is O(n²). The topological sorting routine also catches a cycle automatically.
The practical importance of cycle detection is great. In a project where precedence relations are defined between tasks, a directed cycle means a contradiction such as “A must finish before B, and B before A”, and the project never ends. When building a minimum spanning tree, an edge that closes a cycle is a redundant edge and is not taken into the tree.
15.5.6Testing for bipartiteness
A graph is bipartite if its vertex set V can be split into two disjoint sets A and B such that every edge has one endpoint in A and the other in B.
Students and courses form a bipartite graph: edges connect only a student to a course. K3,3 is a bipartite graph in which each vertex of a group of three is connected to every vertex of the other group of three.
The test is a coloring problem. The start vertex is painted color 0. BFS paints each unmarked neighbor with the opposite color of its own. If the two endpoints of an edge turn out to have the same color, the graph is not bipartite. If no conflict arises, the colors give the two groups.
int color[MAX_V]; /* -1: not colored, 0 or 1 */
bool is_bipartite(int n)
{
int i, v;
node_ptr w;
queue_ptr front = NULL, rear = NULL;
for (i = 0; i < n; i++) color[i] = -1;
for (i = 0; i < n; i++) {
if (color[i] != -1) continue; /* new component */
color[i] = 0;
addq(&front, &rear, i);
while (front) {
v = deleteq(&front, &rear);
for (w = graph[v]; w; w = w->link)
if (color[w->vertex] == -1) {
color[w->vertex] = 1 - color[v];
addq(&front, &rear, w->vertex);
} else if (color[w->vertex] == color[v]) {
while (front) deleteq(&front, &rear); /* empty the queue */
return FALSE;
}
}
}
return TRUE;
}- Line 1. The
colorarray holds both the mark and the color:-1is a vertex not yet colored. A separatevisitedarray is not needed. - Lines 8–12. All colors are cleared; BFS is started separately for each component; the color of one component does not affect another.
- Lines 16–18. An uncolored neighbor is painted the opposite color and enters the queue.
- Lines 19–21. If the neighbor is colored and has the same color, the test fails. Before leaving the routine the queue is emptied; otherwise the items left in the queue are never freed.
In the 6-cycle, BFS colors the vertices in the order 0, 1, 5, 2, 4, 3; the colors are 0, 1, 1, 0, 0, 1. No edge has both endpoints in the same color. In the triangle, 0 gets color 0, and its neighbors 1 and 2 get color 1. When the list of 1 is scanned, 2 is seen; both have color 1, and the test fails.
A graph is bipartite if and only if it contains no cycle of odd length.
One direction is easy. If the graph is bipartite, every edge changes color. A cycle returns to the vertex it started from, that is, to the color it started with; so the number of color changes on the cycle, which is its number of edges, is even. There can be no odd cycle. The other direction follows from the BFS coloring producing a conflict. If two neighbors u and v of the same color are found, they have a common ancestor in the BFS tree. Since they have the same color, the difference of their distances from the start is even; since the levels of adjacent vertices in BFS can differ by at most 1, their levels are equal. The two paths descending from the common ancestor to u and to v have equal length; adding the edge (u, v) to them gives a cycle of odd length. So if there is no odd cycle, the coloring finishes without conflict. ∎
The cost of the test is the cost of BFS: O(n + e). The routine returned TRUE for the 6-cycle and for K3,3, and FALSE for the triangle; the example traversal graph is bipartite too, because all of its cycles have 4 or 6 edges.
15.6Complexity summary
Table 15.23 gives the costs of the operations studied in this chapter for the two basic representations. n is the number of vertices, e the number of edges and d the degree of the vertex in question. In a connected simple graph, n − 1 ≤ e ≤ n(n − 1)/2.
| Operation | Matrix | List | Reason |
|---|---|---|---|
| Memory | O(n²) | O(n + e) | 2e items in an undirected list |
| Is (u, v) present? | O(1) | O(du) | A single cell / a list scan |
| Degree (undirected) | O(n) | O(d) | Row / list length; for in-degree in a directed graph, the inverse list |
| Number of edges | O(n²) | O(n + e) | Sum of degrees / 2 |
| DFS, BFS | O(n²) | O(n + e) | Each vertex once, each list once |
| Connected components | O(n²) | O(n + e) | Sum of the traversals; not a product |
| Cycles, bipartiteness | O(n²) | O(n + e) | Constant extra work on top of DFS or BFS |
| Building the transpose list | — | O(n + e) | The lists are walked once |
The essence of the table is a single sentence: finding neighbors is O(n) in a matrix and O(d) in a list. All traversal-based algorithms add up this difference over n vertices; it comes to n · n in a matrix and Σd = 2e in a list.
15.7Common mistakes
- Treating a directed graph as undirected. Assuming <v, u> exists when <u, v> does, or assuming that the matrix of a directed graph is symmetric. In G3, a[1][2] = 1 and a[2][1] = 0.
- Setting the mark too late in BFS. Marking a vertex when it is taken out of the queue instead of when it is added. The same vertex enters the queue several times; on the example graph 7 is printed four times.
- Not resetting the mark array.
visitedis global. If it is not set back toFALSEbefore a second traversal, the second traversal cannot enter any vertex and prints only its start. - Multiplying costs in the component analysis. Multiplying the outer
forby DFS and saying O(n(n + e)). Thanks to the marks, the total of all the DFS calls is O(n + e). - Careless memory management. Not checking the result of
malloc; allocating pointer-sized space withsizeof(node_ptr); not callingfreeon the lists at the end of the program; reading an item's link after it has been freed. - Needlessly inserting at the end. Appending the edge to the end of the list and walking the list from the start every time. If order does not matter, the O(1) insertion at the front is enough; the drawing must then show the reversed order that the code produces.
- Forgetting the size in a matrix parameter. Writing
int a[][]does not compile; the second dimension must be given:int a[][MAX_V]. - Choosing
INT_MAXfor infinity. Signed overflow occurs in cost sums; use a safely large constant.
15.8Exercises and solutions
The exercises in this section are given in the order of the slides; each is followed by its solution.
15.8.1Degree sequence
Question. Is there a simple undirected graph with degree sequence (3, 3, 2, 2, 1)? How many edges does it have?
Solution. The sum of the degrees is 11. By Theorem 15.1 the sum must be 2e, that is, even. There is no such graph. The same conclusion follows from the number of odd-degree vertices: there are three, namely 3, 3 and 1, whereas this number must be even.
15.8.2Neighbors in the sequential representation
Question. In the sequential representation of G4, which indices hold the neighbors of vertex 5?
Solution. vertex[5] = 18 and vertex[6] = 20. The neighbors are in the cells with indices 18 and 19: vertex[18] = 4, vertex[19] = 6. The neighbors of 5 are 4 and 6, and its degree is 20 − 18 = 2.
15.8.3Traversals starting from 7
Question. On the eight-vertex example graph, what are the outputs if DFS and BFS are started from 7 (lists sorted)?
Solution. DFS: the list of 7 is {3, 4, 5, 6}; the search descends into the first neighbor, 3. The first unmarked neighbor of 3 is 1, of 1 it is 0, of 0 it is 2, and of 2 it is 5. The neighbors of 5, 2 and 7, are marked; the search returns to 2 and descends into 6. The returns continue up to 1, and 4 in the list of 1 is found. The output is 7 3 1 0 2 5 6 4. BFS: the neighbors of 7, 3, 4, 5, 6, are printed in order and enqueued. When 3 is taken, 1 is added; when 4 is taken, nothing; when 5 is taken, 2 is added. The neighbors of 6 are marked. When 1 is taken, 0 is added. The output is 7 3 4 5 6 1 2 0.
15.8.4Moving the mark line
Question. What happens if, in the BFS code, the line visited[w->vertex] = TRUE is moved to after deleteq?
Solution. A vertex stays unmarked while it waits in the queue. When it is seen in the list of another vertex, it is printed again and added to the queue again. On the example graph, before leaving the queue 7 is added four times, via 3, 4, 5 and 6; bfs(0) prints 0 1 2 3 4 5 6 7 7 7 7. If started from 7, 1, 2 and 0 are also repeated: 7 3 4 5 6 1 1 2 2 0 0 0 0. The output is wrong and the work exceeds O(n + e).
15.8.5Counting components with a matrix
Question. Write a routine that finds the number of components of a graph given as an adjacency matrix; what is its complexity?
Solution. The matrix form of DFS finds the neighbors of a vertex by scanning its row:
void mdfs(int a[][MAX_V], int n, int v)
{
int j;
visited[v] = TRUE;
printf("%d ", v);
for (j = 0; j < n; j++) /* the whole row: O(n) */
if (a[v][j] && !visited[j])
mdfs(a, n, j);
}
int matrix_components(int a[][MAX_V], int n)
{
int i, count = 0;
for (i = 0; i < n; i++) visited[i] = FALSE;
for (i = 0; i < n; i++)
if (!visited[i]) {
count++;
mdfs(a, n, i);
printf("\n");
}
return count;
}mdfs descends into each unmarked neighbor for every 1 in the row of v. matrix_components clears the marks, starts a new traversal from every unmarked vertex and increments the counter. Applied to the matrix of G4, it prints the lines 0 1 3 2 and 4 5 6 7 and returns 2. Each vertex is visited once, and each visit scans a row of n cells: O(n²).
15.8.6Giving the in-degree in O(1)
Question. In a directed graph, which structure is kept to give the in-degree in O(1), and how is it updated?
Solution. A counter in[] is kept for each vertex. When the edge <u, v> is added, in[v]++ is done; when it is deleted, in[v]--. The query is a single array read. If the incoming edges themselves are also needed, an inverse list or an orthogonal list is kept; the length of the inverse list is the in-degree, but counting it is O(d).
15.9Summary
- A graph G = (V, E) is a nonempty vertex set together with a possibly empty edge set. In an undirected graph (u, v) = (v, u); in a directed graph <u, v> ≠ <v, u>.
- Adjacency, subgraph, path, cycle, connectivity and degree are the basic notions. Degree is always stated for a particular vertex; in a directed graph it is the sum of in-degree and out-degree.
- The degrees sum to 2e. In a connected graph n − 1 ≤ e ≤ n(n − 1)/2; the lower bound is necessary but not sufficient.
- The adjacency matrix needs O(n²) memory; an edge query is O(1) and a neighbor scan is O(n). The adjacency list needs O(n + e) memory; a neighbor scan is O(d).
- Insertion at the front places each edge in O(1) and reverses the list relative to the arrival order. In a directed graph, the inverse list for in-degrees is built in O(n + e).
- The sequential array is a pointer-free representation of n + 2e + 1 integers but is unsuited to change. The orthogonal list and the multilist keep each edge in a single item.
- In a weighted graph the matrix gets the weights and the list gets a
weightfield; for infinity a large constant that does not overflow is chosen. - DFS descends with recursion or a stack; BFS advances layer by layer with a queue. Both are O(n + e) with lists and O(n²) with a matrix. The resulting order depends on the start vertex and the list order.
- Connected components are found in O(n + e) by starting a traversal from every unmarked vertex; the costs of the outer loop and the traversal are not multiplied.
- In an undirected graph a marked neighbor that is not the parent, and in a directed graph an edge to a gray vertex, means a cycle. 2-coloring with BFS tests bipartiteness; a bipartite graph has no cycle of odd length.
- Method: first the problem and its operations, then how the data will be stored, and the code last. Do not trust the first representation that comes to mind.
15.10Key terms
- graph
- vertex
- edge
- directed graph
- adjacent
- subgraph
- path
- cycle
- connected
- degree
- in-degree
- out-degree
- complete graph
- adjacency matrix
- adjacency list
- orthogonal list
- adjacency multilist
- depth-first search
- breadth-first search
- spanning tree
- minimum spanning tree
- connected component
- cycle detection
- bipartite graph
- queue
- call stack
- shortest path
15.11Test Yourself
What are the minimum and maximum numbers of edges in a connected simple graph with 9 vertices?
Answer
At least n − 1 = 8, at most 9 · 8 / 2 = 36. A connected graph with 8 edges is a tree; a graph with 36 edges is the complete graph K9.
The adjacency lists of an undirected graph contain 30 items in total. How many edges does the graph have? If the same graph were stored as an adjacency matrix, how many 1s would the matrix contain?
Answer
Since every edge appears in two lists, e = 30 / 2 = 15. In the matrix, too, every edge is written into two symmetric cells: 30 ones.
The lists of G2 are kept sorted. What do
dfs(0)andbfs(0)print?Answer
DFS:
0 1 3 4 2 5 6; this is the same as preorder traversal in the tree. BFS:0 1 2 3 4 5 6; the same as level-order traversal.What does
bfs(6)print on the eight-vertex example graph?Answer
6 2 7 0 5 3 4 1. The neighbors of 6 are 2 and 7. When 2 is taken, 0 and 5 are added; when 7 is taken, 3 and 4. When 0 is taken, 1 is added; the neighbors of the rest are marked.The eight-vertex example graph (e = 10) is stored in the sequential array representation. How many cells does the array have, and at which indices are the neighbors of 7?
Answer
n + 2e + 1 = 8 + 20 + 1 = 29 cells. The starting indices are 9, 11, 14, 17, 19, 21, 23, 25, 29.
vertex[7] = 25,vertex[8] = 29: the neighbors of 7 are at indices 25–28: 3, 4, 5 and 6.The edges of G1 are added to a multilist with
ml_add_edgein the order (0,1), (0,2), (0,3), (1,2), (1,3), (2,3). What doesprint_adj(0)print?Answer
3 2 1. Every edge enters at the front of the lists; in the list of 0 the most recently added, (0,3), is at the front.If
connected(11)is applied to G5 (11 vertices; edges (1,4) and (7,8)), how many lines are printed? How many times is theifentered?Answer
9 lines:
0,1 4,2,3,5,6,7 8,9,10. Theifis entered 9 times; ati= 4 andi= 8 the vertices were already marked in earlier traversals.If only
elseis written instead ofelse if (w->vertex != parent)inhas_cycle, what does the routine return for the tree G2? Why?Answer
It returns
TRUE, although G2 has no cycle.has_cycle(1, 0)sees 0, the first item in the list of 1, as marked and counts it as a back edge. In an undirected graph the edge we arrived by is also in the list of the other endpoint; the parent check is there to set this edge apart.
15.12Further reading
- E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2nd ed., Chapter 6. The representations, the
dfsandbfsroutines and the connected components routine in this chapter follow its presentation; the details of the multilist and the sequential representation are also found there. - T. H. Cormen et al., Introduction to Algorithms, 4th ed., Chapter 20. It gives the white/gray/black coloring of DFS, the classification of edges and the proofs of the shortest path property of BFS.
- R. Sedgewick, Algorithms in C, Part 5: Graph Algorithms, 3rd ed. Graph representations and traversals are treated with C code and with experiments on large graphs.
15.13References
- E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2nd ed., Silicon Press, 2008. Chapter 6, Graphs.
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022. Chapter 20, Elementary Graph Algorithms.
- R. Sedgewick, Algorithms in C, Part 5: Graph Algorithms, 3rd ed., Addison-Wesley, 2002.
Related pages: Chapter 15 slides · © Sercan Külcü. All rights reserved.