图的存储与遍历

16 Nov 2024

1. 图是什么

图由顶点和边组成。顶点可以表示地点、人物或任务；边表示两个顶点之间的关系。边有方向时是有向图，例如 1 → 2 不代表可以从 2 回到 1；没有方向时是无向图，一条边 1 - 2 可以双向走。

在对图进行 DFS 或 BFS 之前，先要确定如何保存每个点相邻的顶点。

2. 两种常见存图方式

邻接矩阵使用一个二维数组 edge。例如 edge[x][y] = 1 表示 x 到 y 有一条边。它判断两点是否直接相连很方便，但需要 O(n²) 的空间，适合顶点数较少或边很多的图。

int edge[N][N];
edge[x][y] = 1;

邻接表为每个顶点维护一个列表。graph[x] 中保存从 x 能直接到达的所有顶点。它只保存实际存在的边，空间复杂度为 O(n + m)，其中 n 是顶点数，m 是边数，因此更适合大多数稀疏图。

vector<int> graph[N];
graph[x].push_back(y);

如果边是无向的，需要同时加入两个方向：graph[x].push_back(y) 和 graph[y].push_back(x)。

3. 例题：洛谷 P5318 查找文献

题目给出一个有向图，要求从 1 号顶点开始，分别按 DFS 和 BFS 的顺序输出所有能访问到的顶点。为了让遍历顺序稳定，需要先对每个顶点的邻接表排序。

DFS 会沿着当前边尽可能向下访问；BFS 使用队列，优先访问距离起点更近的顶点。两种遍历都要用 visited 数组标记已访问的顶点，防止在有环的图中重复搜索。

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

const int N = 100000 + 10;
vector<int> graph[N];
bool visited[N];
int n, m;

void dfs(int u) {
    visited[u] = true;
    cout << u << ' ';

    for (int v : graph[u]) {
        if (!visited[v]) {
            dfs(v);
        }
    }
}

void bfs(int start) {
    memset(visited, false, sizeof visited);
    queue<int> q;
    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << ' ';

        for (int v : graph[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

int main() {
    cin >> n >> m;
    while (m--) {
        int x, y;
        cin >> x >> y;
        graph[x].push_back(y);
    }

    for (int i = 1; i <= n; i++) {
        sort(graph[i].begin(), graph[i].end());
    }

    dfs(1);
    cout << '\n';
    bfs(1);
    return 0;
}

例如，边为 1 → 2、1 → 3、2 → 4、3 → 4 时，DFS 的输出顺序是 1 2 4 3，而 BFS 的输出顺序是 1 2 3 4。

使用邻接表时，每个顶点和每条边在一次遍历中最多被处理一次，所以 DFS 和 BFS 的时间复杂度都是 O(n + m)。图题的关键通常不是先选 DFS 还是 BFS，而是先确认边是否有向、如何存储邻接关系，以及何时标记顶点已经访问过。

图的存储与遍历

Related Posts