#ys1. 图的存储+搜索练习

图的存储+搜索练习

1. 三种存图方式

  • 邻接矩阵
  • 邻接表（vector）
  • 链式前向星

【选择题 1】 以下关于三种存图方式的描述，错误的是（　） {{ select(4) }}

  • 邻接矩阵用 a[u][v] 表示边
  • 邻接表只存储真实存在的边
  • 链式前向星使用 head[u] 存储顶点 u 的第一条出边编号
  • 三种存图方式都可以 O(1) 判断任意两点是否相连

2. 邻接矩阵

核心思想

用二维数组 a[u][v] 记录边：1 表示有边，0 表示无边。无向图矩阵对称。

【判断题 1】 对于无向图，若 a[3][5] = 1，则 a[5][3] 一定等于 1。（　） {{ select(2) }}

  • √
  • ×

【选择题 2】 在邻接矩阵的 DFS 中，遍历顶点 u 的邻点时，内层循环的写法是（　） {{ select(4) }}

  • for(int i=0; i<g[u].size(); i++)
  • for(int i=head[u]; i; i=edges[i].next)
  • for(int i=1; i<=n; i++)
  • for(int i=1; i<=m; i++)

【代码作用选择题 1】 观察以下邻接矩阵 DFS 的核心代码片段：

for (int i = 1; i <= n; i++) {
    if (vis[i]) continue;
    if (a[u][i]) {
        dfs(i);
    }
}

其中 if (a[u][i]) 这一行的作用是（　） {{ select(4) }}

  • 标记顶点 i 已被访问
  • 判断顶点 u 和顶点 i 之间是否存在边
  • 将顶点 i 从图中删除
  • 将顶点 i 加入队列等待遍历

【代码作用选择题 2】 在 DFS 函数开头，代码 vis[u] = 1; 的作用是（　） {{ select(4) }}

  • 将顶点 u 加入待访问队列
  • 标记顶点 u 已被访问，防止后续递归中重复遍历
  • 清空顶点 u 的所有邻接边
  • 输出顶点 u 的编号

完整可运行代码

#include<iostream>
using namespace std;

int a[1001][1001];
int n, m;
bool vis[1001];

void dfs(int u) {
    vis[u] = 1;
    cout << u << ' ';
    for (int i = 1; i <= n; i++) {
        if (vis[i]) continue;
        if (a[u][i]) {
            dfs(i);
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        a[u][v] = 1;
        a[v][u] = 1;
    }
    int start;
    cin >> start;
    dfs(start);
    return 0;
}

3. 邻接表（vector 版）

核心思想

每个顶点开一个 vector，只存储真实存在的邻点，大幅节省空间。

优缺点

  • 优点：空间最优、遍历效率高、代码简单不易错
  • 缺点：无法直接 O(1) 查询两点是否连边

【判断题 2】 邻接表中，顶点 u 的邻点存储在 g[u] 中，其顺序与输入时 push_back 的顺序一致。（　） {{ select(2) }}

  • √
  • ×

【选择题 3】 若要在邻接表中判断顶点 u 和 v 之间是否有边，以下做法可行的是（　） {{ select(4) }}

  • if (g[u][v])
  • 遍历 g[u] 查找是否存在 v
  • if (g[u].find(v) != g[u].end())
  • 以上都不对

【代码作用选择题 3】 观察以下邻接表 DFS 的核心代码片段：

for (int i = 0; i < (int)g[u].size(); i++) {
    int v = g[u][i];
    if (vis[v]) continue;
    dfs(v);
}

其中 if (vis[v]) continue; 这一行的作用是（　） {{ select(4) }}

  • 终止整个 DFS 程序，直接返回主函数
  • 如果邻点 v 已被访问过，则跳过本次循环，不再递归进入 v
  • 将 v 重新标记为未访问，以便下次重新遍历
  • 如果 v 未访问，则结束当前顶点的遍历

完整可运行代码

#include<bits/stdc++.h>
using namespace std;

vector<int> g[1001];
int n, m;
bool vis[1001];

void dfs(int u) {
    vis[u] = 1;
    cout << u << ' ';
    for (int i = 0; i < (int)g[u].size(); i++) {
        int v = g[u][i];
        if (vis[v]) continue;
        dfs(v);
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int start;
    cin >> start;
    dfs(start);
    return 0;
}

【程序填空题 2】 在邻接表的 DFS 中，for 循环的判断条件 i < (int)g[u].size() 中，(int) 强制转换的主要作用是（　）【此题为选择题，但保留在填空位置】 {{ select(4) }}

  • 将 size_t 转为 int，避免无符号整数与有符号整数比较时产生编译警告
  • 提高遍历速度，使循环更快
  • 确保 g[u].size() 的返回值一定正确
  • 将 vector 的大小强制减半

4. 链式前向星

核心思想

数组模拟链表，头插法存边。

  • edges[tot].to：边的终点
  • edges[tot].next：同起点的下一条边编号
  • head[u]：u 当前最新一条边的编号，0 代表无边

【判断题 3】 链式前向星中，head[u] 的初始值应为 0，表示顶点 u 当前没有任何边。（　） {{ select(2) }}

  • √
  • ×

【选择题 4】 执行以下 add 操作：

void add(int u, int v) {
    edges[++tot].to = v;
    edges[tot].next = head[u];
    head[u] = tot;
}

若当前 head[1] = 2，执行 add(1, 5) 后，新边 edges[3].next 的值是（　） {{ select(4) }}

  • 0
  • 2
  • 3
  • 5

【代码作用选择题 4】 在链式前向星的 add 函数中，代码行 edges[tot].next = head[u]; 的作用是（　） {{ select(4) }}

  • 将当前边的终点设置为 u
  • 将当前边指向顶点 u 原来的第一条边（头插法，形成链式结构）
  • 清空顶点 u 之前的所有边
  • 将当前边设置为顶点 u 的最后一条边

【代码作用选择题 5】 在链式前向星的 DFS 遍历中，for 循环语句：

for (int i = head[u]; i != 0; i = edges[i].next)

循环更新部分 i = edges[i].next 的作用是（　） {{ select(4) }}

  • 将 i 移动到顶点 u 的下一条出边的编号（沿链表向后遍历）
  • 将 i 直接跳转到当前边的终点
  • 将 i 重置为 0，强制结束循环
  • 将 i 自增 1，按数组下标顺序遍历

完整可运行代码

#include<bits/stdc++.h>
using namespace std;

struct Edge{
	int to,next;
}edges[200005];

int head[100005];
int tot = 0;

void add(int u,int v){
	edges[++tot].to = v;
	edges[tot].next = head[u];
	head[u] = tot;
}

bool vis[100005];

void dfs(int u){
	cout << u << " ";
	vis[u] = 1;
	for(int i=head[u]; i!=0; i=edges[i].next){
		int v = edges[i].to;
		if(vis[v]) continue;
		dfs(v);
	}
}

int main(){
	int n,m;
	cin >> n >> m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin >> u >> v;
		add(u,v);
		add(v,u); // 无向图双向建边
	}
	int start;
	cin >> start;
	dfs(start);
	return 0;
}

【程序填空题 3】 在链式前向星的 DFS 遍历中，若将 for 循环的终止条件 i != 0 误写为 i <= tot，最可能导致的问题是（　） {{ select(4) }}

  • 程序陷入死循环
  • 访问到未初始化的 edges 结构体，可能导致数组越界或逻辑错误
  • 漏掉顶点 u 的部分邻点
  • 程序仍然完全正确，只是多循环几次

5. DFS 通用模板（万能背诵版）

void dfs(int u) {
    vis[u] = true;        // 1. 标记已访问
    // 2. 处理当前点（输出、统计答案）
    for(遍历所有邻点 v){
        if(!vis[v]){
            dfs(v);      // 3. 递归深搜
        }
    }
}

三种存图「遍历邻点」标准写法对照

存图方式 遍历邻点核心代码
邻接矩阵 for(int v=1;v<=n;v++) if(a[u][v] && !vis[v])
邻接表 for(int i=0;i<(int)g[u].size();i++){int v=g[u][i];}
链式前向星 for(int i=head[u];i!=0;i=edges[i].next)

【判断题 4】 在 DFS 模板中，如果将 vis[u] = true; 写在递归调用 dfs(v) 的后面（即先递归再标记），会导致同一个顶点在本次 DFS 中被多次重复访问。（　） {{ select(2) }}

  • √
  • ×

【程序填空题 4（综合）】 请根据三种存图方式，补全以下 DFS 遍历邻点的代码片段（每空填一个表达式）：

存图方式 遍历代码（填一个空）
邻接矩阵 for(int v=1; v<=n; v++) { if( ____①____ && !vis[v]) dfs(v); }
邻接表 for(int i=0; i<g[u].size(); i++) { int v = g[u][i]; if(____②____) continue; dfs(v); }
链式前向星 for(int i=head[u]; i; i=____③____) { int v = edges[i].to; if(!vis[v]) dfs(v); }
{{ select(3) }}
  • ①a[u][v] ②vis[v] ③edges[i].next
  • ①vis[v] ②a[u][v] ③edges[i].next
  • ①a[u][v] ②edges[i].next ③vis[v]

7. 选图技巧

  • n ≤ 1000、要频繁判边 → 邻接矩阵
  • 普通题目、数据中等 → vector 邻接表
  • 数据量大、卡时间、高阶算法 → 链式前向星

【选择题 5】 以下场景中，选择邻接矩阵最合适的是（　） {{ select(4) }}

  • n=200000, m=500000，需要判断两点是否连通上万次
  • n=500, m=600，代码要尽量简单
  • n=500, m=100000，需要快速判断两点是否连通
  • n=10000, m=20000，内存限制严格

【判断题 5】 对于 n=100000, m=100000 的稀疏图，使用链式前向星存储比邻接矩阵更节省内存，且遍历更快。（　） {{ select(2) }}

  • √
  • ×
  1. Language
  2. 兼容模式
  3. 主题
  2. 练习让我快乐！
  3. Worker 0, 22ms
  4. Powered by Hydro v5.0.0 Community