客户端基本不用的算法系列：从 floodfill 到图的连通性
客户端基本不用的算法系列：从 floodfill 到图的连通性
满足欧拉回路的一个大前提是判断当前图是一个连通图。问题又随之而来，什么是连通图？如何才能判断一个图到底是不是连通图？带着这个问题来看后面的内容。
话题引子
先给大家描述一下场景：笔者家乡在天津的大港油田，在油田作业区中会有钻探团队负责检测地下的石油储量。很多块临近的具有石油储量的区域将会在一起工作，所以通过网格来划分整片区域，并将作业区划成了多个作业块。在这种情况下，需要统计作业块的总个数从而预估作业成本。
我们将问题简单的抽象一下，将最大的作业区抽象成一个 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 = 1for 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 个方向临近关系的节点其实就是加了一条边，而我们要求解的结果其实就是父亲图的联通分量的个数。(或许还可以尝试一下并查集？)
图的术语
继续用油田作业区的例子，这里我构建一个真正的图来表示作业区：
如果我们有真正的两个作业块，并且我们在 D 和 G 两个节点进行加边操作，使其连接，那么这个图就变成了通过 DG 边连接的联通图。
在这张大图中， DG 因为是唯一联通两个联通分量的边，所以称 DG 是桥（bridge）。
单独拿出 D 这个节点来看，如果我们去掉 D 以及与它直接相连的所有度，则图又会变成具有两个联通分量的非连通图。所以说 D 节点是整张图的割点（cut point）。
于是我们引入以下几个定义：
割点：无向连通图中，去掉一个顶点及和它相邻的所有边，图中的连通分量数增加，则该顶点称为割点。
桥（又叫割边）：无向联通图中，去掉一条边，图中的连通分量数增加，则这条边，称为桥或者割边。
看到这里，又会想当然的以为：~~两个割点之间的边一定是桥、割边的两个端点一定是割点~~。切记，这是错的！画两个图自己体会：
另外其他还有一些概念，我也一并列出，后面的所有场景可能会出现这些定义名称：
割点集合：在一个无向连通图中，如果有一个顶点集合 V，删除顶点集合 V 以及与 V 中顶点相连（至少有一端在 V 中）的所有边后，原图不连通，就称点集 V 为割点集合。
点连通度：最小割点集合中的顶点数。
割边集合：如果有一个边集合，删除这个边集合后，原图不连通，就称这个边集为割边集合。
边连通度：最小割边集合中的边数。
双连通：如果一个无向连通图的边连通度大于 1，则称该图是边双连通的（edge biconnected），也称双连通或重连通。
有了这些关于无向图的定义（包括上一篇文章的欧拉路，欧拉图等），如果将对应场景的题目抽象建图，就可以解决更多的问题。
再来一道，找感觉
学了很多的理论定义，我们还是需要落回到 Coding 上，这里再给出一道可以多解的习题，大家下来也可以利用其他方法来尝试能否解出。
题目：给出 N 个单词，判断是否这些单词可以“接龙”。所谓的“接龙”和我们日常玩的成语接龙是一个意思，例如：world、 dead 这两个单词，因为 world 的结尾是 d，并且 dead 的开头也是 d，所以这两个单词便可“接龙”。如果这一组单词可以接成一条龙，我们就认为给出的单词集是合法的。
我们首先来分析问题，其实我们并不是很关注单词中间具体是什么，而是关心每个单词的首尾字母分别是啥。这两个字母代表了出入的关系。我们换一个角度来讲，如果我们将 26 个字母当作 26 个图节点，那么这些单词的定义其实就是一组边关系。例如 world 这个单词，其实就是给 w 和 d 这两个字母节点增加了一个有向边。
如此建图之后，你就会发现，这其实是我们之前的七桥问题（一笔画问题），只要通过单词集加边后形成的图是一个欧拉图，就可以完成“接龙”。当输入单词集后，我们要证明生成的图是一个欧拉图，那么就要证明这个图是满足两个条件的：
- 图是连通的，即是一个连通图；
- 对于有向欧拉图来说，需要统计每个点的入度和出度满足：最多有两个点满足出度和入度数量不等，且其中一点出度比入度大1，另一点入度比出度大1；
确定思路，我们来写代码：
import copy
words = ["world", "dead", "deadline", "export", "tiger", "range"]
# 临界矩阵g = [[0 for _ in range(0, 26)] for _ in range(0, 26)]
# 标记数组，图染色使用vis = [0 for _ in range(0, 26)]
# 出度和入度统计inp, outp = [0 for _ in range(0, 26)], [0 for _ in range(0, 26)]
# 字母表chrtoint = {}
for dn in range(0, 26): base_a = ord("a") chrtoint[chr(base_a + dn)] = dn
def dfs(u: int): """ 图联通判断 使用图染色法，将所有与当前节点连接的点染色标记 """ vis[u] = 0 for v in range(0, 26): if vis[v] == 1 and g[u][v] == 1: dfs(v)
# 初始化邻接矩阵for ind, txt in enumerate(words): inp[chrtoint[txt[0]]] += 1 outp[chrtoint[txt[-1]]] += 1 vis[chrtoint[txt[0]]] = 1 vis[chrtoint[txt[-1]]] = 1 g[chrtoint[txt[0]]][chrtoint[txt[-1]]] = 1
import numpy as npfrom collections import Counter
# 看入度和出度的差de = list(np.array(inp) - np.array(outp))ce = Counter(de)if ce[-1] == 1 and ce[1] == 1 and len(ce) <= 3: # 查找起点，即 入度 - 出度 = 1 的点 start = [i for i, n in enumerate(de) if n == 1][0] # 连通性测试 dfs(u=start) vsc = Counter(vis) if 0 in vsc.keys() and len(vsc.keys()) == 1: print("可以接龙") else: print("无法接龙")else: print("这个图不是欧拉图")通过对欧拉图以及连通性的学习，我们可以用图论知识来解决上述看上去像字符串的题目。其实，图论关注的都是节点和节点之间的关系，一旦发现可以建图，并且可以嵌套图论中的算法模型，你会发现很多问题都是很有套路的。后面如果我还能坚持写到二分图，你会发现算法并不难，难的是建图。
提炼重点
在上面的单词接龙中，我们需要掌握的是有向图如果处理欧拉图的问题。当我们判断一个图是否是欧拉图，需要先判断其连通性，再确定是否满足欧拉图的必要条件。
判断连通性，通过 DFS 图染色就可以解决，是不是很像我们的 Floodfill 算法? ：
def dfs(u: int): vis[u] = 0 for v in range(0, 26): if vis[v] == 1 and g[u][v] == 1: dfs(v)判断欧拉路，其实就是简单的出度和入度的计数法，在 Python 中可以简单的使用 Counter 这个类来轻松构建计数字典，并且通过 numpy 中的矩阵相减来轻松解决出入度的相等问题。用 Python 的列表推导轻松的搜到起点（Python 是不是写起来很爽？? ）。
import numpy as npfrom collections import Counter
# 看入度和出度的差de = list(np.array(inp) - np.array(outp))ce = Counter(de)
# ....start = [i for i, n in enumerate(de) if n == 1][0]