第4章：图（Graphs）
一、导读
1.1 本章学习目标
第4章介绍图的基本概念和经典算法。图是描述复杂关系的强大工具。本章核心目标：
- 掌握图的表示方法：邻接矩阵和邻接表
- 深入理解DFS和BFS：两种最基本的图遍历算法
- 掌握最小生成树算法：Prim和Kruskal
- 掌握最短路径算法：Dijkstra算法
- 了解有向图的应用：拓扑排序、强连通分量
1.2 为什么本章如此重要
图是计算机科学中最重要的数据结构之一。社交网络、地图导航、任务调度、编译器优化——几乎所有涉及"关系"的问题都可以用图来建模。DFS和BFS是图算法的基础，理解它们的工作原理，是学习高级图算法的前提。
1.3 核心问题引导
邻接矩阵和邻接表各有什么优缺点？
DFS和BFS的遍历顺序有什么不同？各自适合解决什么问题？
为什么Dijkstra算法不能处理负权边？
最小生成树和最短路径有什么区别？
如何检测图中是否有环？
二、核心概念详解
4.1 图的基本概念
图G=(V,E)由顶点集V和边集E组成。
- 无向图：边没有方向，(v,w)和(w,v)是同一条边
- 有向图：边有方向，<v,w>表示从v到w
- 加权图：边有权重（如距离、费用）
- 路径：顶点序列，相邻顶点之间有边
- 环：起点和终点相同的路径
- 连通图：任意两个顶点之间都有路径
- 度：与顶点相连的边数
4.2 图的表示
4.2.1 邻接矩阵
java
public class GraphMatrix {
private int V;
private int[][] adj;
public GraphMatrix(int V) {
this.V = V;
adj = new int[V][V];
}
public void addEdge(int v, int w) {
adj[v][w] = 1;
adj[w][v] = 1; // 无向图
}
public boolean hasEdge(int v, int w) {
return adj[v][w] != 0;
}
}
// 空间：O(V²)
// 查找边：O(1)
// 遍历邻居：O(V)4.2.2 邻接表
java
import java.util.*;
public class Graph {
private int V;
private List<List<Integer>> adj;
public Graph(int V) {
this.V = V;
adj = new ArrayList<>();
for (int i = 0; i < V; i++)
adj.add(new ArrayList<>());
}
public void addEdge(int v, int w) {
adj.get(v).add(w);
adj.get(w).add(v); // 无向图
}
public Iterable<Integer> adj(int v) {
return adj.get(v);
}
public int V() { return V; }
}
// 空间：O(V + E)
// 查找边：O(degree)
// 遍历邻居：O(degree)4.3 深度优先搜索（DFS）
java
public class DepthFirstSearch {
private boolean[] marked;
private int count;
public DepthFirstSearch(Graph G, int s) {
marked = new boolean[G.V()];
dfs(G, s);
}
private void dfs(Graph G, int v) {
marked[v] = true;
count++;
for (int w : G.adj(v)) {
if (!marked[w]) {
dfs(G, w);
}
}
}
public boolean marked(int v) {
return marked[v];
}
public int count() {
return count;
}
}
// DFS路径查找
public class DepthFirstPaths {
private boolean[] marked;
private int[] edgeTo;
private final int s;
public DepthFirstPaths(Graph G, int s) {
marked = new boolean[G.V()];
edgeTo = new int[G.V()];
this.s = s;
dfs(G, s);
}
private void dfs(Graph G, int v) {
marked[v] = true;
for (int w : G.adj(v)) {
if (!marked[w]) {
edgeTo[w] = v;
dfs(G, w);
}
}
}
public boolean hasPathTo(int v) {
return marked[v];
}
public Iterable<Integer> pathTo(int v) {
if (!hasPathTo(v)) return null;
Stack<Integer> path = new Stack<>();
for (int x = v; x != s; x = edgeTo[x])
path.push(x);
path.push(s);
return path;
}
}4.4 广度优先搜索（BFS）
java
public class BreadthFirstPaths {
private boolean[] marked;
private int[] edgeTo;
private final int s;
public BreadthFirstPaths(Graph G, int s) {
marked = new boolean[G.V()];
edgeTo = new int[G.V()];
this.s = s;
bfs(G, s);
}
private void bfs(Graph G, int s) {
Queue<Integer> queue = new LinkedList<>();
marked[s] = true;
queue.add(s);
while (!queue.isEmpty()) {
int v = queue.poll();
for (int w : G.adj(v)) {
if (!marked[w]) {
edgeTo[w] = v;
marked[w] = true;
queue.add(w);
}
}
}
}
public boolean hasPathTo(int v) {
return marked[v];
}
public Iterable<Integer> pathTo(int v) {
if (!hasPathTo(v)) return null;
Stack<Integer> path = new Stack<>();
for (int x = v; x != s; x = edgeTo[x])
path.push(x);
path.push(s);
return path;
}
}DFS vs BFS：
- DFS：使用栈（递归），适合连通性检测、拓扑排序
- BFS：使用队列，找最短路径（边数最少）
4.5 最小生成树
最小生成树（MST）：连通图中权值之和最小的生成树。
Prim算法（懒实现）
java
public class LazyPrimMST {
private boolean[] marked;
private Queue<Edge> mst;
private PriorityQueue<Edge> pq;
private double weight;
public LazyPrimMST(EdgeWeightedGraph G) {
marked = new boolean[G.V()];
mst = new LinkedList<>();
pq = new PriorityQueue<>();
visit(G, 0);
while (!pq.isEmpty()) {
Edge e = pq.poll();
int v = e.either(), w = e.other(v);
if (marked[v] && marked[w]) continue;
mst.add(e);
weight += e.weight();
if (!marked[v]) visit(G, v);
if (!marked[w]) visit(G, w);
}
}
private void visit(EdgeWeightedGraph G, int v) {
marked[v] = true;
for (Edge e : G.adj(v)) {
if (!marked[e.other(v)])
pq.add(e);
}
}
public double weight() { return weight; }
public Iterable<Edge> edges() { return mst; }
}Kruskal算法
java
public class KruskalMST {
private Queue<Edge> mst;
private double weight;
public KruskalMST(EdgeWeightedGraph G) {
mst = new LinkedList<>();
PriorityQueue<Edge> pq = new PriorityQueue<>();
for (Edge e : G.edges()) pq.add(e);
UF uf = new UF(G.V());
while (!pq.isEmpty() && mst.size() < G.V() - 1) {
Edge e = pq.poll();
int v = e.either(), w = e.other(v);
if (!uf.connected(v, w)) {
uf.union(v, w);
mst.add(e);
weight += e.weight();
}
}
}
public double weight() { return weight; }
public Iterable<Edge> edges() { return mst; }
}4.6 最短路径
Dijkstra算法
java
public class DijkstraSP {
private double[] distTo;
private Edge[] edgeTo;
private PriorityQueue<double[]> pq;
public DijkstraSP(EdgeWeightedGraph G, int s) {
distTo = new double[G.V()];
edgeTo = new Edge[G.V()];
Arrays.fill(distTo, Double.POSITIVE_INFINITY);
distTo[s] = 0.0;
pq = new PriorityQueue<>((a, b) -> Double.compare(a[1], b[1]));
pq.add(new double[]{s, 0.0});
while (!pq.isEmpty()) {
double[] curr = pq.poll();
int v = (int) curr[0];
for (Edge e : G.adj(v)) {
relax(e);
}
}
}
private void relax(Edge e) {
int v = e.either(), w = e.other(v);
if (distTo[w] > distTo[v] + e.weight()) {
distTo[w] = distTo[v] + e.weight();
edgeTo[w] = e;
pq.add(new double[]{w, distTo[w]});
}
}
public double distTo(int v) { return distTo[v]; }
public Iterable<Edge> pathTo(int v) {
Stack<Edge> path = new Stack<>();
for (Edge e = edgeTo[v]; e != null; e = edgeTo[e.either()]) {
path.push(e);
}
return path;
}
}三、实战案例
3.1 课程安排（拓扑排序）
java
public class TopologicalSort {
private Stack<Integer> order;
public TopologicalSort(Digraph G) {
order = new Stack<>();
boolean[] marked = new boolean[G.V()];
boolean[] onStack = new boolean[G.V()];
for (int v = 0; v < G.V(); v++) {
if (!marked[v]) dfs(G, v, marked, onStack);
}
}
private void dfs(Digraph G, int v, boolean[] marked, boolean[] onStack) {
marked[v] = true;
onStack[v] = true;
for (int w : G.adj(v)) {
if (onStack[w]) throw new RuntimeException("Cycle detected");
if (!marked[w]) dfs(G, w, marked, onStack);
}
onStack[v] = false;
order.push(v);
}
public Iterable<Integer> order() { return order; }
}3.2 地图最短路径
java
// 使用Dijkstra算法计算地图上两点间的最短路径
public class MapNavigation {
public static void main(String[] args) {
EdgeWeightedGraph G = new EdgeWeightedGraph(6);
// 添加带权边（城市间的距离）
G.addEdge(new Edge(0, 1, 4)); // A-B: 4km
G.addEdge(new Edge(0, 2, 2)); // A-C: 2km
G.addEdge(new Edge(1, 3, 3)); // B-D: 3km
G.addEdge(new Edge(2, 1, 1)); // C-B: 1km
G.addEdge(new Edge(2, 3, 5)); // C-D: 5km
G.addEdge(new Edge(3, 4, 2)); // D-E: 2km
G.addEdge(new Edge(4, 5, 1)); // E-F: 1km
DijkstraSP sp = new DijkstraSP(G, 0);
System.out.println("Shortest path from A to F:");
System.out.println("Distance: " + sp.distTo(5));
System.out.print("Path: ");
for (Edge e : sp.pathTo(5)) {
System.out.print(e + " ");
}
}
}四、本章小结
第4章介绍了图的核心算法：
图的表示：邻接矩阵（O(V²)空间，O(1)查边）和邻接表（O(V+E)空间，适合稀疏图）。
DFS：递归实现，使用栈。适合连通性检测、拓扑排序、环检测。
BFS：队列实现。找最短路径（边数最少）。
最小生成树：Prim（逐步扩展）和Kruskal（按边排序+并查集）。
最短路径：Dijkstra（贪心+优先队列），不能处理负权边。
五、思考与练习
思考题
为什么稀疏图通常使用邻接表而不是邻接矩阵？
DFS和BFS各自适合解决什么问题？
Dijkstra算法为什么不能处理负权边？Bellman-Ford算法如何解决这个问题？
Prim和Kruskal算法各有什么优缺点？
如何检测有向图中是否有环？
编程练习
实现图的DFS和BFS，比较遍历顺序。
使用BFS解决迷宫最短路径问题。
实现Kruskal算法，使用并查集优化。
使用Dijkstra算法解决地图导航问题。