图及相关算法 · 数据结构与算法 02

关键字DFSBFS连通块连通图拓扑顺序欧拉道路欧拉回路最短路环路对偶图

摘要 —— 本文以算法竞赛的风格对图的相关操作代码进行分析。内容涉及图的深度优先遍历(求连通块、求拓扑排序、求欧拉回路)和广度优先遍历(求最短路径)。本文重点解析了如何将一个问题化归为图问题。

树和图是十分重要的数据结构。在树和图上的操作(如层序遍历、深度优先遍历、寻找最短路、给出拓扑排序、判断是否连通等)在大型工程项目中频繁出现。在前一篇文章中我们分析了树和二叉树的建立、BFS 和 DFS。本文将会以同样的风格对图的相关操作代码进行分析。

图(graph)描述的是一些个体之间的关系,这些个体之间既不是前驱后继的顺序关系,也不是祖先后代的层次关系,而是错综复杂的网络关系。

1 图上的常见问题

1.1 深度优先遍历

和树一样,图上也有深度优先遍历(DFS),并且也用递归来实现。最典型的、图上的 DFS 的应用案例是「求连通块」。


例题 1:油田(Oil deposits, UVa 572)

输入一个 $m$ 行 $n$ 列的字符矩阵,统计字符 @ 组成了多少个八连块。如果两个字符 @ 所在的格子相邻(横、竖或者对角线方向),就说它们属于同一个八连块。

样例输入:
5 5
****@
*@@*@
*@**@
@@@*@
@@**@

样例输出:2


如果我们把 @ 看成节点,相邻的 @ 看成节点之间的无向边,则本题就是要找到输入中的连通图的个数。对于输入的二维字符数组中的任意一个位置 (r,c),如果这个位置存放的是 @ 且没有被访问过,则它属于某个连通块。但是,它属于哪一个连通块呢?因此,我们需要给连通块编号。假设这个元素属于连通块 $x$,则我们递归探索它周遭的 8 个位置,只要这些位置没有被访问过且存放的是 @,那么它们也属于连通块 $x$。否则,直接退出,返回到调用者。

基于以上分析,我们可以写出如下代码:

const int maxn = 100 + 5;
char arr[maxn][maxn];       // 存放读入的二维数组
int m, n;                   // 字符矩阵的真实大小

int idx[maxn][maxn];        // 存放每个位置的元素所属的连通图的编号

void dfs(int r, int c, int cnt) {
    if (r < 0 || r >= m || c < 0 || c >= n) return;     // 出界
    if (idx[r][c] != 0 || arr[r][c] != '@') return;     // 已被探索或不是 @
    idx[r][c] = cnt;
    for (int dr = -1; dr <= 1; dr++) {
        for (int dc = -1; dc <= 1; dc++) {
            if (!(dr == 0 && dc == 0)) {
                dfs(r + dr, c + dc, cnt);               // 递归
            }
        }
    }
}

我们在主函数中启动对 dfs() 的调用:

int main() {
    // do sth...
    int cnt = 0;
    memset(idx, 0, sizeof(idx));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (arr[i][j] == '@' && idx[i][j] == 0) {
                dfs(i, j, ++cnt);
            }
        }
    }
    // do sth...
}

主函数中调用 dfs() 的这一行被执行的次数就是连通块的个数。 完整代码请参见 aoapc/ch06/e6-12 这份代码极为重要,必须要彻底掌握。

1.2 广度优先遍历

和树一样,图上也有广度优先遍历(BFS),也借助队列来实现。 在二叉树的 BFS 中,节点的访问顺序恰好是它们到根节点距离从小到大的顺序。 类似地, 图上的 BFS 可以用于求出最短路径。

考虑如下问题:给出一个二维单元格组成的网格,每个单元格要么是空地(用 1 来表示),要么是障碍物(用 0)来表示,给定起点和终点,如何求出从起点到终点的最短路径?假设起点在左上角,则我们从左上角开始遍历迷宫,逐步计算出它到每一个节点的最短距离,结果如图 1 所示。



图 1 从左上角出发到各个单元格的最短距离。

我们仍然借助队列来实现:

const int maxn = 200 + 5;
int arr[maxn][maxn];            // 存放迷宫
int dis[maxn][maxn];            // 存放各单元格到起点的最短距离
int c[maxn][maxn];              // 存放 BFS 树中各个节点的编号
int m, n;                       // 迷宫大小

struct Node {
    int x, y;
    Node(int x = 0, int y = 0) : x(x), y(y) {}
};

Node parent[maxn][maxn];

// 四个遍历方向
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

void bfs() {
    queue<Node> q;
    memset(dis, -1, sizeof(dis));
    memset(c, 0, sizeof(c));
    int cnt = 1;

    Node u(0, 0);               // 起点
    dis[0][0] = 0;
    c[0][0] = cnt;
    q.push(u);
    while (!q.empty()) {
        Node v = q.front();
        q.pop();
        int i = v.x, j = v.y;
        // 探索周遭的四个单元格
        for (int k = 0; k < 4; k++) {
            int i2 = v.x + dr[k], j2 = v.y + dc[k];
            // 这个单元格位置合法、不是障碍物且没有被访问过
            if (i2 >= 0 && i2 < m && j2 >= 0 && j2 < n && arr[i2][j2] == 1 && dis[i2][j2] < 0) {
                dis[i2][j2] = dis[i][j] + 1;        // 更新最短距离
                parent[i2][j2] = v;                 // 设定指向父亲的指针
                c[i2][j2] = ++cnt;                  // 设定本节点的编号
                q.push(Node(i2, j2));
            }
        }
    }
}

在上面的代码中,我们用二维数组 parent 记录每个单元格(视为一个节点)的「从起点到它的最短路径」中的父节点。二维数组 c 则记录了扩展顺序。如图 2 所示,如果我们把箭头视为「指向父亲的指针」,则这些单元格就变成了一棵树,我们称之为最短路树(a.k.a. BFS 树)。



图 2 扩展顺序和父亲指针。

我们将这棵 BFS 树展开,如图 3 所示。



图 3 BFS 树。

最后,我们给出起点到任意点 $(x,y)$ 的最短路径的输出函数。在这个函数中,我们用 vector 保存最短路径途径的节点,然后逆序输出。

// 追溯从初始节点到目标节点 Node(x,y) 的最短路径
// 用 vector 保存路径并且倒序输出
void print_path(Node u) {
    vector<Node> path;
    for (;;) {
        path.push_back(u);
        if (dis[u.x][u.y] == 0) break;          // 到达起点
        u = parent[u.x][u.y];                   // 找到父亲节点
    }
    for (int i = path.size() - 1; i >= 0; i--) {
        printf("(%d,%d)", path[i].x, path[i].y);
    }
    printf("\n");
}

完整代码请参见 aoapc/ch06/c6-14。大多数「在迷宫中寻找最短路径」问题的求解方法和上面的代码一致。直接的扩展例题有

在第一题和第二题中,我们需要自定义每一步(方向、步长);在第一题和第三题中,vis 矩阵需要增加一个维度,因为这两道题中,每经过一步所抵达的新状态仅仅用坐标 $(x,y)$ 来描述是不够的。这三题的求解代码请分别参见 aoapc/ch06/e6-14aoapc/ch06/p6-4aoapc/ch06/p6-5

1.3 拓扑排序

对于一个有向图,如果我们将每个节点进行排序,使得每一条有向边 $(u,v)$ 对应的节点 $u$ 都排在节点 $v$ 的前面,则称这个排序为 拓扑排序 。显然,如果图中存在环路,则不存在拓扑排序;反之则存在。我们将不存在环路的有向图称为 有向无环图 (DAG)。 对于一个给定的 DAG,拓扑排序可以有多个。对于图 4 所示的 DAG,「1 5 4 6 2 3」、「1 4 6 5 2 3」、「1 4 6 2 5 3」等都是合法的拓扑排序。



图 4 一个 DAG。

现在的问题是,如何求出 DAG 的拓扑排序?或者说,我们应该使用 DFS 还是 BFS?沿着一条路径往下走得「足够深」,我们才能判断这条路径是否回到起点——即形成环路。我们总应该探索出一条完整的路径出来,因此应该使用 DFS。可是,要怎么做呢?可以发现,对于任意一个节点 $u$,它有三种可能的访问状态:

  1. 这个节点尚未被访问过(记为 0);
  2. 这个节点已经被访问过,并且它的所有子孙节点也都被递归访问过(记为 1);
  3. 这个节点正在被访问(它正在被访问或者它的子孙节点正在被访问),递归调用栈尚未退出(记为 -1)。

当我们使用 DFS 时,每当访问完一个节点,就应当把它插入到当前拓扑顺序的 首部 。这是因为我们的递归调用总是先递归到「最深处」,即最末端的孩子节点是先被记录下来的——它自然应该被记录在队伍的末尾。我们只要不断在首部插入,就能保证这是一个「从父亲到孩子」的顺序。

基于以上分析,dfs() 函数可以被实现如下:

const int maxn = 200 + 5;
int vis[maxn];              // 存放访问状态
int topo[maxn];             // 存放拓扑排序
int G[maxn][maxn];          // G[u][v] = 1 若存在从 u 到 v 的边
int n;                      // 节点个数
int t;                      // 游标,总是指向当前拓扑排序的首部

bool dfs(int u) {
    vis[u] = -1;
    for (int v = 0; v < n; i++) {
        if (G[u][v]) {
            if (vis[v] < 0) {       // v 正在被访问,说明有环路
                return false;
            } else if (!vis[v] && !dfs(v)) {    // v 没有被访问过,但是从它开始访问发现有环路
                return false;
            }
        }
    }
    // 递归访问结束,登记到拓扑排序中
    vis[u] = 1;
    topo[--t] = u;
    return true;
}

我们在主函数中启动对 dfs() 的调用:

int main() {
    // do sth...
    t = n;
    memset(vis, 0, sizeof(vis));
    for (int u = 0; u < n; u++) {
        if (!vis[u]) {
            if (!dfs(u)) {
                printf("Loop exists.\n");
                return 0;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        printf("%d", topo[i]);
    }
    // do sth...
}

可以用拓扑排序解决的问题有 给任务排序(Ordering tasks, UVa 10305),对应的求解代码参见 aoapc/ch06/e6-15,此处不在展开。

1.4 欧拉道路与欧拉回路

欧拉道路的概念源自著名的「七桥问题」。其本质是,能否从无向图中的一个节点出发走一条道路,使得每条边恰好经过一次。这样的道路被称为「欧拉道路」(Eulerian Path)。为了保证每条边恰好被走一次,则必然有如下结论:除了起点和终点,其他点的进出次数相等。即,除了起点和终点,其他点的度数为偶数。下面直接给出无向图中欧拉道路存在的充分条件。

无向图中欧拉道路存在的充分条件(结论)。 如果一个无向图是连通的,且最多只有两个奇点,则一定存在欧拉道路。

  • 如果不存在奇点,则可以从任意点出发走出一条欧拉道路,最终会回到该点(形成了欧拉回路);
  • 如果有两个奇点,则必须从其中一个奇点出发,抵达另一个奇点。

同样地,我们直接给出有向图中欧拉道路存在的充分条件:

有向图中欧拉道路存在的充分条件(结论)。 如果一个有向图在忽略边的方向之后是连通的,且最多只能有两个节点的入度不等于出度,而且必须是其中一个节点的出度比入度大 1(作为起点),另一个节点的入度比出度大 1(作为终点),则该有向图中存在欧拉道路。

综上所述,我们将计算欧拉道路的套路总结如下:

对于无向图,下面的代码给出了欧拉道路(回路)的计算:

const int maxn = 100 + 5;
int G[maxn][maxn];
int vis[maxn][maxn];
int n;

struct Edge {
    int x, y;       // 一条边用节点 (x,y) 来标识
    Edge(int x = 0, int y = 0) : x(x), y(y) {}
};

stack<Edge> euler_path;

// 无向图中求欧拉道路的 DFS(已经确定 G 形成了连通图)
void dfs(int u) {
    for (int v = 0; v < n; v++) {
        if (G[u][v] && !vis[u][v]) {
            vis[u][v] = vis[v][u] = 1;
            dfs(v);
            euler_path.push(Edge(u, v));
        }
    }
}

对于有向图,我们只需要将 vis 数组的设定这一行稍加修改即可:

// 有向图中求欧拉道路的 DFS(已经确定 G 形成了连通图)
void dfs(int u) {
    for (int v = 0; v < n; v++) {
        if (G[u][v] && !vis[u][v]) {
            vis[u][v] = 1;
            dfs(v);
            euler_path.push(Edge(u, v));
        }
    }
}

关于欧拉道路的一个完整代码示例参见 aoapc/ch06/c6-16。在这个示例中,我们手动构造了一个连通图,然后将欧拉道路中打印出来。

1.5 将问题化归为图问题

到目前为止,我们讲述了图上的「广度优先遍历及其应用(求最短路径)」和「深度优先遍历及其应用(求连通块的个数、求拓扑排序和求欧拉回路)」。然而,在实际情况中,图常常是隐藏在问题的描述中的,将它们化归成图问题,需要一定的思维能力。接下来将结合几道题目阐述如何将实际问题化归成图问题。


例题 2:古代象形符号(Ancient messages, ACM/ICPC World Finals 2011, UVa 1103)

本题的目的是识别 3000 年前古埃用到的 6 个象形文字,如图 5 所示。输入的是一个 $H$ 行 $W$ 列的字符矩阵,每个字符为横着连续的 4 个相邻像素点的十六进制(例如,10011100 对应的字符是 9c)。每个像素点要么为 1(表示黑点)、要么为 0(表示白点)。输入的二维字符矩阵满足:



图 5 古代象形符号。对于这 6 个符号,我们依次用 A、J、D、S、W 和 K 代指。

我们需要按照字典序输出字符矩阵中识别出的所有符号。 图 6 给出了两个样例输入,对于第一个输入,我们需要输出 AKW;对于第二个输入,我们需要输出 AAAAA



图 6 两个样例输入。

可以发现,二维矩阵中的每个符号组成了一个连通块(图)。由于题目规避了不同字符的重叠和接触,因此连通块的个数就是符号的个数。我们可以先通过 DFS 求出字符的个数。可是,要如何识别出每个连通块分别是 6 个字符中的哪一个呢?显然,我们需要利用「拓扑等价」这个特性。仔细观察图 5,可以发现,我们可以用每个字符内部的白色连通块的个数来区分这 6 个字符(分别为 1、3、5、4、0、2 个)。

可是,如何量化「内部」?一种方法是,直接求出所有连通的部分。如图 7 所示,我们可以在第一个样例输入中找到 7 个连通部分,其中,编号为 1 的是白色背景(字符外部),编号为 2、4、5 的,分别是 3 个字符,编号为 3 的是第一个字符内部的白色连通块,编号为 6 和 7 的,均是第三个字符内部的白色连通块。我们只需要通过和例题 1 中的 dfs() 类似的代码即可找到全部的连通部分。与此同时,我们需要识别出编号为 2、4、5 的连通块代表字符,并将它们的非白色背景的邻居存储下来。例如,第一个字符的内部邻居有 1 个,为 3;第三个字符的内部邻居有 2 个,为 6、7。这样,我们就可以将这些字符和图 5 所示字符对应起来了。最后按照字母顺序输出即可。



图 7 我们可以在样例输入 1 中找到 7 个连通块。

在给出 dfs() 之前,我们还有一些事情要做,那就是将输入的字符矩阵转换为 01 矩阵。

// 01 矩阵的最大大小
const int max_height = 200 + 5;
const int max_width = 50 * 4 + 5;
// pic 存放 01 矩阵
int pic[max_height][max_width];

// 01 矩阵的实际大小
int H, W;

// 存放每一个十六进制的字符到二进制串的映射
// 第一维度之所以是 256,是因为我们直接用 char 隐式转换为 int 作为 index,而 ASCII 码中有 256 个字符。
char hex2bin[256][5];

// 存放每一行读入的十六进制字符串
char line[max_width];

void set_hex2bin() {
    strcpy(hex2bin['0'], "0000");
    strcpy(hex2bin['1'], "0001");
    strcpy(hex2bin['2'], "0010");
    strcpy(hex2bin['3'], "0011");
    strcpy(hex2bin['4'], "0100");
    strcpy(hex2bin['5'], "0101");
    strcpy(hex2bin['6'], "0110");
    strcpy(hex2bin['7'], "0111");
    strcpy(hex2bin['8'], "1000");
    strcpy(hex2bin['9'], "1001");
    strcpy(hex2bin['a'], "1010");
    strcpy(hex2bin['b'], "1011");
    strcpy(hex2bin['c'], "1100");
    strcpy(hex2bin['d'], "1101");
    strcpy(hex2bin['e'], "1110");
    strcpy(hex2bin['f'], "1111");
}

// 将输入的十六进制矩阵转换为 01 矩阵存入 pic
void decode(char ch, int r, int c) {
    for (int i = 0; i < 4; i++) {
        pic[r][c + i] = hex2bin[ch][i] - '0';
    }
}

int main() {
    set_hex2bin();
    while (scanf("%d%d", &H, &W) == 2 && H) {
        // 读取十六进制矩阵转换为 01 矩阵存入 pic 中
        memset(pic, 0, sizeof(pic));
        for (int i = 0; i < H; i++) {
            scanf("%s", line);
            for (int j = 0; j < W; j++) {
                // 注意!这里字符从位置 (1,1) 开始写入
                decode(line[j], i + 1, j * 4 + 1);
            }
        }

        // 后续处理逻辑...
    }
}

上面的代码使用 set_hex2bin()decode() 函数实现字符数组到 01 矩阵的转换。

接下来,我们给出 dfs() 求出 01 矩阵中的所有连通块。这部分代码和例题 1 类似。

int idx[max_height][max_wdith];

// 这两个数组组合起来用于遍历一个位置上下左右的四个位置
const int dr[] = {-1, 1, 0, 0};
const int dc[] = {0, 0, -1, 1};

void dfs(int r, int c, int cnt) {
    idx[r][c] = cnt;
    for (int i = 0; i < 4; i++) {
        int r2 = r + dr[i];
        int c2 = c + dc[i];
        // dfs 的条件 —— 位置 (r2, c2) 合法、该位置没有被探索过、且该位置和 (r, c) 数字一致(要么同为 0、要么同为 1)
        // 满足这 3 个条件的位置才和本位置属于同一个连通块
        if (r2 >= 1 && r2 <= H && c2 >= 1 && c2 <= 4 * W && pic[r][c] == pic[r2][c2] && idx[r2][c2] == 0) {
            dfs(r2, c2, cnt);
        }
    }
}

同样地,我们在主函数中调用 dfs()

int main() {
    set_hex2bin();
    while (scanf("%d%d", &H, &W) == 2 && H) {
        // 读取十六进制矩阵转换为 01 矩阵存入 pic 中...

        int cnt = 0;
        // cc 存放了符号(黑色线条)的颜色编号,cc 的大小等于 pic 中字符的个数
        // 以图 7 为例,cc 中存放的将会是 2、4、5
        vector<int> cc;
        memset(idx, 0, sizeof(idx));
        for (int i = 1; i <= H; i++) {
            for (int j = 1; j <= 4 * W; j++) {
                if (!idx[i][j]) {
                    dfs(i, j, ++cnt);
                    if (pic[i][j] == 1) {
                        cc.push_back(cnt);
                    }
                }
            }
        }

        // 后续处理逻辑...
    }
}

最后,我们需要找到 cc 中每个字符的内部邻居(白色连通块)。

// neighbors 是一个 vector,大小为输入的 pic 中不同的连通块的个数
// 对于每个连通块,用一个 set 记录与其接壤(相邻)的内部白色连通块的个数
vector<set<int>> neighbors;

// 按照白色洞(连通块)的个数来排序(0-5)6 个象形文字
const char *code = "WAKJSD";

int main() {
    set_hex2bin();
    while (scanf("%d%d", &H, &W) == 2 && H) {
        // 读取十六进制矩阵转换为 01 矩阵存入 pic 中...

        // 调用 dfs 计算连通块...

        // 找到 cc 中每个字符的内部邻居(白色连通块)
        neighbors.clear();
        neighbors.resize(cnt + 1);
        for (int i = 1; i <= H; i++) {
            for (int j = 1; j <= 4 * W; j++) {
                if (pic[i][j] == 1) {
                    // 对于每一个黑线(黑线连在一起组成一个符号),判断它的邻居
                    for (int k = 0; k < 4; k++) {
                        int r2 = i + dr[k];
                        int c2 = j + dc[k];
                        // idx 的编号为 1 意味这这个位置属于背景板,与我们要找的白色洞没有关系。因此要去掉
                        if (r2 >= 1 && r2 <= H && c2 >= 1 && c2 <= 4 * W && pic[r2][c2] == 0 && idx[r2][c2] != 1) {
                            // 以图 7 为例,有
                            // neighbors[element = 2] = {3}
                            // neighbors[element = 4] = {}
                            // neighbors[element = 5] = {6, 7}
                            // 注意,neighbours 内部的元素为 set,因此,当同一个颜色被重复插入时,不会改变 set 的大小和内容。
                            neighbors[idx[i][j]].insert(idx[r2][c2]);
                        }
                    }
                }
            }
        }

        // 后续处理逻辑...
    }
}

到目前为止,我们已经将每个字符的内部白色连通块编号存入 neighbors 中了。接下来只需要和题目中的 6 个象形符号对比即可确定 cc 中每个数字对应的是哪一个字符了。

int main() {
    set_hex2bin();
    while (scanf("%d%d", &H, &W) == 2 && H) {
        // 读取十六进制矩阵转换为 01 矩阵存入 pic 中...

        // 调用 dfs 计算连通块...

        // 找到 cc 中每个字符的内部邻居(白色连通块)...

        // 用白色洞的个数来决定它属于哪一个符号,然后按照字母顺序输出
        vector<char> ans;
        for (int i : cc) {
            int white_block_num = (int) neighbors[i].size();
            ans.push_back(code[white_block_num]);
        }
        // 将识别出来的字符按照字母表顺序排序输出
        sort(ans.begin(), ans.end());
    }
}

最后将 ans 内的元素输出即可。看起来很完美。但是,这样真的完全正确吗?设想,如果 01 矩阵 pic 中左上角 (1,1) 的位置是一个黑像素,会发生什么?会导致编号为 1 的连通块是某个字符,而非白色背景!这就和我们所设想的、图 7 中给出的编号不一样了。这会导致 neighbors 计算错误,从而错解。一种简单的方法是将 01 矩阵向外扩展一圈(上下左右各加上一行一列空白像素 0),将检索区间从 (1,1)(H,4*W) 变成 (0,0)(H+1,4*W+1)。经过这个操作,我们可以保证编号为 1 的连通块一定是白色背景。

本题的完整代码请参见 aoapc/ch06/e6-13


例题 3:单词(Play on words, UVa 10129)

输入 $n$ 个单词,判断是否可以将这些单词排成一个序列,使得每个单词的第一个字母和上一个单词的最后一个字母相同。每个单词均由小写字母组成,输入中可能有重复单词。


如果我们把一个单词的首字母和末尾字母看成节点,并且二者直接存在一条有向边,则原问题等价于判断有向图中是否存在欧拉道路(回路)。 根据前文的叙述,首先,我们需要判断有向图的底图是否是连通的;然后,我们计算每个节点的入度和出度并判断是否符合要求。

我们采用 DFS 判断底图是否是连通的:

int used[256];      // used[ch] = 1 表示这个字母是有向图的一个节点
int G[256][256];    // 是否存在边
int vis[256];       // 是否访问过

void dfs(int ch, int cnt) {
    if (vis[ch] != 0 || !used[ch]) return;
    vis[ch] = 1;
    for (int ch2 = 'a'; ch2 <= 'z'; ch2++) {
        if (used[ch2] && G[ch][ch2]) {
            dfs(ch2, cnt);
        }
    }
}

和例题 1 类似,我们在主函数需要启动对 dfs() 的调用:

int main() {
    // do sth...

    // 使用 dfs 判断是否连通
    int cnt = 0;
    // 经过递归之后,若 cnt 等于 1,说明只有一个连通块,即是一个连通图
    for (int ch = 'a'; ch <= 'z'; ch++) {
        if (!vis[ch] && used[ch]) {
            dfs(ch, ++cnt);
        }
    }

    // do sth...
}

只要 cnt 的值为 1,就说明所有节点形成了一个连通图。

接下来,我们需要判断欧拉道路存在性的第二个条件。

int degree[256];    // 出度 +1,入度 -1

int main() {
    // do sth...

    // 假设 degree 在读取单词时已经按照如下方式设置:
    // 每当遇到一条从 ch 出去的边,则 degree[ch]++;
    // 每当遇到一条到 ch 的边,则 degree[ch]--

    vector<int> d;
    for (int ch = 'a'; ch <= 'z'; ch++) {
        if (degree[ch] != 0) {
            d.push_back(degree[ch]);
        }
    }

    bool ok = false;
    // cnt = 1 意味着可以形成一个连通块。这是欧拉道路存在的第一个条件
    // 入度不等于出度的节点,要么是 0,要么是 2。若是 2,则必然一个出度 = 入度 + 1,另一个入度 = 出度 + 1。这是第二个条件
    if (cnt == 1 && (d.empty() || (d.size() == 2 && (d[0] == 1 || d[0] == -1)))) ok = true;
    if (ok) printf("Ordering is possible.\n");
    else printf("The door cannot be opened.\n");

    // do sth...
}

在本题中,我们利用了欧拉道路存在性定理进行判定。我们不需要打印出整条欧拉道路。完整代码请参见 aoapc/ch06/e6-16-2


例题 4:自组合(Self-assembly, ACM/ICPC World Finals 2013, UVa 1572)

有 $n$ 种边上带标号的正方形。每条边上的标号要么是一个大写字母后面跟着一个加号或一个减号,要么为数字 00。当且仅当两个边的字母相同且符号相反时,这两条边能拼接在一起(00 边不能和任何边拼接在一起)。假设输入的每种正方形都有无数种,而且可以旋转和翻转,问:这些正方形能否拼接一个无限大的结构?

图 8 左边给出了 3 种正方形,右边是它们拼接而成的一个有限大的正方形。



图 8 自组合正方形。

样例输入:
3
A+00A+A+ 00B+D+A- B-C+00C+

样例输出:bounded


如何理解「形成无限大的结构」?无限大,并不一定要铺满整个平面,只要 能沿着一个方向不断延伸下去 也可以。正方形的拼接,就是将满足特定条件的边进行连接。如果我们将边上的标号看成图的节点,则对于图 8 左侧所示的第一个正方形,由于 $A+$ 可以和第二个正方形的 $A-$ 进行连接,这意味着 $A+$ 可以和第二个正方形非 $A-$、非 $00$ 的边进行 “连接”,即 分别存在一条「从 $A+$ 到 $B+$」和一条「从 $A+$ 到 $D+$」的边 。同理,存在一条「从 $B +$ 到 $C+$」的边、一条「从 $B -$ 到 $A-$」的边和一条「从 $B -$ 到 $D+$」的边。也就是说,对于图 8 给出的案例输入,我们可以形成一个如图 9 所示的有向图:



图 9 边的标号形成的有向图。

则能否延伸出一条无限长的通路,等价于边的标号形成的有向图中是否有环路。当存在环路时,这些标号所在的正方形就可以无限拼接下去。至此,我们将原问题化归为在有向图中判断是否存在环路的问题。我们可以对图执行一次拓扑排序,如果拓扑排序不存在,则意味着存在环路。因此,对于本题的求解,我们需要依次执行如下两个步骤:

整个实现没有什么难点,代码请参见 aoapc/ch06/e6-19


例题 5:理想路径(Ideal path, ACM/ICPC NEERC 2010, UVa 1599)

给一个 $n$ 个点、$m$ 条边组成的无向图,每条边上都涂有一种颜色。求节点 $1$ 到节点 $n$ 的一条路径,使得经过的边数尽可能少,在此前提下,经过边的颜色序列的字典序最小。注意,一对节点间可能有多条边。输入保证节点 $1$ 可达节点 $n$。输入第一行分别为节点和边的个数,从第二个开始,依次输入每条边的颜色。输出所求路径中边的个数,并按照顺序打印每条边的颜色。

样例输入:
4 6
1 2 1
1 3 2
3 4 3
2 3 1
2 4 4
3 1 1

样例输出:

2
1 3


对于上面的输入样例,其形成的图如图 10 所示。本题的核心诉求是求最短路径,但是难点在于「按颜色序例字典序最小」的方式给出最短路径。 在章节 1.2 中,我们使用 BFS tree 记录每个节点的父节点,在此处将不受用,因为 BFS tree 给出的路径并不能保证字典序最小。实际上,无需记录父节点也可以得到最短路,方法是从终点开始 “倒着” BFS,得到每个节点 $i$ 到终点的最短距离 dis[i]。然后,直接从起点开始走,每到达一个新节点时要保证距离值恰好减 1。如果有多个候选节点满足这个条件,则选择使得颜色字典序最小的节点;如果存在多个候选节点都能使得颜色字典序最小,则记录全部这些节点作为下一步的候选。如此操作,直到抵达终点。我们一共做了两次 BFS。



图 10 边带颜色的无向图。

我们首先准备好所需要的基础变量和结构体:

const int maxn = 100000 + 5;            // 最大节点个数
const int maxc = 1000000000;            // 最大颜色个数
int n;                                  // 节点个数
bool vis[maxn];                         // 访问标记
int dis[maxn];                          // 每个节点到终点的最短距离

struct Edge {
    int u, v, c;
    Edge(int u = 0, int v = 0, int c = 0) : u(u), v(v), c(c) {}
};

vector<Edge> edges;
vector<int> G[maxn];                    // G[u] 记录了和 u 相连的边的索引

void add_edge(int u, int v, int c) {
    edges.emplace_back(u, v, c);
    int edge_idx = (int) edges.size() - 1;
    G[u].push_back(edge_idx);
}

然后,根据刚才的分析,我们从终点(idx = n - 1)开始倒着执行 BFS,依次求出每个节点 u 到终点的最短距离 dis[u]

void rev_bfs() {
    memset(vis, 0, sizeof(vis));
    dis[n - 1] = 0;
    vis[n - 1] = true;

    queue<int> q;
    q.push(n - 1);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < G[u].size(); i++) {
            int e = G[u][i];
            int v = edges[e].v;
            if (!vis[v]) {
                vis[v] = true;
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
    }
}

dis 计算完毕之后,我们从起点开始再执行一遍 BFS,找到字典序最小的边的序列。

vector<int> res;            // 用来存放结果

// 从起点 (idx = 0) 开始 BFS,找到字典序最小的边的序列
void bfs() {
    memset(vis, 0, sizeof(vis));
    vis[0] = true;
    res.clear();

    vector<int> next;
    next.push_back(0);
    // 遍历每一个距离,就是在遍历每一个「下一步」
    for (int i = 0; i < min_dis[0]; i++) {
        int min_color = maxc;
        for (int u : next) {
            for (int k = 0; k < G[u].size(); k++) {
                int e = G[u][k];
                int v = edges[e].v;
                if (min_dis[u] == min_dis[v] + 1) {
                    // 说明 (u,v) 是最短路径上的一条边
                    // 从中选择颜色编号最小的作为理想路径中的边
                    min_color = min(min_color, edges[e].c);
                }
            }
        }
        res.push_back(min_color);

        vector<int> next2;
        for (int u : next) {
            for (int k = 0; k < G[u].size(); k++) {
                int e = G[u][k];
                int v = edges[e].v;
                // 将上面找到的理想路径中的边(即 color == min_color)的终点扔进 vector 用于 BFS
                if (min_dis[u] == min_dis[v] + 1 && !vis[v] && edges[e].c == min_color) {
                    next2.push_back(v);
                    vis[v] = true;
                }
            }
        }
        next = next2;
    }

    printf("%d\n", (int) res.size());
    printf("%d", res[0]);
    for (int i = 1; i < res.size(); i++) printf("%d", res[i]);
    printf("\n");
}

注意,这里的 BFS 没有用 queue 来实现,而采用 vector。这是因为我们已经清晰地知道从起点到终点的最短路径的长度,我们只需要沿着几个可能存在的候选道路坚定地往下走,就可以保证一定能到达终点。这一轮 BFS 的核心是找到颜色编号最小的每一条边。


例题 6:战场(Paintball, UVa 11853)

有一个 $1000 \times 1000$ 的正方形战场,战场西南角的坐标为 $(0,0)$,西北角的坐标为 $(0,1000)$。战场上有 $n$ 个敌人,第 $i$ 个敌人的坐标为 $(x_i, y_i)$,攻击范围为 $r_i$。为了避开敌人的攻击,在任意时刻,你与每个敌人的距离都必须严格大于他的攻击范围。你的任务是从战场的西边($x=0$ 的某个点)进入,东边($x=1000$ 的某个点)离开。如果有多个位置可以进出,你应当求出最靠北的位置。输入每个敌人的 $x_i, y_i, r_i$,输出进入战场和离开战场的坐标。


这个问题可以抽象为:正方形内有 $n$ 个圆形障碍物(可以和正方形的边相交),能否从正方形的左边界走到右边界?如果我们将正方形看成节点,并认为「当两个正方形相交时,它们之间就存在一条无向边」。由此,这些圆形可以组成一个或多个连通图。那么,能否从左侧到达右侧,要看是否有一个连通图将正方形切割成东西两个子部分,即这个连通图最上方的圆和正方形上边界接壤、最下面的圆和正方形下边界接壤。图 11 给出了这种连通图的一个案例。如何实现这个判断?一种方法是,对于每个和上边界相交的圆,我们基于 DFS 逐渐往下走,直到最下面一个圆。如果这个圆和下边界相交,则说明这样的连通图存在,我们无法穿越战场。我们先解决这个问题,然后再考虑从哪里进入和出去。



图 11 “连通图” 将战场分割成东西两个部分。此时无法穿越战场。

我们先准备基本数据结构和方法:

const int maxn = 1000 + 5;
const double W = 1000.0;

int n, vis[maxn];
double x[maxn], y[maxn], r[maxn];
bool ok;

// 判断两个敌人的攻击范围是否交叉(两个圆是否相交、两个节点之间是否存在边)
bool intersect(int c1, int c2) {
    return sqrt(pow(x[c1] - x[c2], 2) + pow(y[c1] - y[c2], 2)) < r[c1] + r[c2];
}

dfs() 函数如下:

// 从北到南通过 dfs 判断是否存在一条连通南北的「踏脚石道路」
bool dfs(int c) {
    if (vis[c]) return false;
    vis[c] = 1;
    // 和下边界相交
    if (y[c] - r[c] < 0) return true;
    for (int v = 0; v < n; v++) {
        if (intersect(c, v) && dfs(v)) return true;
    }

    // 后续处理逻辑...

    return false;
}

在主函数中,我们需要启动对 dfs() 的调用:

int main() {
    // 读取输入...

    for (int c = 0; c < n; c++) {
        // 对于每一个和上边界相交的节点,
        // 我们都需要判断从它开始形成的连通图是否会阻断东西战场
        if (y[c] + r[c] >= W && dfs(c)) {
            ok = false;
            break;
        }
    }

    // 后续处理逻辑...
}

ok = true 时,我们可以穿越战场。可以要从哪里进入、从哪里出去呢?图 12 到图 14 给出了所有的可能情况。题目要求我们从尽可能靠北的位置离开战场。我们不妨也从最靠北的位置进入战场。如图 12 所示,如果左右边界最上面的圆不和上边界相交,则从顶端进出即可。如果左右边界最上面的圆和上边界相交,则找到圆和左右边界的下交点,从这些点进出。和判断战场是否被分割遵循一样的思路,我们应该分别在左右边界上找到「从和上边界相交的圆开始的」连通图,并将这个连通图最下面的圆和边界的下交点作为进出点。这就是我们所能得到的最靠北的合法位置。



图 12 如果左右边界最上面的圆不和上边界相交,则从顶端进出即可。




图 13 如果左右边界最上面的圆和上边界相交,则找到圆和左右边界的下交点,从这些点进出。




图 14 找到在边界上最下面一个连通的圆,计算出它和左右边界的下交点,从这些点进出。


图 13 和图 14 中左右进出点的计算方式实现如下:

double left, right;

void check_circle(int c) {
    // 该圆和左边界相交,求出两个交点中更低的那个交点的高度(y 值)
    if (x[c] - r[c] < 0) {
        left = min(left, y[c] - sqrt(pow(r[c], 2) - pow(x[c], 2)));
    }
    // 该圆和右边界相交,求出两个交点中更低的那个交点的高度(y 值)
    if (x[c] + r[c] > W) {
        right = min(right, y[c] - sqrt(pow(r[c], 2) - pow(W - x[c], 2)));
    }
}

最后,我们只需要将 check_circle() 的调用插入 dfs() 函数的末尾即可。本题完整代码请参见 aoapc/ch06/e6-22


例题 7:雕塑(Sculpture, ACM/ICPC NWERC 2008, UVa 12171)

某雕塑由 $n$ 个边平行于坐标轴的长方体组成。每个长方体用 6 个整数 $x_0, y_0, z_0, x, y, z$ 表示(均为 1~500 的整数),其中 $x_0$ 为长方体的顶点中 $x$ 坐标的最小值, $x$ 表示长方体在 $x$ 方向的总长度。其他 4 个值的定义类似。你的任务是统计这个雕塑的体积和表面积。注意,雕塑内部可能会有密闭空间,其体积应该计算在总体积中,但从外部看不见的面不应计入表面积。雕塑可能会由多个连通块组成。


这道题目的本质仍然是「寻找连通块」,尽管需要探索的空间从二维数组变成了三位数组。此外,和例题 2 类似,我们需给背景(空气)和雕塑组成的各个连通块分别求出来并编号。除了以上关于图的操作,我们还需要通过离散化的操作降低问题的计算规模,否则会超时。整体执行思路如下:

完整代码请参见 aoapc/ch06/e6-18


例题 8:骰子难题(A dicey problem, ACM/ICPC World Finals 1999, UVa 810)

如图 15 所示,左边是一个迷宫,右边是一个骰子。你的任务是把骰子放在起点(骰子顶面和正面由输入决定)经过若干次滚动之后回到起点。每次骰子只能往和其顶面数字相同的格子移动,除非这个格子是五角星——不论骰子顶面是什么数字,它总可以向内容为五角星的格子滚动。输入一个 $R$ 行 $C$ 列的迷宫,起点坐标以及骰子顶面、正面的数字,输出一条可行的路径。



图 15 左边是一个迷宫,右边是标准的骰子的六个面的布局。

本题本质上是通过 BFS 求最短路径。难点是骰子的移动以及要设计四维的 vis 矩阵(当前所在格子的横纵坐标以及骰子的顶面与正面)。

首先,我们准备数据结构和一些基础操作:

const int maxn = 10 + 5;

int n, m;                           // 迷宫大小
int die[6 + 1][6 + 1];              // 用于存放将骰子逆时针转动 90 度后正面的数值
int vis[maxn][maxn][6 + 1][6 + 1];  // 四维的 vis 矩阵
int sx, sy, u, f;                   // 起点的坐标以及起点的顶面和正面
int maze[maxn][maxn];               // 存放迷宫内每个格子的数值

int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

struct State {
    // 状态由 4 个元素组成,当前所在格子的坐标以及骰子的顶面和正面
    int x, y, u, f;
    int pre;
    State() {}
    State(int x, int y, int u, int f, int pre) : x(x), y(y), u(u), f(f), pre(pre) {}
} states[10000 + 5];

// 将骰子逆时针转动 90 度,面向我们的面的数值
void init() {
    die[1][2] = 4; die[1][3] = 2; die[1][4] = 5; die[1][5] = 3;
    die[2][1] = 3; die[2][3] = 6; die[2][4] = 1; die[2][6] = 4;
    die[3][1] = 5; die[3][2] = 1; die[3][5] = 6; die[3][6] = 2;
    die[4][1] = 2; die[4][2] = 6; die[4][5] = 1; die[4][6] = 5;
    die[5][1] = 4; die[5][3] = 1; die[5][4] = 6; die[5][6] = 3;
    die[6][2] = 3; die[6][3] = 5; die[6][4] = 2; die[6][5] = 4;
}

// d 是 4 个滚动方向,上下左右依次编号为 0 1 2 3
// roll 函数给出了,当顶面为 vu、正面为 vf 时,向着 d 方向滚动一格之后骰子的新顶面和新正面
void roll(int &vu, int &vf, int d) {
    if (d == 0) {
        int tmp = vf;
        vf = 7 - vu;
        vu = tmp;
    } else if (d == 1) {
        int tmp = vu;
        vu = 7 - vf;
        vf = tmp;
    } else if (d == 2) {
        vu = 7 - die[vu][vf];
    } else if (d == 3) {
        vu = die[vu][vf];
    }
}

当以上关于骰子移动的操作正确设计之后,本题就没有什么难度了。只需要来一轮 BFS 即可。

typedef pair<int, int> pos;
vector<pos> trace;              // 存放路径

// 根据每个状态中的 pre(父指针)回溯到起点(将整个经过的 pos 按照顺序插入 trace 中)
void dfs(int idx) {
    if (idx == -1) return;
    dfs(states[idx].pre);
    trace.emplace_back(states[idx].x, states[idx].y);
}

void bfs() {
    trace.clear();
    int head = 0, rear = 0;
    states[rear++] = State(sx, sy, u, f, -1);
    memset(vis, 0, sizeof(vis));
    vis[sx][sy][u][f] = 1;
    while (head < rear) {
        State s = states[head++];
        for (int i = 0; i < 4; i++) {
            State s2 = s;
            s2.x += dr[i];
            s2.y += dc[i];
            if (s2.x <= 0 || s2.x > n || s2.y <= 0 || s2.y > m) continue;       // 往这个方向滚动会出界
            if (maze[s2.x][s2.y] != -1 && s.u != maze[s2.x][s2.y]) continue;    // 往这个方向滚动不合法
            if (s2.x == sx && s2.y == sy) {
                dfs(head - 1);
                // 最后回到了起点,别忘了将起点也插入到 trace 中
                trace.emplace_back(sx, sy);
                for (int j = 0; j < (int) trace.size(); j++) {
                    if (j % 9 == 0) printf("\n");
                    printf("(%d,%d)%c", trace[j].first, trace[j].second, j == (int) trace.size() - 1 ? '\n' : ',');
                }
                return;
            }
            // 滚动骰子
            roll(s2.u, s2.f, i);
            if (vis[s2.x][s2.y][s2.u][s2.f]) continue;
            vis[s2.x][s2.y][s2.u][s2.f] = 1;
            s2.pre = head - 1;
            states[rear++] = s2;
        }
    }
    cout << endl << "No Solution Possible" << endl;
}

本题的完整代码请参见 aoapc/ch06/p6-12


例题 9:检查员的难题(Inspector's dilemma, ACM/ICPC Dhaka 2007, UVa 12118)

某国家有 $V$ 个城市,每两个城市之间都有一条双向道路直接相连,长度为 $T$。你的任务时找一条最短的道路(起点和终点任意),使得该道路经过 $E$ 条指定的边。首先输入 $V$、$E$、$T$,然后在接下来的 $E$ 行输入每条边的起点和终点,输出最短道路的长度。如图 16 所示,若 $V = 5, E = 3, T = 1$,指定的 3 条边为 1-2、1-3、4-5,则最优道路为 3 1 2 4 5,长度为 4。



图 16 检察员的难题。

这道题看起来是 BFS 求最短路径,其实是欧拉道路问题。需要通过构造边使得构建出来的图具有欧拉道路。首先,我们将全连通图中的所有边都去掉,然后只将指定的无向边添加上,由此我们形成了一个新的图。然后,我们需要通过 DFS 检查这个图中有几个连通子图,并依次判定每个连通子图中奇点的个数(注意,奇点的个数必然为偶数)。如果这个连通子图中没有奇点或有两个奇点,则这个连通子图中存在欧拉道路。如果这个连通子图中的奇点个数超过 2,不妨设为 $x$,则我们只需要添加 $\frac{x - 2}{2}$ 条边就可以使得欧拉道路存在。 经过上述操作之后,每个连通子图内都存在了欧拉道路。我们现在只需要再将这些连通子图通过添加边的方式 “串联” 起来,就可以让整张图存在欧拉道路。而这样的欧拉道路,就是满足条件的最短道路。

图 17 形象地展示了以上流程。



图 17 最左图:一共有 7 个节点,5 条必须经过的边。然后是两个步骤 —— 第一步:在每个连通子图中添加边(非必需操作);第二步:将连通子图串联起来。

2 总结

本文重点解析了图上的 DFS 和 BFS 及相关的应用,包含求连通块、最短路径、拓扑排序和欧拉回路。和树类似,图的 BFS 通常用队列来实现,而图的深度优先遍历和递归紧密关联。如何将一个问题化归为图问题,是本文试图传授的核心理念。

本文给出的仅仅是图中的基本问题和算法实现。在未来,我会继续撰写进阶图论模型与实现,例如,最小生成树、Dijkstra 算法、Bellman-Ford 算法等。

最后

本文改写自刘大爷的经典教材《算法竞赛入门经典(第二版)》的第六章的部分内容。此外, 图 5 和图 6 来自 UVa 的官方网站(参见对应的链接)。


  1. 「并查集」的方法会在未来的某篇文章中进行分析。本文不讲是因为我还没搞懂:-) 

转载申请

本作品采用 知识共享署名 4.0 国际许可协议 进行许可, 转载时请注明原文链接。您必须给出适当的署名,并标明是否对本文作了修改。

您也可以通过下方按钮直接分享本页面:


发表评论

登录以发表评论

最新评论


Designed & written by Hailiang Zhao.
hliangzhao.cn. Copyright © 2021 - 2022 | 浙ICP备2021026965号-1
Manage