图

图（Graph）是一种多对多的非线性数据结构。树是图的一种特例（树是"一对多"，图是"任意点之间都可能有边"）。

---

一、图

1.1 图的定义

图：由顶点（节点）和边组成。边连接两个顶点。

graph TD  
 A --- B 
 B --- C 
 A --- C 
 B --- D 
 C --- D  

顶点：A、B、C、D（4 个）
边：A-B、A-C、B-C、B-D、C-D（5 条）

1.2 名词：点、边、权

带权图（边上标数值）：

graph TD  
 A ---|3| B 
 A ---|5| C 
 B ---|2| C  

A-B 的权是 3，A-C 的权是 5，B-C 的权是 2。

1.3 有向图与无向图

无向图：边没有方向，A-B 和 B-A 是同一条边。

graph LR  
 A --- B
  B --- D
   D --- C 
   C --- A  

有向图：边有方向，A→B 和 B→A 是两条不同的边。

graph LR  
 A --> B 
 A --> C 
 B --> D 
 C --> D  

无向边用 ---，有向边用 -->。有向图的边 A→B 和 B→A 是两条不同的边。

1.4 完全图

完全图：任意两个顶点之间都有边。

无向完全图 K_n：n 个顶点，边数 = n(n-1) / 2

无向完全图 K4（4 个顶点，6 条边）：

graph TD  
 A --- B 
 A --- C 
 A --- D 
 B --- C 
 B --- D 
 C --- D  

6 条边：A-B、A-C、A-D、B-C、B-D、C-D

有向完全图：n 个顶点，每对顶点之间有两个方向，边数 = n(n-1)

💡 记忆：无向图每条边被算了 2 次，所以要除以 2；有向图两个方向各算一条，不用除。

1.5 度的概念

度：一个顶点连了几条边。

• 无向图：度 = 和该顶点相连的边数；
• 有向图：分成入度（指向它的边数）和出度（从它指出的边数）。

无向图（A 连 B、C，度是 2）：

graph LR  
 A --- B 
 B --- D 
 D --- C 
 C --- A  

有向图（A 出度 2，D 入度 2）：

graph LR  
 A --> B 
 A --> C 
 B --> D 
 C --> D  

A 有 2 条边指向外（A→B、A→C），出度 = 2；D 有 2 条边指向它（B→D、C→D），入度 = 2。

握手定理（无向图）：所有顶点的度之和 = 边数 × 2。因为每条边给两个端点各贡献 1 度。

1.6 连通性

连通图（无向图）：任意两个顶点之间都有路径。

连通图：

graph LR  
 A --- B 
 B --- D 
 D --- C 
 C --- A  

非连通图（有 2 个连通分量）：

graph LR  
 A --- B 
 B --- D 
 D --- C 
 C --- A 
 E --- F 
 F --- H 
 H --- G 
 G --- E  

• 连通分量：极大的连通子图。上面右边这张图有 2 个连通分量。
• 强连通图（有向图）：任意两个顶点之间互相可达（有双向路径）。

1.7 有向无环图与树图

有向无环图（DAG）：有向图，且没有环（不会走一圈回到起点）。

DAG（无环）：

graph LR  
 A --> B --> C  

有环（A→B→C→D→A 走一圈回来）：

graph LR  
 A --> B --> C --> D --> A  

树：连通且无环的无向图。n 个节点的树，恰好有 n-1 条边。

graph TD  
 A --> B 
 A --> C 
 C --> D 
 C --> E  

💡 树 = 图的特例：连通、无环。所以树是"一对多"，图是"多对多"。

---

二、图的存储

2.1 邻接矩阵

用一个二维数组 g[i][j] 表示：顶点 i 到顶点 j 有没有边（或边的权值）。

图：

1---2  
|   |  
3---4  

邻接矩阵（1 表示有边，0 表示无边）：

     1  2  3  4 
 1   0  1  1  0 
 2   1  0  0  1 
 3   1  0  0  1 
 4   0  1  1  0

代码：

const int N = 1005;  
int g[N][N];   // g[i][j] = 1 表示 i 到 j 有边  
  
// 无向图，边 u-vg[u][v] = g[v][u] = 1;  
  
// 有向图，边 u -> vg[u][v] = 1;  

带权图：

int g[N][N];   // g[i][j] = w 表示权值（0 或 INF 表示无边）  
g[u][v] = g[v][u] = w;  

2.2 邻接表

每个顶点用一个链表（或 vector）存它连到的所有顶点。

图：

1---2  
|   |  
3---4  

邻接表：

1: 2, 3  
2: 1, 4  
3: 1, 4  
4: 2, 3  

代码：

const int N = 100005;  
vector<int> g[N];   // g[i] 存顶点 i 连到的所有顶点  
  
// 无向图，边 u-v（两边都要加）  
g[u].push_back(v);  
g[v].push_back(u);  
  
// 有向图，边 u -> v（只加一边）  
g[u].push_back(v);  

带权图（存边 + 权值）：

struct Edge { int to, w; };  
vector<Edge> g[N];  
  
g[u].push_back({v, w});  
g[v].push_back({u, w});   // 无向图双向加  

💡 选哪个？顶点少（n ≤ 1000）用邻接矩阵；顶点多（n 上万）用邻接表。

---

三、图的遍历

3.1 深度优先 DFS

DFS（Depth First Search）：从起点出发，一条路走到底，走不通再回头换路。

graph TD  
 1 --> 2 
 1 --> 3 
 2 --> 4 
 2 --> 5 
 3 --> 6  

从 1 开始 DFS，遍历顺序：1 2 4 5 3 6

（先沿着 1→2→4 走到底，再回头走 5，再走 3→6）

代码：

const int N = 100005;
vector<int> g[N];
bool vis[N];

void dfs(int u) {
	vis[u] = true;              // 标记访问过
	cout << u << ' ';           // 处理当前节点
	for (int v : g[u])          // 遍历所有邻居
		if (!vis[v]) dfs(v);    // 没访问过就递归深入
}

💡 特点：递归 + 回溯，配合 vis 数组防止重复访问。DFS 天然用"栈"（系统调用栈）实现。

3.2 广度优先 BFS

BFS（Breadth First Search）：从起点出发，一层一层往外扩展。

graph TD  
 1 --> 2 1 --> 3 2 --> 4 2 --> 5 3 --> 6  

从 1 开始 BFS，遍历顺序：1 2 3 4 5 6

（先访问 1，再访问它的一圈邻居 2、3，再访问 4、5、6）

代码：

const int N = 100005;
vector<int> g[N];
bool vis[N];

void bfs(int s) {
	queue<int> q;
	q.push(s);
	vis[s] = true;
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		cout << u << ' ';
		for (int v : g[u]) {
			if (!vis[v]) {
				vis[v] = true;
				q.push(v);
			}
		}
	}
}

💡 特点：用队列，先访问的先扩展，所以是"一层一层"往外走。BFS 找最短路（无权图）靠的就是这个性质。

3.3 DFS 和 BFS 对比

---