E37499e16c77f6cc56f808b2a6e1e2a9
图论的开端-七桥问题

图论的开端-七桥问题

冬瓜一直在想着写一个系列来罗列一些在客户端开发中,根本无法用到的算法。但是在计算机科学中又是能独立出来的学科。这之中图论就是一大块。

其实,一切的写作来源都是因为有一天冬瓜在自己的群里讨论了二分图问题,结果发现很多老哥或是一脸懵逼或是喊个 666 防止冷场。虽然在客户端(笔者是 iOS )开发中,这些东西并不常用,深追是根本不用,但是为什么互联网行业能侵入到各行各业的低层和上层,肯定有他自身的原因。当然,计算机科学自身也是一个交叉学科,离不开几何数学、高等数学、数论、图论、博弈论、组合数学、运筹学等等的理论基础。

话题跑偏了,我们继续来说图论。

话题印子

在日常开发中,我们很少接触图论,因为图论多半都是用来解决 N 的子节点的关系问题。但是图论又无处不在。我们通常讲网络作为互联网的代称,在宏观上讲,一个网络其实是组织事物之间的结构。这里我举几个例子:

  • 配电系统

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

  • 公司关系

    之前我们遇到了很多 P2P 雷暴的新闻,那么其实就带来一个对于公司是否可靠的探究问题。如果我们利用复杂的网路图来抽象出公司之间的担保关系,并评估一下指定公司的连带责任担保,其实就可以分析下担保网络复杂度就可以了。这个场景是来
    自知乎的一个回答,个人觉得很有意思。

有哪些看起来和图论无关的问题可以通过图论模型来解决? - shihang Wen的回答 - 知乎
https://www.zhihu.com/question/40771687/answer/185127200

  • 哥尼斯堡七桥问题

这是一个图论的超级经典问题,你几乎在所有的算法书中(只要目录有图论的)都能看到。这是一个生活问题,当时的哥尼斯堡(现在俄罗斯的加里宁格勒)有如图所示的 7 个桥,小岛与河的两岸由这些桥连接。本着不走回头路的原则,我们到底有没有办法一次性的将所有桥都走过。我们抽象出来建图就是如下场景:

分析七桥问题

继续趁热打铁,根据上面的场景,我们建一个图来描述这个问题:

我们讲岛屿和大陆抽象成 A、B、C、D 四个节点(Vertex),将七桥抽象成链接这些节点的度(Edge),然后我们整理出 N 年以前在大学课堂中学习到的邻接表(如果忘了自己看一眼就明白了🙄 )!

    A    B    C    D
A   0    1    2    2
B   1    0    1    1
C   2    1    0    0
D   2    1    0    0

使用下标 1, 2, 3, 4 来对应 A, B, C, D 四个点,我们来构建二维数组 graph[x][y]xy代表两个节点,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']

top Created with Sketch.