14.图-存储与遍历.md 12 KB
14. 图-存储与遍历
概念
图（Graph） 由顶点集 V 和边集 E 组成，记为 G = (V, E)。图中的数据元素称为顶点（Vertex），顶点之间的关系称为边（Edge）。图比树更一般：树是一种特殊的图（连通且无环），而图中任意两个顶点之间都可以相连。
按边是否有方向，图分为两类：
- 无向图：边没有方向，用圆括号 (u, v) 表示，且 (u,v) 与 (v,u) 是同一条边。
- 有向图：边有方向，用尖括号
<u, v>表示，代表从 u 指向 v 的弧，u 称为弧尾，v 称为弧头。
若边上带有数值（权值），则称为带权图，也叫网（Network）。权值常表示距离、花费、时间等。
顶点的度（Degree）：无向图中顶点的度是与它相连的边数；有向图中分为入度（指向该顶点的边数）和出度（从该顶点发出的边数）。
连通与连通分量：无向图中，若两个顶点之间存在路径则称它们连通；若任意两个顶点都连通，则该图为连通图。无向图的极大连通子图称为连通分量（连通图只有一个连通分量，即它本身）。有向图中，若任意两个顶点相互可达（双向都有路径），则称为强连通图，其极大强连通子图称为强连通分量。
两种存储结构
1. 邻接矩阵（Adjacency Matrix）
用二维数组 g[n][n] 存储：g[i][j] = 1 表示顶点 i 到 j 有边（无向图中对称，g[i][j] = g[j][i]）；带权图存权值、无边存无穷大 ∞、对角线存 0。
0 1 2 3 4
0 | 0 1 1 0 0
1 | 1 0 0 1 1
2 | 1 0 0 0 1
3 | 0 1 0 0 0
4 | 0 1 1 0 0
2. 邻接表（Adjacency List）
用一个顶点表数组，每个顶点挂一条单链表，链表中的每个结点存储一个邻接顶点的编号（无向图每条边出现两次，两个方向各一次；有向图通常只存出边）。
邻接矩阵 vs 邻接表对比：
| 对比项 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 存储空间 | O(n²)，与边数无关 | O(n+e)，稀疏图省空间 |
| 判断两点是否相邻 | O(1) | O(deg(v))，需扫描链表 |
| 找出某点的所有邻点 | O(n) | O(deg(v)) |
| 求顶点的度 | 无向图 O(n)，有向图需统计行列 | 无向图 O(deg)，有向图还须另建入度表 |
| 适用场景 | 稠密图（边数接近 n²） | 稀疏图（边数接近 n） |
核心操作 / 算法
- 建立图：读入顶点和边。邻接矩阵直接填矩阵；邻接表把边的两个端点插入对方（或单向）的链表中。
- BFS 广度优先遍历（Breadth-First Search）：借助队列。从起点出发先访问它，再将其所有未访问的邻点入队；随后依次出队并重复"访问 + 邻点入队"。特点：一层一层向外扩展（类似树的层次遍历），可求无权图的最短路径。
- DFS 深度优先遍历（Depth-First Search）：借助递归（系统栈）或显式栈。从起点出发沿一条路径走到尽头，走不通就回退（回溯）换路再走。特点：一条路走到底再回头。
- 遍历的应用：判断连通性、求连通分量、检测环、求路径等。BFS 与 DFS 都要保证每个顶点只访问一次，用 visited 数组标记。
复杂度分析
| 操作 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 判断两点是否相邻 | O(1) | O(deg(v)) |
| BFS 遍历 | O(n²) | O(n+e) |
| DFS 遍历 | O(n²) | O(n+e) |
| 存储空间 | O(n²) | O(n+e) |
为什么：
- 邻接矩阵 BFS/DFS 中，每个顶点都要扫描一整行（n 个位置）来寻找邻点，n 个顶点共 O(n²)；即使边很少也必须查遍矩阵，空间恒为 O(n²)。
- 邻接表中，每个顶点恰好出队/入栈一次，共 O(n)；每条边恰好被扫描一次，共 O(e)，总计 O(n+e)。空间上每个顶点一个表头 O(n)，无向图每条边两个边结点 O(2e)，即 O(n+e)。
语言实现
下面 4 种语言的实现演示相同的操作：用邻接表存储同一个无向图（5 个顶点、5 条边），从顶点 0 出发分别做 BFS 和 DFS 并打印遍历序列。
C
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 20
// 邻接表边结点：存储一个邻接顶点
typedef struct ArcNode {
int adjvex; // 邻接顶点的编号
struct ArcNode *next; // 指向下一条边的结点
} ArcNode;
// 顶点表结点
typedef struct VNode {
int data; // 顶点信息
ArcNode *first; // 指向第一条边
} VNode;
// 图结构：顶点表 + 顶点数
typedef struct {
VNode vertices[MAX_VERTICES];
int n;
} ALGraph;
// 初始化图：顶点编号 0..n-1 作为顶点数据
void initGraph(ALGraph *g, int n) {
g->n = n;
for (int i = 0; i < n; i++) {
g->vertices[i].data = i;
g->vertices[i].first = NULL;
}
}
// 向链表中尾部追加一个边结点（保持与其它语言 push_back 一致的顺序）
void appendArc(VNode *vnode, int v) {
ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = v;
p->next = NULL;
if (vnode->first == NULL) {
vnode->first = p;
return;
}
ArcNode *t = vnode->first;
while (t->next != NULL) t = t->next;
t->next = p;
}
// 无向图加边 (u,v)：两个方向都要加
void addEdge(ALGraph *g, int u, int v) {
appendArc(&g->vertices[u], v);
appendArc(&g->vertices[v], u);
}
// BFS：借助队列，从 start 出发广度优先遍历
void bfs(ALGraph *g, int start) {
int visited[MAX_VERTICES] = {0};
int queue[MAX_VERTICES], front = 0, rear = 0;
queue[rear++] = start;
visited[start] = 1;
while (front < rear) {
int u = queue[front++];
printf("%d ", u);
for (ArcNode *p = g->vertices[u].first; p != NULL; p = p->next) {
int v = p->adjvex;
if (!visited[v]) {
visited[v] = 1;
queue[rear++] = v;
}
}
}
printf("\n");
}
// DFS 辅助：递归访问顶点 u
void dfsVisit(ALGraph *g, int u, int visited[]) {
printf("%d ", u);
visited[u] = 1;
for (ArcNode *p = g->vertices[u].first; p != NULL; p = p->next) {
int v = p->adjvex;
if (!visited[v])
dfsVisit(g, v, visited);
}
}
// DFS：从 start 出发深度优先遍历（递归）
void dfs(ALGraph *g, int start) {
int visited[MAX_VERTICES] = {0};
dfsVisit(g, start, visited);
printf("\n");
}
int main() {
ALGraph g;
initGraph(&g, 5);
// 无向图的边 (u, v)
int edges[][2] = {{0,1}, {0,2}, {1,3}, {1,4}, {2,4}};
for (int i = 0; i < 5; i++)
addEdge(&g, edges[i][0], edges[i][1]);
printf("BFS from 0: ");
bfs(&g, 0);
printf("DFS from 0: ");
dfs(&g, 0);
return 0;
}
C++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// 邻接表：vector<int> 的数组，每个元素存邻接顶点编号
class Graph {
public:
int n;
vector<vector<int>> adj;
Graph(int n) : n(n), adj(n) {}
// 无向图加边 (u,v)
void addEdge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u);
}
// BFS：借助队列，从 start 出发广度优先遍历
void bfs(int start) {
vector<bool> visited(n, false);
queue<int> q;
q.push(start);
visited[start] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
cout << u << " ";
for (int v : adj[u]) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
cout << endl;
}
// DFS 辅助：递归访问顶点 u
void dfsVisit(int u, vector<bool>& visited) {
cout << u << " ";
visited[u] = true;
for (int v : adj[u])
if (!visited[v])
dfsVisit(v, visited);
}
// DFS：从 start 出发深度优先遍历
void dfs(int start) {
vector<bool> visited(n, false);
dfsVisit(start, visited);
cout << endl;
}
};
int main() {
Graph g(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 4);
cout << "BFS from 0: ";
g.bfs(0);
cout << "DFS from 0: ";
g.dfs(0);
return 0;
}
Java
import java.util.*;
public class GraphTraversal {
private int n;
private List<List<Integer>> adj;
public GraphTraversal(int n) {
this.n = n;
adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
}
// 无向图加边 (u,v)
public void addEdge(int u, int v) {
adj.get(u).add(v);
adj.get(v).add(u);
}
// BFS：借助队列
public void bfs(int start) {
boolean[] visited = new boolean[n];
Queue<Integer> q = new LinkedList<>();
q.offer(start);
visited[start] = true;
while (!q.isEmpty()) {
int u = q.poll();
System.out.print(u + " ");
for (int v : adj.get(u)) {
if (!visited[v]) {
visited[v] = true;
q.offer(v);
}
}
}
System.out.println();
}
// DFS：递归
public void dfs(int start) {
boolean[] visited = new boolean[n];
dfsVisit(start, visited);
System.out.println();
}
private void dfsVisit(int u, boolean[] visited) {
System.out.print(u + " ");
visited[u] = true;
for (int v : adj.get(u))
if (!visited[v])
dfsVisit(v, visited);
}
public static void main(String[] args) {
GraphTraversal g = new GraphTraversal(5);
int[][] edges = {{0,1}, {0,2}, {1,3}, {1,4}, {2,4}};
for (int[] e : edges) g.addEdge(e[0], e[1]);
System.out.print("BFS from 0: ");
g.bfs(0);
System.out.print("DFS from 0: ");
g.dfs(0);
}
}
Python
from collections import deque
class Graph:
"""邻接表实现的图（无向）"""
def __init__(self, n):
self.n = n
self.adj = [[] for _ in range(n)] # 邻接表：每个顶点一个列表
def add_edge(self, u, v):
"""无向图加边"""
self.adj[u].append(v)
self.adj[v].append(u)
def bfs(self, start):
"""BFS：借助队列"""
visited = [False] * self.n
q = deque([start])
visited[start] = True
order = []
while q:
u = q.popleft()
order.append(u)
for v in self.adj[u]:
if not visited[v]:
visited[v] = True
q.append(v)
return order
def dfs(self, start):
"""DFS：递归"""
visited = [False] * self.n
order = []
self._dfs(start, visited, order)
return order
def _dfs(self, u, visited, order):
order.append(u)
visited[u] = True
for v in self.adj[u]:
if not visited[v]:
self._dfs(v, visited, order)
if __name__ == "__main__":
g = Graph(5)
edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 4)]
for u, v in edges:
g.add_edge(u, v)
print("BFS from 0:", g.bfs(0))
print("DFS from 0:", g.dfs(0))