7f2ea67b550e55a4537e5ea5e6f7ff7b
Floodfill 算法和图的连通性

这些文章转自公众号:tech_gua,关注公众号可免费阅读这些文章。小专栏有独家的习题集和习题解答,会帮你掌握这些知识点。

上一篇文我们讲了七桥问题以及衍生出来的欧拉图的判断方式。再来复习一下欧拉道路的成立条件:除了起点和终点外, 其他点的“进出” 次数应该相等。 换句话说,除了起点和终点外, 其他点的度数应该是偶数。对于有向图来说,如果存在 2 个奇点,则这两个点其中一个点的出度恰好比入度大 1,另一个入度比出度大 1。

满足欧拉回路的一个大前提是判断当前图是一个连通图。问题又随之而来,什么是连通图?如何才能判断一个图到底是不是连通图?带着这个问题来看后面的内容。

话题引子

先给大家描述一下场景:笔者家乡在天津的大港油田,在油田作业区中会有钻探团队负责检测地下的石油储量。很多块临近的具有石油储量的区域将会在一起工作,所以通过网格来划分整片区域,并将作业区划成了多个作业块。在这种情况下,需要统计作业块的总个数从而预估作业成本。

我们将问题简单的抽象一下,将最大的作业区抽象成一个 m * n 的字符矩阵,*代表没有石油的无用之地,@代表具有石油储量的地方。例如如下矩阵:

****@
*@@*@
*@**@
@@@*@
@@**@

如上图所示的描述矩阵,我们可以给其划分成两个作业块:

            @   
@@          @
@    And    @
@@@         @
@@          @

判断一个点周围是否有其他点与其组成一个作业块,只需要找到当前格子的周围 8 个点(强调一下,斜线也考虑到情况中)。那其实我们的思路就很清晰了,只需要遍历一遍所有的矩阵区域,发现第一个 @就开始对图用不同的标记染色,最后对染色计数就完成了统计。Talk is cheap,看代码。

g = [
    '****@',
    '*@@*@',
    '*@**@',
    '@@@*@',
    '@@**@',
]

idx = [[0 for _ in range(0, len(g[0]))] for i in range(0, len(g))]

def dfs(x: int, y: int, color: int):
    if x < 0 or x >= len(g) or y < 0 or y >= len(g[0]):
        return
    if idx[x][y] > 0 or g[x][y] != '@':
        return
    idx[x][y] = color
    for dx in range(-1, 2, 1):
        for dy in range(-1, 2, 1):
            if dx != 0 or dy != 0:
                dfs(x=x + dx, y=y + dy, color=color)

col = 1
for i in range(0, len(g)):
    for j in range(0, len(g[0])):
        if idx[i][j] == 0 and g[i][j] == '@':
            dfs(x=i, y=j, color=col)
            col += 1

print("区域数量", col - 1)

如上代码使用一个双层循环来遍历一个点周围的 8 个点,然后再递归 8 个点的情况继续相同 color 的染色,从而达到区域内中的一点染色,使得整片区域染色。可以继续延伸思考下这个题目,其实使用 BFS 也可以将所有区块扫出来,因为染色问题只要标记就可以在让下一步完成状态更新。

回归文章的目的,我们为什么要出这道题呢?其实这道题就是经典的 Floodfill 算法,Floodfill 的原型是从一个区域中提取若干个连通的点与其他相邻区域区分开(或分别染成不同颜色)的算法,它的临近只是包含了上下左右四个方向,而这个题目又增加了斜对角的四个方向,但是搜索的思想是一样的。

或许你会想,这道题和图论有什么关系?其实,坐标图也是图的一种,我们可以理解成每一个 @ 在周围的 8 个方向上,如果存在另一个 @ 就说明它有一条边是连接彼此的。我们这样就将所有的 @ 节点组织到一张图中,并且由于分成多个作业块,所以这张图在 col 大于 1 的情况下,这张图是不连通的。我们引出图连通的定义:

图连通:如果无向图 G 中的任意两个节点联通,则称图 G 是联通的。

连通分量:如果无向图 G 是非连通的,那么每一个天然分隔的子图都是父亲图的联通分量。

我们从建图的角度来看,具有 8 个方向临近关系的节点其实就是加了一条边,而我们要求解的结果其实就是父亲图的联通分量的个数。(或许还可以尝试一下并查集?)

图的术语

继续用油田作业区的例子,这里我构建一个真正的图来表示作业区:

如果我们有真正的两个作业块,并且我们在 DG 两个节点进行加边操作,使其连接,那么这个图就变成了通过 DG 边连接的联通图。

在这张大图中,DG 因为是唯一联通两个联通分量的边,所以称 DG桥(bridge)

单独拿出 D 这个节点来看,如果我们去掉 D 以及与它直接相连的所有度,则图又会变成具有两个联通分量的非连通图。所以说 D 节点是整张图的割点(cut point)

于是我们引入以下几个定义:

割点:无向连通图中,去掉一个顶点及和它相邻的所有边,图中的连通分量数增加,则该顶点称为割点。

桥(又叫割边):无向联通图中,去掉一条边,图中的连通分量数增加,则这条边,称为桥或者割边。

看到这里,又会想当然的以为:两个割点之间的边一定是桥、割边的两个端点一定是割点。切记,这是错的!画两个图自己体会:

另外其他还有一些概念,我也一并列出,后面的所有场景可能会出现这些定义名称:

割点集合:在一个无向连通图中,如果有一个顶点集合 V,删除顶点集合 V 以及与 V 中顶点相连(至少有一端在 V 中)的所有边后,原图不连通,就称点集 V 为割点集合

点连通度:最小割点集合中的顶点数

割边集合:如果有一个边集合,删除这个边集合后,原图不连通,就称这个边集为割边集合。

边连通度:最小割边集合中的边数。

双连通:如果一个无向连通图的边连通度大于 1,则称该图是边双连通的(edge biconnected),也称双连通或重连通。

top Created with Sketch.