6.4 图

用DFS求连通块

例题:油田(UVa 572)

输入一个m行n列的字符矩阵,统计字符@组成多少八连块。如果两个字符@所在的格子相邻,就说他们同属一个八连块。

题意分析

和前面的二叉树遍历类似,图也有DFS和BFS遍历。由于DFS更容易编写,所以一般用DFS找连通块:从每个@格子出发,递归遍历它周围的@格子。每次访问一个格子时,就给它写上一个“连通分量编号”(即下面代码中的idx数组),这样就可以在访问之前检查它是否已经有了编号,从而避免同一个格子访问多次。

题解代码

#include<cstdio>
#include<cstring>
const int maxn = 100+5;
char pic[maxn][maxn];
int m, n, idx[maxn][maxn];

void dfs(int r, int c, int id){
    if(r < 0 || r >= m || c < 0 || c >= n) return; // 未出界
    if(idx[r][c] > 0 || pic[r][c] != '@') return; // 不是@或已经访问过
    idx[r][c] = id; // 连通分量编号
    for(int dr = -1; dr <= 1; dr++)
        for(int dc = -1; dc <= 1; dc++)
            if(dr != 0 || dc != 0) dfs(r+dr, c+dc, id);    
}

int main(){
    while(scanf("%d%d", &m, &n) == 2 && m && n){
        for(int i = 0; i < m; i++) scanf("%s", pic[i]);
        memset(idx, 0, sizeof(idx));
        int cnt = 0;
        for(int i = 0; i < m; i++)
            for(int j = 0; i < n; j++)
                if(idx[i][j] == 0 && pic[i][j] == '@') dfs(i, j, ++cnt);
        printf("%d\n", cnt);
    }
    return 0;
}

上面的代码用一个二重循环来找到当前格子的相邻8个格子,也可以用常量数组活着八条DFS调用。这道题的算法别名种子填充,Wikipedia有相应的动画。
PS:图也有DFS遍历和BFS遍历,其中前者用递归实现,后者用队列实现。求多维数组连通块的过程也成为种子填充。

例题:古代象形符号(UVa 1103)

本题的目的是识别三千年前古埃及用到的6种象形文字。
每组数据包含一个H行W列的字符矩阵(H<=200,W<=50),每个字符为4个相邻像素点的十六进制。转化为二进制后,1表示黑点,2表示白点。输入满足:
1. 不会出现上述六个符号之外的其他符号
2. 输入至少包含一个符号,且每个黑像素都属于一个符号。
3. 每个符号都是一个四连块,并且不同符号不会相互接触或者包含。
4. 如果两个像素有公共顶点,那么他们一定有一个相同的相邻黑像素(有公共边)。
5. 符号的形状一定和图像拓扑等价(可以拉伸不能拉断)

用BFS求最短路

假设有一个网格迷宫,由n行m列的单元格组成,每个单元格要么是空地(用1表示),要么是障碍物(用0表示)。如何找到从起点到终点的最短路径?

分析

还记得二叉树的BFS吗?结点的访问顺序恰好是它们到根结点距离从小到大的顺序。类似地,也可以用BFS来按照从起点的距离顺序遍历迷宫图。
例如,假定起点在左上角,就从左上角开始用BFS遍历迷宫图,逐步计算出它到每个点的最短路距离,以及这些最短路径上每个结点的“前一个结点”。注意,如果把图中遍历的箭头理解为指向父亲的指针,那么迷宫中的格子就变成了一棵树——除了起点之外,每个结点恰好有一个父亲。这棵树称为最短路树,或者BFS树。

例题:Abbott的复仇(UVa 816)

有一个最多包含9*9个交叉点的迷宫。输入起点、离开起点时的朝向和终点,求一条最短路。
这个迷宫的特殊之处在于:进入一个交叉点的方向不同,那么允许出去的方向也不同。

分析

本题和普通的迷宫在本质上是一样的,但是由于朝向也起到了关键作用, 所以需要用一个三元组(r, c, dir)表示“位于(r, c),面朝dir这个状态。假设入口位置为(r0, c0),朝向为dir,则初始状态并不是(r0, c0, dir)而是(r1, c1, dir),其中(r1, c1)(r0, c0)沿着方向dir走了一步之后的坐标。此处用d[r][c][dir]表示初始状态到(r, c, dir)的最短路长度,并且用p[r][c][dir]保存了状态(r, c, dir)在BFS树中的父结点。
许多复杂的迷宫问题都可以转化为最短路问题,然后用BFS求解。在套用BFS框架之前,需要先搞清楚图中的结点包含哪些内容。

代码及分步分析

#include<cstdio>
#include<cstring>
#include<vector>
// 首先是输入过程,将4个方向和3种转弯方式编号为0~3和0~2,并且提供相应的转换函数:
const char* dirs = "NFSW";
const char* turns = "FLR";
int dir_id(char c){
    return strchr(dirs, c) - dirs;
}
int turn_id(char c) {
    return strchr(turns, c) - turns;
}
// 接下来是行走函数,根据当前状态和转弯方式,计算出后继状态:
const int dr[] = {-1, 0, 1, 0};
const int dc[] = {0, 1, 0, -1};

Node walk(const Node& u, int turn){
    int dir = u.dir;
    if(turn == 1) dir = (dir + 3) % 4; // 逆时针
    if(turn == 2) dir = (dur + 1) %4; // 顺时针
    return Node(u.r + dr[dir], u.c + dc[dir], dir);
}
// 输入函数比较简单,作用就是读取r0,c0,dir,并且计算出r1,c1,然后读入has_edge数组,其中has-edge[r][c][dir][turn]表示当前状态是(r,c,dir),是否可以沿着转弯方向turn行走。下面是BFS主过程:
void solve(){
    queue<Node> q;
    memset(d, -1, sizeof(d));
    Node u(r1, ci, dir);
    d[u.r][u.c][u.dir] = 0;
    q.push(u);
    while(!q.empty()){
        Node u = q.front(); q.pop();
        if(u.r == r2 && u.c == c2){
            print_ans(u); return;
        }
        for(int i = 0; i < 3; i++){
            Node v = walk(u,i);
            if(has_edge[u.r][u.c][u.dir][i) && inside(v.r, v.c) && d[v.r][v.c][v.dir] < 0){
                d[v.r][v.c][v.dir] = d[u.r][u.c][u.dir] + 1;
                p[v.r][v.c][v.dir] = u;
                q.push(v);
            }
        }
    }
    printf("No Solution Possible\n");
}
// 最后是解的打印过程。它也可以写成递归函数,不过用vector保存结点可以避免递归时出现栈溢出,并且更加灵活。
// 使用BFS求出最短路之后,可以用递归方式打印最短路的具体路径。如果最短路非常长,递归可能会引起栈溢出。此时可以改用循环,用vector保存路径。
void print_ans(Node u){
    // 从目标结点逆序追溯到初始结点
    vector<Node> nodes;
    for(;;){
        nodes.push_back(u);
        if(d[u.r][u.c][u.dir] == 0) break;
        u = p[u.r][u.c][u.dir];
    }
    nodes.push_back(Node(r0, c0, dir));

    // 打印解,每行10个。
    int cnt = 0;
    for(int i = nodes.size()-1; i >= 0; i--){
        if(cnt % 10 == 0) printf(" ");
        printf(" (%d, %d)", nodes[i].r, nodes[i].c);
        if(++cnt % 10 == 0) printf("\n");
    }
    if(nodes.size() % 10 != 0) printf("\n");
}

本题非常重要

拓扑排序

例题:给任务排序(UVa 10305)

假设有n个变量,还有m个二元组(u,v),分别表示变量u小于v。那么所有的变量从小到大排列应该是什么样子呢?例如有四个变量a,b,c,d,如果已知a<b,c<b,d<c那么这四个变量的排序可能是a<d<c<b

分析

把每个变量看成一个点,小于关系看成有向边,则得到了一个有向图。这样,我们的任务实际上的把一个图的所有结点排序,使得每一条有向边(u,v)对应的u都排在v的前面。在图论中,这个问题被称为拓扑排序。
不难发现,如果图中存在有向环,则不存在拓扑排序,反之则存在。不包含有向环的有向图称之为有向无环图(DAG),可以借助DFS完成拓扑排序。在访问完一个结点之后把它加到当前拓扑序的首部。

代码

#include<cstdio>
int c[maxn];
int topo[manx], t;
bool dfs(int u){
    c[u] = -1; // 访问标志
    for(int v= 0; v < n; v++) if(G[u][v]){
        if(c[v] < 0) return false;// 存在有向环,退出
        if(!c[v] && !dfs(v)) return false;
    }
    c[u] = 1;
    topo[--t] = u;
    return true;
}
bool toposort(){
    t = n
    memset(c, 0, sizeof(c));
    for(int u =0; u < n; u++) if(!c[u])
        if(!dfs(u)) return false;
    return true;
}

这里用到了一个c数组,c[u]=0表示从来没有访问过(从来没有调用过dfs(u)c[u]=1表示已经访问过,并且还递归访问过它的所有子孙;c[u]=-1表示正在访问)。
可以用DFS求出有向无环图的拓扑排序。如果排序失败,说明该图存在有向环,不是DAG。

欧拉回路

背景

有一条名为Pregel的河流经过konigsberg城。城中有7座桥,把河中的两个岛与河岸连接起来。当地居民热衷于一个难题:是否存在一条路线,可以不重复地走遍7座桥。这就是著名的七桥问题。它由大数学家欧拉提出,并给出了完美的解答。
欧拉首先把七桥问题改写成了图论的形式,则问题变成了:能否从无向图的一个结点出发,走出一条道路,每条边刚好经过一次。这样的路线称为欧拉道路,也可以形象地称为一笔画。

分析

不难发现,在欧拉道路中,“进”和“出”是相对应的——除了起点和终点之外,其他点的进出次数应该相等。换句话说,其他点的度数应该是偶数。很可惜,在七桥问题中,所有点的度数均为奇数,因此是不可能存在欧拉道路的。上述条件也是充分条件——如果一个无向图是连通的,且最多只有两个奇点,那么一定存在欧拉道路。如果有两个奇点,则必须从其中一个奇点出发,另一个奇点终止。如果奇点不存在,则可以从任意点出发,最终回到改点,称为欧拉回路。
用类似的推理方式可以得到有向图的结论:最多只能有两个点的入度不等于出度,而且必须是其中一个点的出度恰好比入度大1,另一个点的入度比出度大1。当然,还有一个前提条件:忽略边的方向之后,图必须是连通的。

通用代码

下面的程序同时适用于欧拉道路和贿赂。但是如果需要打印的是欧拉道路,在主程序中调用时,参数必须是道路的起点。另外,打印的顺序的逆序的,因此真正使用这份代码时,应当把printf语句替换为push语句,把边(u,v)压入一个栈内。

void euler(int u){
    for(int v = 0; v < n; v++) if(G[u][v] && !vis[u][v]){
        vis[u][v] = vis[v][u] = 1;
        euler(v);
        printf("%d %d\n", u, v);
    }
}

尽管上面的代码只适用于无向图,但是不难改成有向图:把vis[u][v]=vis[v][u]=1改成vis[u][v]即可。
根据连通性和度数可以判断出无向图和有向图是否存在欧拉道路和欧拉回路。可以用DFS构造欧拉回路和欧拉道路。

例题:单词(UVa 10129)

输入n个单词,是否可以把这些单词排成一个序列,使得每个单词的第一个字母和上一个单词的最后一个字母相同。每个单词最多包含1000个小写字母。输入中可以有重复单词。

分析

把字母看作结点,单词看做有向边,则问题有解当且仅当图中有欧拉路径。前面讲过,有向图存在欧拉道路的条件有两个:底图(忽略边方向后得到的无向图)连通,且度数满足条件。判断联通的方法有两种,一是之前介绍过的DFS,二是并查集。