【图论】图的概念、存储和遍历学习笔记

图的概念

从数据结构的角度看，图可以看作一个多对多的数据存储结构。而结合图论算法，图就可以成为很多问题的载体。图论是数据结构与算法结合的产物。

OI Wiki 上给出的图相关概念比较全面，但是因为 OI 是民科各个地方的一些定义都不太一样，所以作大概了解即可。

图的存储

图的存储常用下面几种方式。

边目录。通常情况下，题目数据都是直接给出边的起点，终点和边权（如果有），则可以直接存储这些信息来存图。

邻接矩阵。用一个二维数组（矩阵） $g[n][n]$ 来存图。在带权图中， $g[u][v]=x$ 表示从点 $u$ 到点 $v$ 有一条权为 $x$ 的图， $g[u][v]=-inf$ 表示点 $u$ 到点 $v$ 没有边。在无权图中， $g[u][v]$ 表示点 $u$ 到点 $v$ 是否有边。

邻接表。将所有边按点归类存储。用链表实现的邻接表也叫链式前向星。

下面给出存图的代码：

洛谷 B3643 图的存储（参考代码）

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

int n, m;
int g1[1005][1005];
vector<int> g2[1005];

signed main() {
    ios::sync_with_stdio(0);
    #ifndef ONLINE_JUDGE
    clock_t t0 = clock();
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
    #endif

    cin >> n >> m;
    for (int i = 1;i <= m;i++) {
        int u, v;
        cin >> u >> v;
        g1[u][v] = g1[v][u] = 1;
        g2[u].push_back(v);
        g2[v].push_back(u);
    }
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            cout << g1[i][j] << ' ';
        }
        cout << endl;
    }

    for (int i = 1;i <= n;i++) {
        sort(g2[i].begin(), g2[i].end());
        cout << g2[i].size() << ' ';
        for (int& j : g2[i]) cout << j << ' ';
        cout << endl;
    }

    // Don't stop. Don't hide. Follow the light, and you'll find tomorrow. 

    #ifndef ONLINE_JUDGE
    cerr << "Time used:" << clock() - t0 << "ms" << endl;
    #endif
    return 0;
}

图的遍历

不重复、不遗漏访问图上每个点，称为图的遍历。

遍历图时通常使用邻接表存储图。遍历图的方式通常有两种：深度优先遍历和广度优先遍历，分别用栈（递归）和队列实现。

下面是两种遍历方式的代码实现：

洛谷 P5318 查找文献（参考代码）

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

const int N = 1e5 + 5;

vector<int> g[N];

int n, m;

bool vis[N];

int dfs(int p) {
    vis[p] = 1;
    cout << p << ' ';
    for (int& i : g[p]) {
        if (vis[i]) continue;
        dfs(i);
    }
}

void bfs() {
    queue<int> q;
    q.push(1);
    vis[1] = 1;
    while (!q.empty()) {
        int p = q.front(); q.pop();
        cout << p << ' ';
        for (int& i : g[p]) {
            if (vis[i]) continue;
            vis[i] = 1;
            q.push(i);
        }
    }
}

signed main() {
    ios::sync_with_stdio(0);
    #ifndef ONLINE_JUDGE
    clock_t t0 = clock();
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
    #endif

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

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

    dfs(1);

    cout << endl;

    memset(vis, 0, sizeof(vis));

    bfs();

    #ifndef ONLINE_JUDGE
    cerr << "Time used:" << clock() - t0 << "ms" << endl;
    #endif
    return 0;
}

例题

洛谷 P3916 图的遍历

从一个点出发对图进行深度优先遍历，时间复杂度为 $O(N + M)$ 。

若从每个点开始进行一次遍历，时间复杂度无法通过此题。

正难则反。考虑编号大的点能从哪些点到达。对原图建立反图，从节点大小由大到小遍历，找出这个点可以从哪些点到达，则这些点能到达的最大点是这个点。

参考代码：

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

const int N = 1e5 + 5;

vector<int> g[N];

int n, m;

int ans[N];

void dfs(int p, int u) { // 可以到达点 u 的点
    ans[p] = max(ans[p], u);
    for (int& i : g[p]) {
        if (ans[i]) continue;
        dfs(i, u);
    }
}

signed main() {
    ios::sync_with_stdio(0);
    #ifndef ONLINE_JUDGE
    clock_t t0 = clock();
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
    #endif

    cin >> n >> m;
    for (int i = 1;i <= m;i++) {
        int u, v;
        cin >> u >> v;
        g[v].push_back(u); // 建立反图
    }

    for (int i = n;i > 0;i--) dfs(i, i);

    for (int i = 1;i <= n;i++) cout << ans[i] << ' ';

    #ifndef ONLINE_JUDGE
    cerr << "Time used:" << clock() - t0 << "ms" << endl;
    #endif
    return 0;
}

P1113 杂务

对原关系建立一个有向图，每个点建立指向必须完成他才能进行的任务，然后从对图进行 dfs 就可以求出完成每个点及其之后杂物的最少时间。

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

const int N = 1e4 + 5;

vector<int> g[N];

int n, t[N];

int d[N];

int dfs(int x) {
    if (d[x]) return d[x];
    for (int& v : g[x]) d[x] = max(d[x], dfs(v));
    d[x] += t[x];
    return d[x];
}

signed main() {
    ios::sync_with_stdio(0);
    #ifdef DEBUG
    clock_t t0 = clock();
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
    #endif

    cin >> n;
    for (int i = 1;i <= n;i++) {
        int u, v;
        cin >> u >> t[i];
        while (cin >> v, v) {
            g[v].push_back(u);
        }
    }

    int ans = 0;
    for (int i = 1;i <= n;i++) {
        ans = max(ans, dfs(i));
    }

    cout << ans << endl;

    #ifdef DEBUG
    cerr << "Time used:" << clock() - t0 << "ms" << endl;
    #endif
    return 0;
}

P4017 最大食物链计数

对原图建立反图，用记忆化搜索求出到达每个点的食物链数量，然后将所有终点的数量相加得到答案。

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

const int N = 5005, M = 5e5 + 5, mod = 80112002;

int in[N], out[N];

int n, m;

vector<int> g[N];

int f[N];

int dfs(int x) {
    if (f[x]) return f[x];
    int ans = 0;
    for (int& v : g[x]) {
        ans = (ans + dfs(v)) % mod;
    }
    return f[x] = ans;
}

signed main() {
    ios::sync_with_stdio(0);
    #ifdef DEBUG
    clock_t t0 = clock();
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
    #endif

    cin >> n >> m;
    for (int i = 1, u, v;i <= m;i++) {
        cin >> u >> v;
        out[u]++, in[v]++;
        g[v].push_back(u);
    }

    for (int i = 1;i <= n;i++) {
        if (in[i] == 0)f[i] = 1;
    }
    for (int i = 1;i <= n;i++) dfs(i);
    int ans = 0;
    for (int i = 1;i <= n;i++) if (out[i] == 0) ans = (ans + f[i]) % mod;

    cout << ans << endl;

    #ifdef DEBUG
    cerr << "Time used:" << clock() - t0 << "ms" << endl;
    #endif
    return 0;
}

拓展阅读 && 参考资料 && 推荐题目

图论部分简介 - OI Wiki
《深入浅出程序设计竞赛（基础篇）》第 18 章图的基本应用
《算法竞赛进阶指南》 0x21 树和图的遍历

【图论】图的概念、存储和遍历 学习笔记