图的概念、存储方式和遍历

一、 图的核心概念

1. 基础定义

• 节点（顶点）：表示研究对象（如迷宫、加工站、电脑），编号通常为1~n（信奥题首选，避免下标0的额外转换）。
• 边：表示节点间的关系，分为两种：
  • 无向边：双向通行（如电脑数据线、无向图连通分量），记为u-v，题目中常描述为“可以往返”。
  • 有向边：单向通行（如参考文献引用、传送带），记为u→v，题目中常描述为“从u到v”。
• 特殊结构：
  • 树：无向图的特殊情况，n个节点n-1条边，且连通（无环），如牛奶加工厂的原始结构。
  • 连通分量：无向图中相互连通的节点集合（相互可达），如“至少输入几台电脑”问题的核心就是统计连通分量个数。
  • 公共可达节点：有向图中，所有其他节点都能到达的节点（如牛奶加工厂问题的目标）。

2. 高频衍生概念

• 度：节点的边数关联数
  • 无向图：度数=邻接节点数（如邻接表输出问题中，节点的度数就是邻接表大小）。
  • 有向图：入度（指向该节点的边数）、出度（该节点指出去的边数）（如迷宫可达性统计问题，行对应出度、列对应入度）。
• 可达性：从节点u出发，能否通过一系列边到达节点v（DFS/BFS的核心应用场景）。
• 遍历要求：有序遍历（优先访问小编号节点，需对邻接表排序），无重复、无遗漏（依赖访问标记数组）。

二、 图的两种核心存储方式（信奥必掌握）

信奥题中，图的存储方式仅需掌握邻接矩阵和邻接表，两者各有适用场景，需根据数据范围选择。

1. 邻接矩阵

（1） 存储原理

用n×n的二维数组mat[n+1][n+1]（节点1~n）存储，mat[u][v]的值表示节点u和v的关系：

• 无向图：mat[u][v] = mat[v][u] = 1（有边），0（无边），矩阵为对称矩阵。
• 有向图：mat[u][v] = 1（有u→v的边），0（无边），矩阵无需对称。
• 特殊：节点自身可达（如迷宫问题），mat[i][i] = 1。

（2） 模版代码（精简版）

const int MAXN = 1001; // 适用于n≤1000的场景
int mat[MAXN][MAXN] = {0}; // 初始化全0

// 输入无向边
void input_undirected(int u, int v) {
    mat[u][v] = 1;
    mat[v][u] = 1;
}

// 输入有向边
void input_directed(int u, int v) {
    mat[u][v] = 1;
}

（3） 适用场景 & 注意事项

• 适用：节点数n≤1000（二维数组空间为n²，n=1000时为1e6，符合内存限制），如迷宫可达性统计、邻接矩阵输出问题。
• 优点：实现简单，查询两点间是否有边效率高（O(1)），适合小规模数据。
• 缺点：空间利用率低，稀疏图（边数m远小于n²）会浪费大量空间，无法应对n≥1e4的场景（如连通分量统计问题，n=1e4时空间为1e8，超出内存限制）。
• 注意：信奥题中，邻接矩阵通常初始化为0，无需手动初始化所有元素（C++中全局数组默认全0）。

2. 邻接表

（1） 存储原理

用向量数组vector<int> g[n+1]（节点1~n）存储，g[u]是一个向量，存储所有与u直接相连的节点（无向图）或u指出去的节点（有向图）。

• 无向图：g[u].push_back(v)且g[v].push_back(u)（双向填充）。
• 有向图：g[u].push_back(v)（单向填充，仅存出边）。

（2） 模版代码（精简版，信奥首选）

const int MAXN = 100001; // 适用于n≤1e5的场景
vector<int> g[MAXN]; // 邻接表，全局定义避免栈溢出

// 输入无向边（兼容重边、自环，无需额外处理）
void input_undirected(int u, int v) {
    g[u].push_back(v);
    g[v].push_back(u);
}

// 输入有向边（仅存出边）
void input_directed(int u, int v) {
    g[u].push_back(v);
}

// 有序遍历预处理：对每个节点的邻接表升序排序（满足优先访问小编号）
void sort_graph(int n) {
    for (int i = 1; i <= n; ++i) {
        sort(g[i].begin(), g[i].end());
    }
}

（3） 适用场景 & 注意事项

• 适用：节点数n≤1e5、边数m≤2e5的大规模场景（空间为O(n+m)），如DFS/BFS有序遍历、连通分量统计、牛奶加工厂问题。
• 优点：空间利用率高，适合稀疏图，是信奥大题的首选存储方式。
• 缺点：查询两点间是否有边效率低（O(k)，k为u的邻接节点数）。
• 关键注意事项：
  1. 有序遍历要求：需对每个节点的邻接表排序（sort()），DFS反向遍历、BFS正序遍历，即可优先访问小编号节点。
  2. 避免栈溢出：邻接表需全局定义或动态分配，不可在主函数内定义（n=1e5时，局部向量数组会超出栈内存）。
  3. 重边/自环处理：无需手动去重，访问标记数组会避免重复遍历，不影响结果且节省时间。

三、 图的两种核心遍历方法（信奥必背模版）

图的遍历是解决可达性、连通分量、路径统计等问题的基础，信奥中仅需掌握深度优先搜索（DFS）和广度优先搜索（BFS），两者均需依赖访问标记数组避免重复遍历。

1. 深度优先搜索（DFS）

（1） 核心思想

“先深入，后回溯”，从起始节点出发，不断访问邻接节点，直到无法深入，再回溯到上一个节点，继续访问未遍历的邻接节点（递归实现最简洁，适合信奥解题）。

（2） 模版代码（精简版，有序遍历，全局变量版）

const int MAXN = 100001;
vector<int> g[MAXN];
bool vis[MAXN] = {0}; // 访问标记数组，初始全0
vector<int> res; // 存储遍历结果（可选，也可直接输出）

// DFS核心函数（u为当前节点，有序遍历：反向遍历升序邻接表）
void dfs(int u) {
    vis[u] = true; // 标记已访问
    res.push_back(u); // 存储结果（或直接cout << u << " "）
    
    // 反向遍历升序邻接表，优先访问小编号节点
    for (auto it = g[u].rbegin(); it != g[u].rend(); ++it) {
        int v = *it;
        if (!vis[v]) { // 未访问的节点才递归深入
            dfs(v);
        }
    }
}

// DFS调用流程（起始节点为start，n为总节点数）
void dfs_call(int start, int n) {
    memset(vis, 0, sizeof(vis)); // 重置访问标记（多组数据/多次遍历需调用）
    res.clear(); // 清空结果数组
    dfs(start); // 执行DFS
    
    // 输出结果（可选）
    for (int i = 0; i < res.size(); ++i) {
        if (i > 0) cout << " ";
        cout << res[i];
    }
    cout << endl;
}

（3） 适用场景 & 注意事项

• 适用：连通分量统计、可达性验证、路径搜索（如牛奶加工厂的节点验证），数据量适中的场景。
• 优点：代码简洁，递归实现无需额外数据结构，容易理解和书写。
• 关键注意事项：
  1. 访问标记重置：多次遍历（如验证多个节点）时，需用memset(vis, 0, sizeof(vis))重置标记数组（仅全局数组可用memset）。
  2. 递归深度限制：n≤1e4时可能出现栈溢出（递归深度过深），此时需改用非递归实现（信奥中n≤1e3时递归完全安全，n≥1e4优先选BFS）。
  3. 有序遍历：邻接表升序排序后，用反向迭代器（rbegin()/rend()）遍历，实现优先访问小编号节点。

2. 广度优先搜索（BFS）

（1） 核心思想

“逐层遍历，先广后深”，从起始节点出发，先访问所有邻接节点（第一层），再依次访问每个邻接节点的邻接节点（第二层），以此类推（依赖队列实现，无递归）。

（2） 模版代码（精简版，有序遍历，全局变量版，贴合信奥解题习惯）

const int MAXN = 100001;
vector<int> g[MAXN];
bool vis[MAXN] = {0}; // 访问标记数组
vector<int> res; // 存储遍历结果（可选）
queue<int> q; // BFS核心队列

// BFS核心函数（start为起始节点，有序遍历：正序遍历升序邻接表）
void bfs(int start) {
    // 初始化队列
    q.push(start);
    vis[start] = true;
    
    while (!q.empty()) {
        int fro = q.front(); // 取出队首节点
        q.pop();
        res.push_back(fro); // 存储结果（出队时存储，符合信奥模版）
        
        // 正序遍历升序邻接表，优先访问小编号节点
        for (int i = 0; i < g[fro].size(); ++i) {
            int v = g[fro][i];
            if (!vis[v]) { // 未访问的节点入队并标记
                q.push(v);
                vis[v] = true;
            }
        }
    }
}

// BFS调用流程
void bfs_call(int start, int n) {
    memset(vis, 0, sizeof(vis)); // 重置访问标记
    res.clear(); // 清空结果数组
    while (!q.empty()) q.pop(); // 清空队列（多次调用需注意）
    bfs(start); // 执行BFS
    
    // 输出结果（可选）
    for (int i = 0; i < res.size(); ++i) {
        if (i > 0) cout << " ";
        cout << res[i];
    }
    cout << endl;
}

（3） 适用场景 & 注意事项

• 适用：大规模数据遍历（无栈溢出风险）、层次遍历问题、最短路径问题（无权图），如n≤1e5的连通分量统计。
• 优点：无递归栈溢出风险，适合大规模数据，层次清晰。
• 关键注意事项：
  1. 队列清空：多次调用BFS时，需手动清空队列（while (!q.empty()) q.pop()），避免残留数据影响结果。
  2. 标记时机：入队时标记访问（vis[v] = true），避免同一节点多次入队，提升效率（不可出队时标记，会导致重复入队）。
  3. 有序遍历：邻接表升序排序后，正序下标遍历，即可优先访问小编号节点。

四、 信奥解题高频模版汇总

1. 邻接矩阵/邻接表输出问题

• 核心：无向图双向填充，邻接表排序后输出度数和邻接节点。
• 注意：邻接矩阵输出避免末尾多余空格，邻接表排序保证有序。

2. 连通分量统计问题（无向图）

• 核心：遍历所有节点，未访问节点即为新连通分量，用DFS/BFS标记该分量所有节点。
• 模版代码（精简版）：

int count_connected(int n) {
    int ans = 0;
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) {
            ans++;
            dfs(i); // 或bfs(i)
        }
    }
    return ans;
}

3. 公共可达节点验证问题（有向图）

• 核心：从1~n遍历节点，验证每个节点是否被所有其他节点可达（双重循环：外层遍历目标节点，内层遍历所有起始节点）。
• 关键：保证最小性，找到第一个满足条件的节点直接输出。

4. 大规模数据输入输出优化

• 核心：关闭C++输入输出同步，避免超时（必加，尤其是n≥1e4、m≥1e5的场景）。
• 模版代码：

ios::sync_with_stdio(false);
cin.tie(nullptr);

五、 信奥解题关键注意事项

1. 节点编号：优先使用1~n编号，与题目输入一致，避免下标0的额外转换，减少错误。
2. 数据类型：结果可能溢出时，需用long long（如路径计数问题），避免int溢出导致答案错误。
3. 访问标记数组：
   • 全局定义：方便用memset重置，且避免栈溢出。
   • 分工明确：多次遍历（如DFS和BFS）时，可使用两个标记数组（vis1、vis2），避免反复重置，提升效率。
4. 有序遍历：邻接表必须排序，DFS反向遍历、BFS正序遍历，是满足“优先访问小编号”的唯一简洁方式。
5. 边界条件：
   • n=0：无节点，直接输出0（如连通分量统计问题）。
   • 自环/重边：无需额外处理，访问标记会自动规避，不影响结果。
6. 时间复杂度：
   • 邻接矩阵遍历：O(n²)，适用于n≤1000。
   • 邻接表遍历：O(n+m)，适用于n≤1e5、m≤2e5。
   • 有序遍历：额外增加O(m log k)（k为每个节点的邻接节点数），完全满足信奥时限要求。

六、 总结

1. 图的存储：小规模用邻接矩阵，大规模用邻接表，邻接表是信奥大题的首选。
2. 图的遍历：DFS简洁，BFS适合大规模数据，两者均需掌握，且能灵活切换。
3. 信奥解题核心：将问题转化为图的遍历/连通性/可达性问题，套用模版即可解决大部分题目。
4. 避坑关键：节点编号、访问标记、有序遍历、数据类型，这四点是减少错误的核心。

掌握以上内容，即可应对信奥中所有图的基础题型，为复杂题型（如最短路径、最小生成树）打下坚实基础。