This is a beta course, so its structure, chapters, and examples may continue to change.

Graphs

A graph is a more general non-linear data structure than a tree: its vertices stand in a “many-to-many” relation, and social networks, map navigation, task scheduling and network topologies can all be abstracted as graphs. This chapter revolves around the storage of a graph, its traversal and four classic applications, and it is the most comprehensive part of the data structures course. After reading this chapter you will be able to understand the basic concepts, the terminology and the properties of a graph, master the two storage structures, the adjacency matrix and the adjacency list, master breadth-first search (BFS) and depth-first search (DFS), master the minimum spanning tree (Prim/Kruskal) and the shortest path (Dijkstra/Floyd) algorithms, and understand the idea and the applications of topological sorting and of the critical path.

Questions This Chapter Answers

How can the arbitrarily complex connections between vertices be represented? The adjacency matrix and the adjacency list are the two most fundamental storage schemes, and each of them has its own trade-offs. On top of that, how to traverse a graph with BFS or DFS, how to find a minimum spanning tree with Prim or Kruskal and a shortest path with Dijkstra or Floyd, and how to perform topological sorting and critical path analysis are the core questions that this chapter takes on one by one.

Basic route: basic concepts → storage structures → graph traversal; master the representation of a graph and the two search algorithms first.

Advanced route: basic applications → summary; understand the classic algorithms such as the minimum spanning tree, the shortest path and the topological sort.

BFS uses a queue and DFS uses recursion or a stack, which is consistent with the level-order and the pre-order rules in trees, so do not confuse them. Prim suits dense graphs and Kruskal suits sparse graphs; Dijkstra is single-source with non-negative weights and Floyd is multi-source and allows negative weights, and these comparisons are a common choice question.

Basic Concepts

A graph (Graph) consists of a vertex set V and an edge set E, and it is written $G=(V, E)$ . An edge may have a direction (a directed graph) or no direction (an undirected graph), and it may carry a weight (a network).

Common Terminology

Adjacent: two vertices are joined by an edge
Degree: the number of edges incident to a vertex in an undirected graph; in a directed graph it is split into an in-degree and an out-degree
Path: a sequence of vertices whose edges do not repeat (a simple path)
Cycle (circuit): a path whose starting vertex and ending vertex are the same
Connected: in an undirected graph there is a path between any two vertices; in a directed graph the mutual reachability of any two vertices is called strongly connected
Connected component: a maximal connected subgraph of an undirected graph
Spanning tree: a minimal connected subgraph of a connected graph that contains all the vertices but only n-1 edges

Properties of Graphs

In an undirected graph, the sum of the degrees of all the vertices equals twice the number of edges
In a directed graph, the sum of the in-degrees of all the vertices equals the sum of the out-degrees, and both equal the number of edges
A complete undirected graph with n vertices has $\frac{n(n-1)}{2}$ edges
A complete directed graph with n vertices has $n(n-1)$ edges

Exercises

Exercise 1

Among the following statements about graphs, the incorrect one is ( )

(A) In an undirected graph, the sum of the degrees of all the vertices equals twice the number of edges (B) In a directed graph, the sum of the in-degrees of all the vertices equals the sum of the out-degrees of all the vertices (C) A complete undirected graph with n vertices has n(n-1)/2 edges (D) A complete directed graph with n vertices has n(n-1)/2 edges

Reference Answer

graphcomplete graphvertex degreedirected graph

Approach:

This question tests the basic properties of a graph. The idea is to check one by one the classic conclusions on which the four options rely: in an undirected graph the sum of the degrees equals twice the number of edges, in a directed graph the sum of the in-degrees equals the sum of the out-degrees, and the number of edges of a complete graph has to distinguish the directed case from the undirected one.

Steps:

Option (A) is correct: in an undirected graph every edge is incident to two vertices and therefore contributes 2 to the total degree, so the sum of the degrees of all the vertices equals twice the number of edges.
Option (B) is correct: in a directed graph every arc contributes one in-degree and one out-degree, so the sum of the in-degrees of all the vertices equals the sum of the out-degrees.
Option (C) is correct: in a complete undirected graph there is exactly one edge between each pair of vertices, so the number of edges is $\frac{n(n-1)}{2}$ .
Option (D) is wrong: in a complete directed graph there are two oppositely directed edges between each pair of vertices, so the number of edges is $n(n-1)$ ; $\frac{n(n-1)}{2}$ is the number of edges of a complete undirected graph.

Answer:

Exercise 2

Briefly describe the basic concepts and the common terminology of a graph.

Reference Answer

graphvertex set and edge setvertex degreeconnectivity

Approach:

This question tests the basic concepts and the common terminology of a graph. In the answer, first give the definition of a graph and its two classifications, and then explain the terms one by one in the order: the relation between the vertices and the edges, the vertex degrees, the paths and the cycles, the connectivity, and the properties of a graph.

Steps:

A graph consists of a vertex set and an edge set, and according to whether the edges have a direction it is divided into directed graphs and undirected graphs.
Adjacent: two vertices are joined by an edge; degree: the number of edges incident to a vertex, which is split into an in-degree and an out-degree in a directed graph.
Connected: there is a path between any two vertices; connected component: a maximal connected subgraph of the graph.
Path: a sequence of edges from one vertex to another; cycle: a path whose start and end are the same; weight: the numeric value on an edge; spanning tree: a minimal connected subgraph that contains all the vertices and has no cycle.

Answer:

A graph consists of a vertex set and an edge set, and it is divided into directed graphs and undirected graphs. The common terms are: adjacent (two vertices joined by an edge), degree (the number of incident edges, split into an in-degree and an out-degree in a directed graph), connected (a path exists between any two vertices), weight (the numeric value on an edge), path, cycle, connected component, spanning tree, and so on.

Storage Structures

Adjacency Matrix

It is stored in a two-dimensional array $A[n][n]$ , where $A[i][j]=1$ indicates that there is an edge between vertex i and vertex j.

Advantages: deciding whether two vertices are adjacent takes $O(1)$ . Disadvantages: the space cost is $O(n^2)$ , so it suits dense graphs.

#define MaxVertexNum 100
typedef struct {
    int edges[MaxVertexNum][MaxVertexNum];  // adjacency matrix
    int n, e;  // number of vertices, number of edges
} MGraph;

Adjacency List

Every vertex stores all of its adjacent vertices in a linked list.

Advantages: the space cost is $O(n+e)$ , so it suits sparse graphs. Disadvantages: deciding whether two vertices are adjacent requires traversing the linked list.

typedef struct ArcNode {       // edge table node
    int adjvex;                // index of the adjacent vertex
    struct ArcNode *next;
} ArcNode;

typedef struct VNode {         // vertex table node
    int data;
    ArcNode *first;            // points to the first edge
} VNode, AdjList[MaxVertexNum];

typedef struct {
    AdjList vertices;
    int n, e;
} ALGraph;

Other Storage Structures

Orthogonal list: used for directed graphs, it records both the in-edges and the out-edges
Adjacency multilist: used for undirected graphs, it stores every edge only once

Exercises

Exercise 1

An undirected graph with n vertices and e edges is stored in an adjacency list. How many edge table nodes does the adjacency list contain ( )

A. n B. e C. 2e D. n+e

Reference Answer

adjacency listundirected graphedge table nodestorage space

Approach:

This question tests the number of edge table nodes in an adjacency list. The key is to work out how many times one edge of an undirected graph is registered in the adjacency list: once in the edge table of each of its two endpoints.

Steps:

The adjacency list builds an edge table for every vertex, and the linked list of that table records all the vertices adjacent to it.
In an undirected graph an edge $(u, v)$ has to be registered once in the edge table of vertex $u$ and once in the edge table of vertex $v$ , so it occupies two edge table nodes in total.
There are $e$ edges, so the total number of edge table nodes is $2e$ , which corresponds to option C.

Answer:

C (2e).

Exercise 2

What are the advantages and the disadvantages of the adjacency matrix and of the adjacency list?

Reference Answer

adjacency matrixadjacency liststorage spaceapplicable scenarios

Approach:

This question tests the comparison between the two storage structures of a graph. In the answer, evaluate the time and the space cost of the two structures with respect to the two key operations, deciding whether two vertices are adjacent and enumerating all the neighbours of a vertex, and then state the scenarios in which each of them applies.

Steps:

The advantages of the adjacency matrix: deciding whether two vertices are adjacent needs only a direct table lookup, which is $O(1)$ , and the implementation is simple; the disadvantages: the space cost is $O(n^2)$ , which wastes a great deal of space for a sparse graph, so it suits dense graphs.
The advantages of the adjacency list: the space cost is $O(n+e)$ , which saves storage space; the disadvantages: deciding whether two vertices are adjacent requires traversing the linked list, so it suits sparse graphs.
Conclusion: a dense graph whose number of edges is close to the square of the number of vertices should use the adjacency matrix, and a sparse graph whose number of edges is far smaller than the square of the number of vertices should use the adjacency list.

Answer:

Adjacency matrix: the advantages are that deciding adjacency takes $O(1)$ and that the implementation is simple; the disadvantages are the space cost of $O(n^2)$ and the large waste of space, so it suits dense graphs. Adjacency list: the advantages are the space cost of $O(n+e)$ and the saved storage space; the disadvantages are that deciding adjacency requires traversing the linked list, so it suits sparse graphs.

Graph Traversal

Breadth-First Search (BFS)

Starting from a starting vertex, it visits all of its adjacent vertices first and then visits the adjacent vertices of those adjacent vertices in turn; it is implemented with a queue and it resembles the level-order traversal of a tree.

bool visited[MAX];
void BFS(ALGraph G, int v) {
    InitQueue(Q);
    visit(v);
    visited[v] = true;
    EnQueue(Q, v);
    while (!QueueEmpty(Q)) {
        DeQueue(Q, v);
        for (ArcNode *p = G.vertices[v].first; p; p = p->next) {
            if (!visited[p->adjvex]) {
                visit(p->adjvex);
                visited[p->adjvex] = true;
                EnQueue(Q, p->adjvex);
            }
        }
    }
}

Complexity: $O(n+e)$ with an adjacency list and $O(n^2)$ with an adjacency matrix.

Depth-First Search (DFS)

Starting from a starting vertex, it keeps going until it reaches the end and then backtracks; it is implemented with recursion (a stack) and it resembles the pre-order traversal of a tree.

void DFS(ALGraph G, int v) {
    visit(v);
    visited[v] = true;
    for (ArcNode *p = G.vertices[v].first; p; p = p->next) {
        if (!visited[p->adjvex]) {
            DFS(G, p->adjvex);  // recursively visit an adjacent vertex that has not been visited
        }
    }
}

Complexity: $O(n+e)$ with an adjacency list and $O(n^2)$ with an adjacency matrix.

BFS uses a queue (first in, first out) and DFS uses a stack or recursion (last in, first out). This is consistent with the rule in trees that the level-order traversal uses a queue while the pre-order, the in-order and the post-order traversals use recursion, so do not confuse them!

Exercises

Exercise 1

What are the basic ideas and the implementation styles of DFS and BFS?

Reference Answer

depth-first searchbreadth-first searchgraph traversaltime complexity

Approach:

This question tests the ideas and the implementations of the two graph traversal algorithms. The idea is to explain first the difference in the visiting order, going deep versus advancing layer by layer, then to point out the data structure each of them corresponds to, and finally to compare their time complexities.

Steps:

DFS (depth-first search): starting from a vertex, it visits the adjacent vertices in the depth direction first and backtracks when it reaches the end; it is implemented with recursion (a stack) and it resembles the pre-order traversal of a tree.
BFS (breadth-first search): starting from a vertex, it visits all of the adjacent vertices first and then the adjacent vertices of those vertices; it is implemented with a queue and it resembles the level-order traversal of a tree.
The two have the same time complexity: $O(n+e)$ with an adjacency list representation and $O(n^2)$ with an adjacency matrix representation.

Answer:

DFS (depth-first search): starting from a vertex, it visits the adjacent vertices in the depth direction first and backtracks when it reaches the end; it is implemented with recursion (a stack) and it resembles the pre-order traversal of a tree. BFS (breadth-first search): starting from a vertex, it visits all of the adjacent vertices first and then the adjacent vertices of those vertices; it is implemented with a queue and it resembles the level-order traversal of a tree. The two have the same time complexity: $O(n+e)$ with an adjacency list and $O(n^2)$ with an adjacency matrix.

Basic Applications

Minimum Spanning Tree (MST)

In a connected undirected weighted graph, find a spanning tree that contains all the vertices and whose edge weights sum to the minimum.

Algorithm	Idea	Complexity	Applicable to
Prim	Start from a vertex and each time pick the lightest edge that connects the selected set	$O(n^2)$	Dense graphs
Kruskal	Pick the edges in increasing order of weight and use a union-find to detect cycles	$O(e\log e)$	Sparse graphs

Shortest Path

Algorithm	Problem solved	Complexity	Remarks
Dijkstra	Single-source shortest path	$O(n^2)$	Cannot handle negative-weight edges
Floyd	Shortest path between every pair of vertices	$O(n^3)$	Can handle negative-weight edges, dynamic programming

Topological Sort

It orders the vertices of a directed acyclic graph (DAG) so that the starting vertex of every edge comes before its ending vertex. It is used to detect whether a graph contains a cycle, for task scheduling and so on. Each time a vertex whose in-degree is 0 is selected, it is output and its out-edges are deleted.

Complexity: $O(n+e)$ . If the topological sort outputs fewer than n vertices, the graph contains a cycle.

Critical Path

In an AOE network (a weighted directed graph whose edges represent activities), the path of the greatest length from the source to the sink is called the critical path, and the activities on it are the critical activities. The length of the critical path determines the shortest possible duration of the project.

Exercises

Exercise 1

Given a directed acyclic graph whose topological sequence is unique, this graph must be ( )

(A) A strongly connected graph (B) A complete directed graph (C) A directed tree (D) A directed chain

Reference Answer

topological sortdirected acyclic graphdirected chainuniqueness of the topological sequence

Approach:

This question works backwards from a unique topological sequence to the structure of the graph. The idea is that a unique topological sequence means that a definite precedence relation exists between any two vertices, and such a global strict order can only hold when all the vertices are strung into a single chain.

Steps:

A unique topological sequence means that there is a clear precedence relation between any two vertices of the graph, and that there is no pair of independent vertices whose positions could be swapped freely.
If the graph contains any structure other than a directed chain, a branch of a directed tree or a complete directed graph for instance, then two mutually unconstrained vertices appear, their relative order can be exchanged, and several topological sequences appear.
Therefore only a directed chain in which all the vertices form a single chain can guarantee a unique topological sequence, which corresponds to option (D).

Answer:

D (a directed chain).

Exercise 2

Among the following algorithms, the one that solves the single-source shortest path problem and requires non-negative edge weights is ( )

A. The Prim algorithm B. The Dijkstra algorithm C. The Floyd algorithm D. The Kruskal algorithm

Reference Answer

single-source shortest pathDijkstra algorithmnon-negative edge weightsapplicability of the algorithm

Approach:

This question tests the range of applicability of the shortest path algorithms. The idea is to classify the four algorithms by the problem each of them solves: Prim and Kruskal belong to the minimum spanning tree, Floyd belongs to the multi-source shortest path and allows negative-weight edges, and only Dijkstra is exactly the single-source shortest path with the requirement of non-negative edge weights.

Steps:

The Dijkstra algorithm solves the single-source shortest path problem and requires non-negative edge weights, so option B is correct.
The Floyd algorithm solves the shortest path between every pair of vertices and allows negative-weight edges, as long as the graph contains no negative-weight cycle, so it does not meet the single-source requirement.
The Prim algorithm and the Kruskal algorithm solve the minimum spanning tree problem, that is, connecting all the vertices with the minimum total weight, which has nothing to do with the shortest path.

Answer:

Exercise 3

Which algorithms are commonly used for the minimum spanning tree and for the shortest path, and what are their complexities?

Reference Answer

minimum spanning treeshortest pathPrim algorithmDijkstra algorithm

Approach:

This question tests the common algorithms of the minimum spanning tree and of the shortest path together with their complexities. In the answer, list the two kinds of problem separately: for the minimum spanning tree give Prim and Kruskal together with the dense or sparse case each of them suits, and for the shortest path give Dijkstra and Floyd together with the difference between the single-source and the every-pair case.

Steps:

For the minimum spanning tree: the Prim algorithm has a complexity of $O(n^2)$ and suits dense graphs; the Kruskal algorithm has a complexity of $O(e \log e)$ and suits sparse graphs.
For the shortest path: the Dijkstra algorithm solves the single-source shortest path with a complexity of $O(n^2)$ and it requires non-negative edge weights.
The Floyd algorithm solves the shortest path between every pair of vertices with a complexity of $O(n^3)$ and it allows negative-weight edges, as long as there is no negative-weight cycle.

Answer:

Minimum spanning tree: the Prim algorithm ( $O(n^2)$ , suits dense graphs) and the Kruskal algorithm ( $O(e \log e)$ , suits sparse graphs). Shortest path: the Dijkstra algorithm (single-source, $O(n^2)$ , requires non-negative edge weights) and the Floyd algorithm (every pair of vertices, $O(n^3)$ , allows negative-weight edges).

Exercise 4

What are the application scenarios of topological sorting?

Reference Answer

topological sortdirected acyclic graphdependency schedulingcycle detection

Approach:

This question tests the preconditions and the typical application scenarios of topological sorting. The idea is to point out first that topological sorting only makes sense for a directed acyclic graph, then to summarize its role as producing a legal precedence order according to the dependencies, and to list the corresponding scenarios.

Steps:

Topological sorting is used on a directed acyclic graph (DAG); it outputs the vertices step by step according to whether their in-degree is zero, and thus produces a linear sequence that satisfies the precedence relation of every directed edge.
The precedence order of course schedules: a prerequisite has to come before the courses that build on it.
The dependency scheduling of engineering tasks and the compilation order of the source files in a compiler belong to the same kind of scenario, in which a precondition comes first.
In addition, if no vertex whose in-degree is zero can be found during the topological sort, the graph contains a cycle, so topological sorting can also be used to detect whether a directed graph contains a cycle.

Answer:

Topological sorting is used on a directed acyclic graph (DAG), and its application scenarios include the precedence order of course schedules, the dependency scheduling of engineering tasks, the compilation order of the source files in a compiler, and detecting whether a directed graph contains a cycle.

Summary

The terminology of this chapter is the densest in the whole book: the adjacency matrix and the adjacency list determine how a graph is stored, DFS and BFS determine how it is traversed, and the minimum spanning tree, the shortest path and the topological sort are three classic problems. The terminology reference aligns the Chinese and the English wording, while the key takeaways give the degree relations and the traversal complexities that have to be remembered; it is recommended to come back to this summary after finishing the exercises of this chapter.

Terminology Reference

Term	Abbreviation	Explanation
Graph	-	A collection of a vertex set and an edge set
Directed graph	-	The edges have a direction
Undirected graph	-	The edges have no direction
Adjacency matrix	-	Stored in a two-dimensional array
Adjacency list	-	The adjacent vertices are stored in linked lists
Depth-first search	DFS	Uses recursion or a stack, going deep first
Breadth-first search	BFS	Uses a queue, visiting layer by layer
Minimum spanning tree	MST	A spanning tree with the minimum sum of the weights
Shortest path	-	The shortest path between two vertices
Topological sort	-	A linear ordering of the vertices of a DAG
Critical path	-	The longest path, which determines the duration

Key Takeaways

In an undirected graph the sum of the degrees is 2e; in a directed graph the sum of the in-degrees equals the sum of the out-degrees and both equal e
BFS uses a queue and DFS uses recursion or a stack, and both have a complexity of $O(n+e)$ with an adjacency list
Prim suits dense graphs and Kruskal suits sparse graphs
Dijkstra is single-source with non-negative weights, while Floyd is multi-source and allows negative weights
If the topological sort outputs fewer than n vertices, the graph contains a cycle

Trees and Binary Trees

Sorting

Found an issue with this content?

Tell us what could be improved.

Unlock Full Course ·

Your membership covers this course — no need to buy it again.

Login Required to Purchase

Payment Failed

Payment Successful!

Price History

Graphs

Questions This Chapter Answers

Basic Concepts

Common Terminology

Properties of Graphs

Exercises

Exercise 1

Exercise 2

Storage Structures

Adjacency Matrix

Adjacency List

Other Storage Structures

Exercises

Exercise 1

Exercise 2

Graph Traversal

Breadth-First Search (BFS)

Depth-First Search (DFS)

Exercises

Exercise 1

Basic Applications

Minimum Spanning Tree (MST)

Shortest Path

Topological Sort

Critical Path

Exercises

Exercise 1

Exercise 2

Exercise 3

Exercise 4

Summary

Terminology Reference

Key Takeaways

Send feedback