2023年7月19日发(作者：)

⽆向完全图k6有⼏条边_客户端基本不⽤的算法系列：从floodfill到图的连通性客户端基本不⽤的算法系列：从floodfill 到图的连通性微博：@冬⽠争做全栈⽠上⼀篇⽂我们讲了七桥问题以及衍⽣出来的欧拉图的判断⽅式。再来复习⼀下欧拉道路的成⽴条件：除了起点和终点外， 其他点的“进出” 次数应该相等。换句话说，除了起点和终点外， 其他点的度数应该是偶数。对于有向图来说，如果存在 2 个奇点，则这两个点其中⼀个点的出度恰好⽐⼊度⼤ 1，另⼀个⼊度⽐出度⼤ 1。满⾜欧拉回路的⼀个⼤前提是判断当前图是⼀个连通图。问题⼜随之⽽来，什么是连通图？如何才能判断⼀个图到底是不是连通图？带着这个问题来看后⾯的内容。话题引⼦先给⼤家描述⼀下场景：笔者家乡在天津的⼤港油⽥，在油⽥作业区中会有钻探团队负责检测地下的⽯油储量。很多块临近的具有⽯油储量的区域将会在⼀起⼯作，所以通过⽹格来划分整⽚区域，并将作业区划成了多个作业块。在这种情况下，需要统计作业块的总个数从⽽预估作业成本。我们将问题简单的抽象⼀下，将最⼤的作业区抽象成⼀个 m*n 的字符矩阵， *代表没有⽯油的⽆⽤之地， @代表具有⽯油储量的地⽅。例如如下矩阵：****@*@@*@*@**@@@@*@@@**@如上图所⽰的描述矩阵，我们可以给其划分成两个作业块：@@@ @@ And @@@@ @@@ @判断⼀个点周围是否有其他点与其组成⼀个作业块，只需要找到当前格⼦的周围 8 个点(强调⼀下，斜线也考虑到情况中)。那其实我们的思路就很清晰了，只需要遍历⼀遍所有的矩阵区域，发现第⼀个 @就开始对图⽤不同的标记染⾊，最后对染⾊计数就完成了统计。Talk ischeap，看代码。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]):returnif idx[x][y] > 0 or g[x][y] != '@':returnidx[x][y] = colorfor 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 += 1print("区域数量", 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. 图是连通的，即是⼀个连通图；2. 对于有向欧拉图来说，需要统计每个点的⼊度和出度满⾜：最多有两个点满⾜出度和⼊度数量不等，且其中⼀点出度⽐⼊度⼤1，另⼀点⼊度⽐出度⼤1；确定思路，我们来写代码：import copywords = ["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)] = dndef dfs(u: int):"""图联通判断使⽤图染⾊法，将所有与当前节点连接的点染⾊标记"""vis[u] = 0for 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]]] += 1outp[chrtoint[txt[-1]]] += 1vis[chrtoint[txt[0]]] = 1vis[chrtoint[txt[-1]]] = 1g[chrtoint[txt[0]]][chrtoint[txt[-1]]] = 1import numpy as npfrom collections import Counter# 看⼊度和出度的差de = list((inp) - (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 () and len(()) == 1:print("可以接龙")else:print("⽆法接龙")else:print("这个图不是欧拉图")通过对欧拉图以及连通性的学习，我们可以⽤图论知识来解决上述看上去像字符串的题⽬。其实，图论关注的都是节点和节点之间的关系，⼀旦发现可以建图，并且可以嵌套图论中的算法模型，你会发现很多问题都是很有套路的。后⾯如果我还能坚持写到⼆分图，你会发现算法并不难，难的是建图。提炼重点在上⾯的单词接龙中，我们需要掌握的是有向图如果处理欧拉图的问题。当我们判断⼀个图是否是欧拉图，需要先判断其连通性，再确定是否满⾜欧拉图的必要条件。判断连通性，通过 DFS 图染⾊就可以解决，是不是很像我们的 Floodfill 算法? ：def dfs(u: int):vis[u] = 0for 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((inp) - (outp))ce = Counter(de)# ....start = [i for i, n in enumerate(de) if n == 1][0]好了剩下的交给⼤家来练习了，下节课我们开始讲解图论中最叼的 Tarjan 算法！对应练习看懂⽂章后，不看实例代码，把下⾯两个题 A 了，就能效果拔群。上⽂【例题⼀】的油⽥分块：HDU-1241 / UVa572 Oil Deposits上⽂【例题⼆】的单词：UVa-10129