# 客户端基本不用的算法系列：图论的开端-七桥问题

## 话题印子

• 配电系统 配电系统中，我们会将多个电站抽象成一个个大的节点，并且每个节点总有输入和输出的电力资源，只要沾上资源，那么就要有开销问题，那么我们如何规划这个电力系统，才能让流量效率（流）和经济成本（费用）得到最合理的分配？你如果是强电或者是弱电专业的童鞋，那你一定知道著名的基尔霍夫电流定律。（笔者是通信的，hhh，还记得被《电路分析》支配的恐惧吗）
• 哥尼斯堡七桥问题

## 分析七桥问题

`    A    B    C    DA   0    1    2    2B   1    0    1    1C   2    1    0    0D   2    1    0    0`

```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} 种情况')```

```['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']

18世纪时，当这个问题被提出的时候，大家都尝试去解决这个问题，而没有对不存在答案这个答案来做思考。其中 Leonhard Euler 就是就对这个问题产生了疑问，他并没有像其他人一样去解决问题，而是明其不可解决

Euler 的证明思路其实很简单，我们单独来看一个节点，如果我走到这个节点上，那么它必须有一个边让我进来，有另一条不同的边让我出去，除非我们将这个节点作为起始点和终止点。我们再来想想，其实就是一个很简单的道理。

## 七桥问题的总结

• 图：图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。
• 边（度）：连接图中每个节点的路径。
• 奇点：那些度（对于有向图来说就是出度+入度）数量是奇数的节点。
• 偶点：对应度的数量是偶数的节点。
• 欧拉图：可以完成一笔画的图。
• 欧拉路径：欧拉图中一笔画时经过的路径。
• 欧拉回路：欧拉图并且一笔画起点和终点相等（欧拉路径成环）的路经集合。

## 欧拉回路的解题模板

```// 求欧拉回路或欧拉路，邻接阵形式，复杂度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; }```

63 篇文章11 人订阅

0 条评论