客户端基本不用的算法系列：图论的开端-七桥问题
客户端基本不用的算法系列：图论的开端-七桥问题
冬瓜一直在想着写一个系列来罗列一些在客户端开发中，根本无法用到的算法。但是在计算机科学中又是能独立出来的学科。这之中图论就是一大块。
其实，一切的写作来源都是因为有一天冬瓜在自己的群里讨论了二分图问题，结果发现很多老哥或是一脸懵逼或是喊个 666 防止冷场。虽然在客户端（笔者是 iOS ）开发中，这些东西并不常用，深追是根本不用，但是为什么互联网行业能侵入到各行各业的低层和上层，肯定有他自身的原因。当然，计算机科学自身也是一个交叉学科，离不开几何数学、高等数学、数论、图论、博弈论、组合数学、运筹学等等的理论基础。
话题跑偏了，我们继续来说图论。
话题印子
在日常开发中，我们很少接触图论，因为图论多半都是用来解决 N 的子节点的关系问题。但是图论又无处不在。我们通常讲网络作为互联网的代称，在宏观上讲，一个网络其实是组织事物之间的结构。这里我举几个例子：
- 配电系统 配电系统中，我们会将多个电站抽象成一个个大的节点，并且每个节点总有输入和输出的电力资源，只要沾上资源，那么就要有开销问题，那么我们如何规划这个电力系统，才能让流量效率（流）和经济成本（费用）得到最合理的分配？你如果是强电或者是弱电专业的童鞋，那你一定知道著名的基尔霍夫电流定律。（笔者是通信的，hhh，还记得被《电路分析》支配的恐惧吗）
- 公司关系 之前我们遇到了很多 P2P 雷暴的新闻，那么其实就带来一个对于公司是否可靠的探究问题。如果我们利用复杂的网路图来抽象出公司之间的担保关系，并评估一下指定公司的连带责任担保，其实就可以分析下担保网络复杂度就可以了。这个场景是来自知乎的一个回答（https://www.zhihu.com/question/40771687/answer/185127200），个人觉得很有意思。
- 哥尼斯堡七桥问题
这是一个图论的超级经典问题，你几乎在所有的算法书中（只要目录有图论的）都能看到。这是一个生活问题，当时的哥尼斯堡（现在俄罗斯的加里宁格勒）有如图所示的 7 个桥，小岛与河的两岸由这些桥连接。本着不走回头路的原则，我们到底有没有办法一次性的将所有桥都走过。我们抽象出来建图就是如下场景：
分析七桥问题
继续趁热打铁，根据上面的场景，我们建一个图来描述这个问题：
我们讲岛屿和大陆抽象成 A、B、C、D 四个节点（Vertex），将七桥抽象成链接这些节点的度（Edge），然后我们整理出 N 年以前在大学课堂中学习到的邻接表（如果忘了自己看一眼就明白了? ）！
A B C DA 0 1 2 2B 1 0 1 1C 2 1 0 0D 2 1 0 0使用下标 1,2,3,4 来对应 A,B,C,D 四个点，我们来构建二维数组 graph[x][y]， x和 y代表两个节点， graph[x][y]代表这两个点之间的路径有几条。然后我们从图中任意找一个起始点，开始DFS（深度优先遍历）所有路径。
为什么要这么做？因为我们现在不知道问题的答案，那么我们就想开发客户端一样，暴力扫出所有的答案。下面我们来确定一个思路：我们在搜索一条路径的时候，每次访问一个节点a，就去查阅我们创建的邻接表，如果邻接表中记录的路径仍旧存在，那么那个节点就是即将行走的下一个节点。由于我们需要在无路可走的情况下返回上层节点，所以最后回溯一下情况，即路径记录数组还原以及邻接矩阵路径还原即可。
下面我用代码来穷举所有的情况：
import copy
graph = [ [0, 1, 2, 2], [1, 0, 1, 1], [2, 1, 0, 0], [2, 1, 0, 0],]
hash_v = { 0: 'A', 1: 'B', 2: 'C', 3: 'D',}
hash_v_res = {v: k for k, v in hash_v.items()}tot_case = 0
def vetex(v: str) -> int: return hash_v_res[v]
def show_path(path_record: list, g: list): global tot_case tot_case += 1 path = [hash_v[i] for i in path_record] # print('当前路径:') print(path) # print('未走的边') # for i in range(0, len(g)): # for j in range(0, i): # if g[i][j] > 0: # print(f'{hash_v[i]} <=> {hash_v[j]}')
def dfs(g: list, v: int, result: list): result.append(v) have_next_step = False for node, _ in enumerate(graph): if g[v][node] > 0: have_next_step = True g[v][node] -= 1 g[node][v] -= 1 dfs(g=g, v=node, result=result) g[v][node] += 1 g[node][v] += 1 if not have_next_step: show_path(path_record=result, g=g) result.pop()
dfs(g=copy.deepcopy(graph), v=vetex('A'), result=[])dfs(g=copy.deepcopy(graph), v=vetex('B'), result=[])dfs(g=copy.deepcopy(graph), v=vetex('C'), result=[])dfs(g=copy.deepcopy(graph), v=vetex('D'), result=[])
print(f'一共 {tot_case} 种情况')上述代码中我们穷举了所有的路径，并且可以打印出其路径结果。最后发现一共 100 种方法，每一种都是走到最后无路可走的情况。
['A', 'B', 'C', 'A', 'C']['A', 'B', 'C', 'A', 'D', 'A', 'C']['A', 'B', 'C', 'A', 'D', 'B']['A', 'B', 'D', 'A', 'C', 'A', 'D']['A', 'B', 'D', 'A', 'C', 'B']['A', 'B', 'D', 'A', 'D']['A', 'C', 'A', 'B', 'C']['A', 'C', 'A', 'B', 'D', 'A', 'D']['A', 'C', 'A', 'D', 'A', 'B', 'C']['A', 'C', 'A', 'D', 'A', 'B', 'D']['A', 'C', 'A', 'D', 'B', 'A', 'D']['A', 'C', 'A', 'D', 'B', 'C']['A', 'C', 'B', 'A', 'C']['A', 'C', 'B', 'A', 'D', 'A', 'C']['A', 'C', 'B', 'A', 'D', 'B']['A', 'C', 'B', 'D', 'A', 'B']['A', 'C', 'B', 'D', 'A', 'C']['A', 'C', 'B', 'D', 'A', 'D']['A', 'D', 'A', 'B', 'C', 'A', 'C']['A', 'D', 'A', 'B', 'D']['A', 'D', 'A', 'C', 'A', 'B', 'C']['A', 'D', 'A', 'C', 'A', 'B', 'D']['A', 'D', 'A', 'C', 'B', 'A', 'C']['A', 'D', 'A', 'C', 'B', 'D']['A', 'D', 'B', 'A', 'C', 'A', 'D']['A', 'D', 'B', 'A', 'C', 'B']['A', 'D', 'B', 'A', 'D']['A', 'D', 'B', 'C', 'A', 'B']['A', 'D', 'B', 'C', 'A', 'C']['A', 'D', 'B', 'C', 'A', 'D']['B', 'A', 'C', 'A', 'D', 'A']['B', 'A', 'C', 'A', 'D', 'B', 'C']['B', 'A', 'C', 'B', 'D', 'A', 'C']['B', 'A', 'C', 'B', 'D', 'A', 'D']['B', 'A', 'D', 'A', 'C', 'A']['B', 'A', 'D', 'A', 'C', 'B', 'D']['B', 'A', 'D', 'B', 'C', 'A', 'C']['B', 'A', 'D', 'B', 'C', 'A', 'D']['B', 'C', 'A', 'B', 'D', 'A', 'C']['B', 'C', 'A', 'B', 'D', 'A', 'D']['B', 'C', 'A', 'C']['B', 'C', 'A', 'D', 'A', 'B', 'D']['B', 'C', 'A', 'D', 'A', 'C']['B', 'C', 'A', 'D', 'B', 'A', 'C']['B', 'C', 'A', 'D', 'B', 'A', 'D']['B', 'D', 'A', 'B', 'C', 'A', 'C']['B', 'D', 'A', 'B', 'C', 'A', 'D']['B', 'D', 'A', 'C', 'A', 'B', 'C']['B', 'D', 'A', 'C', 'A', 'D']['B', 'D', 'A', 'C', 'B', 'A', 'C']['B', 'D', 'A', 'C', 'B', 'A', 'D']['B', 'D', 'A', 'D']['C', 'A', 'B', 'C', 'A', 'D', 'A']['C', 'A', 'B', 'C', 'A', 'D', 'B']['C', 'A', 'B', 'D', 'A', 'C', 'B']['C', 'A', 'B', 'D', 'A', 'D']['C', 'A', 'C', 'B', 'A', 'D', 'A']['C', 'A', 'C', 'B', 'A', 'D', 'B']['C', 'A', 'C', 'B', 'D', 'A', 'B']['C', 'A', 'C', 'B', 'D', 'A', 'D']['C', 'A', 'D', 'A', 'B', 'C', 'A']['C', 'A', 'D', 'A', 'B', 'D']['C', 'A', 'D', 'A', 'C', 'B', 'A']['C', 'A', 'D', 'A', 'C', 'B', 'D']['C', 'A', 'D', 'B', 'A', 'C', 'B']['C', 'A', 'D', 'B', 'A', 'D']['C', 'A', 'D', 'B', 'C', 'A', 'B']['C', 'A', 'D', 'B', 'C', 'A', 'D']['C', 'B', 'A', 'C', 'A', 'D', 'A']['C', 'B', 'A', 'C', 'A', 'D', 'B']['C', 'B', 'A', 'D', 'A', 'C', 'A']['C', 'B', 'A', 'D', 'B']['C', 'B', 'D', 'A', 'B']['C', 'B', 'D', 'A', 'C', 'A', 'B']['C', 'B', 'D', 'A', 'C', 'A', 'D']['C', 'B', 'D', 'A', 'D']['D', 'A', 'B', 'C', 'A', 'C']['D', 'A', 'B', 'C', 'A', 'D', 'B']['D', 'A', 'B', 'D', 'A', 'C', 'A']['D', 'A', 'B', 'D', 'A', 'C', 'B']['D', 'A', 'C', 'A', 'B', 'C']['D', 'A', 'C', 'A', 'B', 'D', 'A']['D', 'A', 'C', 'A', 'D', 'B', 'A']['D', 'A', 'C', 'A', 'D', 'B', 'C']['D', 'A', 'C', 'B', 'A', 'C']['D', 'A', 'C', 'B', 'A', 'D', 'B']['D', 'A', 'C', 'B', 'D', 'A', 'B']['D', 'A', 'C', 'B', 'D', 'A', 'C']['D', 'A', 'D', 'B', 'A', 'C', 'A']['D', 'A', 'D', 'B', 'A', 'C', 'B']['D', 'A', 'D', 'B', 'C', 'A', 'B']['D', 'A', 'D', 'B', 'C', 'A', 'C']['D', 'B', 'A', 'C', 'A', 'D', 'A']['D', 'B', 'A', 'C', 'B']['D', 'B', 'A', 'D', 'A', 'C', 'A']['D', 'B', 'A', 'D', 'A', 'C', 'B']['D', 'B', 'C', 'A', 'B']['D', 'B', 'C', 'A', 'C']['D', 'B', 'C', 'A', 'D', 'A', 'B']['D', 'B', 'C', 'A', 'D', 'A', 'C']
一共 100 种情况我们查看上面的情况发现了一个问题，因为我们有 7 个桥，所以我们如果想全部都走完的话，最少要途经 8 个点。可是穷举的所有答案当中，最多只有 7 个点，也就是说所有的走投无路的情况都无法完成七个桥全部走完。
18世纪时，当这个问题被提出的时候，大家都尝试去解决这个问题，而没有对不存在答案这个答案来做思考。其中 Leonhard Euler 就是就对这个问题产生了疑问，他并没有像其他人一样去解决问题，而是明其不可解决。
并且从中，Euler 还对问题做了一些升华的思考，他对这个七桥问题（Euler 称之为一笔画问题）给出了一个充要条件：在连通图中，奇点的数目不是 0 个就是 2 个（连到一点的数目如是奇数条，就称为奇点，如果是偶数条就称为偶点，要想一笔画成，必须中间点均是偶点，也就是有来路必有另一条去路，奇点只可能在两端，因此任何图能一笔画成，奇点要么没有要么在两端）。
Euler 的证明思路其实很简单，我们单独来看一个节点，如果我走到这个节点上，那么它必须有一个边让我进来，有另一条不同的边让我出去，除非我们将这个节点作为起始点和终止点。我们再来想想，其实就是一个很简单的道理。
像这样可以一口气走完的图，为了纪念 Euler 这一伟大的证明方法，在图论中被称为欧拉图，且其中经过的路径被称之为欧拉路径。当奇点为零的时候，起始和终止点相同，则走过的路径我们将其画出来后成为一个环，这种情况下这个闭合的路径集合则称之为欧拉回路。
七桥问题也是图论这么学科的起源，也是我们学习图论的开端~ 我们虽然没有欧拉这些科学家的智商，但是我们有计算机+代码，就可以枚举（暴力）出最终结果。至于方法论，就交给科学家来证明好了。工程师的工作就是解决问题。
七桥问题的总结
- 图：图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。
- 边（度）：连接图中每个节点的路径。
- 奇点：那些度（对于有向图来说就是出度+入度）数量是奇数的节点。
- 偶点：对应度的数量是偶数的节点。
- 欧拉图：可以完成一笔画的图。
- 欧拉路径：欧拉图中一笔画时经过的路径。
- 欧拉回路：欧拉图并且一笔画起点和终点相等（欧拉路径成环）的路经集合。
欧拉回路的解题模板
一下是求欧拉回路的 Fleury算法（你们根本想不到还有这种东西）：
// 求欧拉回路或欧拉路，邻接阵形式，复杂度O（n^2）// 返回路径长度，path 返回路径(有向图是得到的是反向路径)// 传入图的大小 n 和邻接阵 mat，不相交邻点边权0// 可以有自环与重边，分为无向图和有向图#define MAXN 100
void find_path_u(int n, int mat[][MAXN], int now, int& step, int* path) { int i; for (i = n - 1; i >= 0; i --) while (mat[now][i]) { mat[now][i]--,mat[i][now]--; find_path_u(n, mat, i, step, path); } path[step++] = now; }
void find_path_d(int n,int mat[][MAXN],int now,int& step,int* path) { int i; for (i = n - 1; i >= 0;i --) while (mat[now][i]) { mat[now][i]--; find_path_d(n, mat, i, step, path); } path[step++] = now; }
int euclid_path(int n, int mat[][MAXN], int start, int* path) { int ret = 0; find_path_u(n, mat, start, ret, path); // find_path_d(n,mat,start,ret,path); return ret; }