4.2节后习题 - 图的存储与遍历
一、基础概念题
1. 邻接矩阵和邻接表的优缺点比较
答案与解析
邻接矩阵
优点：
- 直观，便于判断两顶点是否相邻，时间复杂度为O(1)
- 方便获取顶点的度，对于无向图，顶点v的度是第v行（或列）非零元素的个数，对于有向图，出度是第v行非零元素的个数，入度是第v列非零元素的个数
- 矩阵运算可用于图的一些算法，如弗洛伊德（Floyd）算法求最短路径
缺点：
- 存储空间大，对于有V个顶点的图，需要V²的空间，若为稀疏图会浪费大量空间
- 插入和删除边的操作时间复杂度高，为O(1)，但修改矩阵元素涉及到对矩阵的操作
适用场景：稠密图，即边数E接近V²的图；需要频繁判断顶点间是否相邻的场景；一些基于矩阵运算的图算法。
邻接表
优点：
- 节省空间，对于稀疏图，只存储存在的边，空间复杂度为O(V + E)
- 插入和删除边的操作相对简单，时间复杂度为O(1)（不考虑查找边的时间）
- 便于遍历每个顶点的邻接点，时间复杂度为O(d(v))，d(v)为顶点v的度
缺点：
- 判断两顶点是否相邻需要遍历顶点u的邻接表，时间复杂度为O(d(u))
- 获取顶点的度需要遍历邻接表统计邻接点个数，时间复杂度为O(d(v))
适用场景：稀疏图，即边数E远小于V²的图；需要频繁遍历顶点邻接点的场景。
2. 不同存储方式的时间复杂度
请填写以下操作在不同存储方式下的时间复杂度：
| 操作 | 邻接表 | 邻接矩阵 | 边集 | 链式前向星 |
|---|---|---|---|---|
| 判断顶点u和v是否邻接 | ||||
| 遍历顶点u的所有邻接点 | ||||
| 添加一条边u→v |
二、代码实现题
3. 邻接表的BFS遍历
题目：使用C++实现邻接表存储的无向图，并从顶点0出发进行BFS遍历，输出访问顺序。
- 输入示例：顶点数 V=4，边集为
({0,1}, {0,2}, {2,3}) - 输出示例：0 1 2 3
代码实现
vector<int> adj[100];
bool vis[100];
void bfs(int start) {
queue<int> q;
q.push(start);
vis[start] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
cout << u << " ";
for (int v : adj[u]) {
if (!vis[v]) {
q.push(v);
vis[v] = true;
}
}
}
}解析：首先定义邻接表adj存储无向图，vis数组记录顶点是否被访问。bfs函数实现广度优先遍历，使用队列q存储待访问的顶点。从起始顶点start开始，将其入队并标记为已访问，然后循环取出队列头部顶点，输出该顶点，遍历其邻接点，若邻接点未被访问则入队并标记为已访问。在main函数中添加边并初始化访问数组，最后调用bfs(0)从顶点0开始进行BFS遍历。
核心知识点：邻接表的存储方式；广度优先遍历（BFS）算法，利用队列实现逐层访问顶点；访问数组的使用，用于标记顶点是否已被访问。
4. 链式前向星的DFS遍历
题目：使用链式前向星存储有向图，并实现非递归（栈）的DFS遍历，从顶点0出发输出访问顺序。
- 输入示例：顶点数 V=3，边集为
({0,1}, {0,2}, {2,1}) - 输出示例：0 2 1（依赖遍历顺序）
代码实现
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
const int N = 100;
struct Edge {
int to;
int next;
};
Edge edge[N];
int head[N], cnt = 0;
bool vis[N];
// 添加边
void addEdge(int u, int v) {
edge[cnt].to = v;
edge[cnt].next = head[u];
head[u] = cnt++;
}
// 链式前向星DFS遍历（非递归，使用栈）
void dfs(int start) {
stack<int> st;
st.push(start);
vis[start] = true;
while (!st.empty()) {
int u = st.top();
st.pop();
cout << u << " ";
for (int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].to;
if (!vis[v]) {
st.push(v);
vis[v] = true;
}
}
}
}
int main() {
int V = 3;
// 初始化head数组
for (int i = 0; i < V; ++i) {
head[i] = -1;
}
// 添加边
addEdge(0, 1);
addEdge(0, 2);
addEdge(2, 1);
// 初始化访问数组
for (int i = 0; i < V; ++i) {
vis[i] = false;
}
dfs(0);
return 0;
}解析：定义结构体Edge存储边的信息，包括目标顶点to和指向下一条边的指针next。head数组存储每个顶点的第一条边在edge数组中的下标。addEdge函数用于添加边，将边信息存入edge数组并更新head数组。dfs函数实现链式前向星的非递归DFS遍历，使用栈st存储待访问的顶点。从起始顶点start开始，将其入栈并标记为已访问，然后循环取出栈顶顶点，输出该顶点，遍历以该顶点为起点的边链表，若目标顶点未被访问则入栈并标记为已访问。在main函数中初始化head数组，添加边并初始化访问数组，最后调用dfs(0)从顶点0开始进行DFS遍历。
核心知识点：链式前向星的存储方式；深度优先遍历（DFS）算法，利用栈实现非递归的DFS；结构体和数组的使用来实现链式前向星存储图；访问数组的使用，用于标记顶点是否已被访问。
三、综合应用题
5. 最短路径问题
题目：给定一个无权无向图（边权为1），使用邻接表存储，编写BFS算法求解从顶点 s 到顶点 t 的最短路径长度。若不可达返回-1。
输入示例：
V=5, E=6, edges=({0,1}, {0,2}, {1,3}, {2,3}, {2,4}, {3,4})- s=0, t=4
- 输出：3（路径0→2→4）
代码实现
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N = 100;
vector<int> adj[N];
bool vis[N];
int dist[N];
// BFS求最短路径
int bfs(int s, int t) {
queue<int> q;
q.push(s);
vis[s] = true;
dist[s] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (!vis[v]) {
q.push(v);
vis[v] = true;
dist[v] = dist[u] + 1;
if (v == t) {
return dist[v];
}
}
}
}
return -1;
}
int main() {
int V = 5, E = 6;
// 添加边
adj[0].push_back(1);
adj[1].push_back(0);
adj[0].push_back(2);
adj[2].push_back(0);
adj[1].push_back(3);
adj[3].push_back(1);
adj[2].push_back(3);
adj[3].push_back(2);
adj[2].push_back(4);
adj[4].push_back(2);
adj[3].push_back(4);
adj[4].push_back(3);
int s = 0, t = 4;
// 初始化访问数组和距离数组
for (int i = 0; i < V; ++i) {
vis[i] = false;
dist[i] = -1;
}
cout << bfs(s, t) << endl;
return 0;
}解析：定义邻接表adj存储无向图，vis数组记录顶点是否被访问，dist数组记录从起始顶点到其他顶点的最短距离。bfs函数实现BFS算法求最短路径，使用队列q存储待访问的顶点。从起始顶点s开始，将其入队并标记为已访问，距离设为0，然后循环取出队列头部顶点，遍历其邻接点，若邻接点未被访问则入队并标记为已访问，更新其距离为当前顶点距离加1，若邻接点为目标顶点t，则返回其距离。若遍历完所有顶点仍未找到目标顶点，则返回-1。在main函数中添加边并初始化访问数组和距离数组，最后调用bfs(s, t)求解从顶点s到顶点t的最短路径长度。
核心知识点：邻接表的存储方式；广度优先遍历（BFS）算法，利用队列实现逐层访问顶点；访问数组和距离数组的使用，访问数组用于标记顶点是否已被访问，距离数组用于记录从起始顶点到其他顶点的最短距离。
6. 图的连通分量计数
题目：使用邻接矩阵存储图，通过DFS遍历统计图中的连通分量数量。
输入示例：
V=5, edges=({0,1}, {1,2}, {3,4})// 图分为两个连通分量- 输出：2
代码实现
#include <iostream>
#include <vector>
using namespace std;
const int N = 100;
int adjMatrix[N][N];
bool vis[N];
// DFS遍历
void dfs(int u, int V) {
vis[u] = true;
for (int v = 0; v < V; ++v) {
if (adjMatrix[u][v] && !vis[v]) {
dfs(v, V);
}
}
}
// 统计连通分量数量
int countConnectedComponents(int V) {
int count = 0;
for (int i = 0; i < V; ++i) {
if (!vis[i]) {
count++;
dfs(i, V);
}
}
return count;
}
int main() {
int V = 5;
// 初始化邻接矩阵
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
adjMatrix[i][j] = 0;
}
}
// 添加边到邻接矩阵
adjMatrix[0][1] = 1;
adjMatrix[1][0] = 1;
adjMatrix[1][2] = 1;
adjMatrix[2][1] = 1;
adjMatrix[3][4] = 1;
adjMatrix[4][3] = 1;
// 初始化访问数组
for (int i = 0; i < V; ++i) {
vis[i] = false;
}
cout << countConnectedComponents(V) << endl;
return 0;
}解析：定义邻接矩阵adjMatrix存储图，vis数组记录顶点是否被访问。dfs函数实现深度优先遍历，从顶点u开始，标记其为已访问，然后遍历邻接矩阵中与顶点u相邻且未被访问的顶点，递归调用dfs进行遍历。countConnectedComponents函数统计连通分量数量，遍历所有顶点，若顶点未被访问，则连通分量数量加1，并调用dfs进行遍历。在main函数中添加边到邻接矩阵并初始化访问数组，最后调用countConnectedComponents(V)统计连通分量数量。
核心知识点：邻接矩阵的存储方式；深度优先遍历（DFS）算法，递归实现对图的遍历；访问数组的使用，用于标记顶点是否已被访问；连通分量的概念，通过DFS遍历统计图中连通分量的数量。
四、进阶思考题
7. 存储方式选择与优化
题目：假设需要频繁进行两种操作：(1) 判断任意两顶点是否邻接；(2) 遍历某个顶点的所有邻接点。 若图的顶点数 V=1000，边数 E=3000，你会选择哪种存储方式？为什么？如果边数变为 E=800000，选择会变化吗？
答案与解析
当V = 1000，E = 3000时：
为稀疏图（因为边数E远小于V² = 1000×1000 = 1000000），应选择邻接表或链式前向星存储。
理由：
空间效率：邻接矩阵存储需要V² = 1000000的空间，会浪费大量空间，而邻接表和链式前向星的空间复杂度为O(V + E) = O(1000 + 3000) = O(4000)，空间效率高。
操作效率分析：
- 对于操作(1)判断任意两顶点是否邻接：邻接表时间复杂度为O(d(u))，链式前向星为O(d(u))，虽然不如邻接矩阵的O(1)，但由于是稀疏图，平均度数d(u) = 2E/V = 2×3000/1000 = 6较小，实际判断时间可接受
- 对于操作(2)遍历某个顶点的所有邻接点：邻接表和链式前向星时间复杂度为O(d(u))，邻接矩阵为O(V)，邻接表和链式前向星更优
当V = 1000，E = 800000时：
为稠密图（因为边数E接近V² = 1000×1000 = 1000000），应选择邻接矩阵存储。
理由：
操作效率优势：对于操作(1)判断任意两顶点是否邻接，邻接矩阵时间复杂度为O(1)，邻接表和链式前向星为O(d(u))，稠密图中平均度数d(u) = 2E/V = 2×800000/1000 = 1600较大，邻接矩阵在判断顶点邻接关系上效率更高
实现便利性：对于操作(2)遍历某个顶点的所有邻接点，邻接矩阵时间复杂度为O(V)，邻接表和链式前向星为O(d(u))，由于是稠密图，O(V)和O(d(u))相差不大，且邻接矩阵更便于操作和实现
核心知识点：图的存储方式（邻接矩阵、邻接表、链式前向星）及其优缺点；稀疏图和稠密图的概念；根据图的特点（顶点数、边数）和操作需求（判断顶点邻接关系、遍历邻接点）选择合适的存储方式；时间复杂度和空间复杂度的分析，用于评估不同存储方式在不同操作下的效率。