小米 6 首席研究员的研究报告集

Hi there!

Python数据结构与算法补全系列(五)--图

Posted on Edited on In ,

图的术语和定义

顶点

顶点又称节点，是图的基础部分。顶点的名字被称为“键”。顶点也可以带有附加信息，我称作“有效载荷”。

边

边是图的另一个基础部分。两个顶点通过一条边相连，表示它们之间存在关系。边既可以是单向的，也可以是双向的。如果图中的所有边都是单向的，我们称之为有向图。

权重

边可以带权重，用来表示从一个顶点到另一个顶点的成本。例如在路线图中，从一个城市到另一个城市，边的权重可以表示两个城市之间的距离。

图的定义

图可以用 G 来表示，并且 $G = (V, E)$。其中，V 是一个顶点集合，E 是一个边集合。每一条边是一个二元组(v, w)，其中 $w, v \in V$ 。可以向边的二元组中再添加一个元素，用于表示权重。子图 s 是一个由边 e 和顶点 v 构成的集合，其中 $e \subset E$ 且 $v \subset V$。

路径

路径是由边连接的顶点组成的序列。路径的正式定义为$w_1, w_2,…,w_n$, 其中对于所有的$1\leq i \leq n-1$, 有 $(w_1, w_{i+1}) \in E$。 无权重路径的长度是路径上的边数，有权重路径的长度是路径的边的权重之和。

环

环是有向图中的一条起点和终点为同一个顶点的路径。没有环的图被称为无环图，没有环的有向图被称为有向无环图，简称为 DAG。

图的数据抽象类型

有两种非常著名的图实现：邻接矩阵和邻接表。

邻接矩阵

实现图最简单的方式就是使用二维矩阵。在矩阵实现中，每一行和每一列都表示图中的一个顶点。第 v 行和第 w 列交叉的格子中的值表示从顶点 v 到顶点 w 的边的权重。如果两个顶点被一条边连接起来，就称它们是相邻的。

邻接矩阵的优点是简单。对于小图来说，邻接矩阵可以清晰地展示哪些顶点是相连的。如果一个邻接矩阵的绝大多数单元格是空的，这种矩阵是“稀疏”的。对于存储稀疏数据来说，矩阵并不高效。

邻接表

为了实现稀疏连接的图，更高效的方式是使用邻接表。在邻接表实现中，我们为图对象的所有顶点保存一个主列表，同时为每一个顶点对象都维护一个列表，其中记录了与它相连的顶点。

在 Python 中，通过字典可以轻松地实现邻接表。创建两个类：： Graph 类存储包含所有顶点的主列表， Vertex 类表示图中的每一个顶点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
## Vertrx 类
class Vertex:
    def __init__(self, key):
        self.id = key
        self.connected_to = {}
    
    def add_neighbor(self, nbr, weight=0):
        self.connected_to[nbr] = weight
    
    def __str__(self):
        return str(self.id) + ' conneted to: ' + str([x.id for x in self.connected_to])

    def get_connections(self):
        return self.connected_to.keys()
    
    def get_id(self):
        return self.id

    def get_weight(self, nbr):
        return self.connected_to[nbr]

class Graph:
    def __init__(self):
        self.ver_list = {}
        self.num_vertices = 0
    
    def add_vertex(self, key):
        self.num_vertices = self.num_vertices + 1
        new_vertex = Vertex(key)
        self.ver_list[key] = new_vertex
        return new_vertex

    def get_vertex(self, n):
        if n in self.ver_list:
            return self.ver_list[n]
        else:
            return None
    
    def __contains__(self, n):
        return n in self.ver_list
    
    def add_edge(self, f, t, cost=0):
        if f not in self.ver_list:
            nv = self.add_vertex(f)
        if t not in self.ver_list:
            nv = self.add_vertex(t)
        self.ver_list[f].add_neighbor(self.ver_list[t], cost)

    def get_vertices(self):
        return self.ver_list.keys()

    def __iter__(self):
        return iter(self.ver_list.values())
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
>>> g = Graph()
>>> for i in range(6): 
...    g.addVertex(i)
>>> g.vertList
{0: <__main__.Vertex at 0x20181075b20>,
 1: <__main__.Vertex at 0x20181075ac0>,
 2: <__main__.Vertex at 0x20181075f40>,
 3: <__main__.Vertex at 0x20181075ee0>,
 4: <__main__.Vertex at 0x20181075df0>,
 5: <__main__.Vertex at 0x20181075e80>}
>>> g.addEdge(0, 1, 5) 
>>> g.addEdge(0, 5, 2) 
>>> g.addEdge(1, 2, 4) 
>>> g.addEdge(2, 3, 9) 
>>> g.addEdge(3, 4, 7) 
>>> g.addEdge(3, 5, 3) 
>>> g.addEdge(4, 0, 1) 
>>> g.addEdge(5, 4, 8) 
>>> g.addEdge(5, 2, 1) 
>>> for v in g: 
...    for w in v.getConnections(): 
...        print(f'({v.get_id()} ,{w.get_id()})')
...
(0 ,1)
(0 ,5)
(1 ,2)
(2 ,3)
(3 ,4)
(3 ,5)
(4 ,0)
(5 ,4)
(5 ,2)

宽度优先搜索

考虑这样一个任务：将单词 FOOL 转换成 SAGE。在解决词梯问题时，必须每次只替换一个字母，并且每一步的结果都必须是一个单词，而不能是不存在的词。假设单词表中有 n 个单词，将一个单词与列表中其他所有单词进行比较，时间复杂度为 $O(n^2)$。用图算法来解决这个问题，大致步骤为：

  1. 用图表示单词之间的关系
  2. 用宽度优先搜索的图算法找到从起始单词到结束单词的最短路径

单词集合：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
FOOL
POOL
FOIL
FOUL
COOL
POLL
FAIL
POLE
PALL
POPE
PALE
PAGE
SALE
SAGE

假设有数目巨大的桶，每个个桶上都标有一个长度为 4 的单词，但是某一个字母被下划线代替，如 POP_。当处理列表中的每一个单词时，将它与桶上的标签进行比较。使用下划线作为通配符，我们将 POPE 和 POPS 放入同一个桶中。同一个桶中的单词一定是相连的。

在 Python 中，可以通过字典来实现上述方法。字典的键就是桶上的标签，值就是对应的单词列表。一旦构建好字典，就能利用它来创建图。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from pythonds.graphs import Graph
def build_graph(word_file):
    d = {}
    g = Graph()
    wfile = open(word_file,'r')
    # 创建词桶  
    for line in wfile:
        word = line[:-1]
        for i in range(len(word)):
            bucket = word[:i] + '_' + word[i+1:]
            if bucket in d:
                d[bucket].append(word)
            else:
                d[bucket] = [word]

    # 为同一个桶中的单词添加顶点和边 
    for bucket in d.keys():
        for word1 in d[bucket]:
            for word2 in d[bucket]:
                if word1 != word2:
                    g.addEdge(word1, word2)
    
    return g

宽度优先搜索(BFS)是最简单的图搜索算法之一，也是许多其他重要图算法的原型。 给定图 G 和起点 s，BFS 通过边来访问在 G 中与 s 之间存在路径的顶点。BFS 的一个重要特性是，它会在访问完所有与 s 相距为 k 的顶点之后再去访问与 s 相距为 k+1 的顶点。

为了记录进度，BFS 会将顶点标记成白色、灰色或黑色。在构建时，所有顶点都被初始化成白色。白色代表该顶点没有被访问过。当顶点第一次被访问时，它就会被标记为灰色；当 BFS完成对该顶点的访问之后，它就会被标记为黑色。这意味着一旦顶点变为黑色，就没有白色顶点与之相连。灰色顶点仍然可能与一些白色顶点相连，这意味着还有额外的顶点可以访问。

BFS 在访问一个新的顶点时，如果是白色，说明顶点没有被访问过，接下来执行以下四步：

  1. 将新的未访问顶点 nbr 标记成灰色
  2. 将 nbr 的 predecessor 设置成当前顶点 currentVert
  3. 将 nbr 的 distance 设置成到 currentVert 的 distance 加 1
  4. 将 nbr 添加到队列的尾部
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 宽度优先搜索
from pythonds.graphs import Graph, Vertex
from pythonds.basic import Queue
def bfs(g, start):
    start.setDistance(0)
    start.setPred(None)
    vert_queue = Queue()
    vert_queue.enqueue(start)
    while (vert_queue.size() > 0):
        current_vert = vert_queue.dequeue()
        for nbr in current_vert.getConnections():
            if (nbr.getColor() == 'white'):
                nbr.setColor('gray')
                nbr.setDistance(current_vert.getDidtance() + 1)
                nbr.set_pred(current_vert)
                vert_queue.enqueue(nbr)
        current_vert.setColor('black')

def traverse(y):
    x = y
    while (x.getPred()):
        print(x.getId())
        x = x.getPred()
    print(x.getId())
1
2
3
4
5
6
7
8
9
10
>>> g = build_graph('word_file.txt')
>>> bfs(g, g.getVertex('FOOL'))
>>> traverse(g.getVertex('SAGE'))
SAGE
SALE
PALE
PALL
POLL
POOL
FOOL

深度优先搜索

马踏棋盘问题（也成为骑士周游问题）：将吗随机放在国际象棋的 8*8 的棋盘中的某个格子里，马按照走棋规则进行移动。要求每个方格只进入一次，走遍 64 个方格。

图搜索算法是解决马踏棋盘问题的算法中最易理解也最易编程的一种。通过两个步骤解决这个问题：

  1. 用图表示骑士在棋盘上的合理走法
  2. 使用图算法找到一条长度为 $rows \times columns - 1$, 满足图中的每一个顶点都只被访问一次。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
from pythonds.graphs import Graph
def kinghtGraph(bd_size):
    ktGraph = Graph()
    for row in range(bd_size):
        for col in range(bd_size):
            node_id = pos_to_node_id(row, col, bd_size)
            new_positions = get_legal_moves(row, col, bd_size)
            for e in new_positions:
                nid = pos_to_node_id(e[0], e[1], bd_size)
                ktGraph.addEdge(node_id, nid)
    return ktGraph

def get_legal_moves(x, y ,bd_size):
    new_moves = []
    move_off_sets = [(-1, -2), (-1, 2), (-2, -1), (-2, 1), (1, -2), (1, 2), (2, -1), (2, 1)]

    for i in move_off_sets:
        new_x = x + i[0]
        new_y = y + i[1]

        if legal_coord(new_x, bd_size) and legal_coord(new_y, bd_size):
            new_moves.append((new_x, new_y))

    return new_moves

def legal_coord(x, bd_size):
    if x >= 0 and x < bd_size:
        return True
    else:
        return False

def pos_to_node_id(row, col, bd_size):
    return row * bd_size + col

用来解决骑士周游问题的搜索算法是深度优先搜索（DFS）。DFS 通过尽可能深地探索分支来构建树。 这个例子中，DFS 的目的是找到 63 条边构成的路径，当 DFS 遇到死路时，它会回退到树种倒数第 2 深的顶点，以继续移动。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from pythonds.graphs import Graph, Vertex
def knightTour(n,path,u,limit):
        u.setColor('gray')
        path.append(u)
        if n < limit:
            nbrList = list(u.getConnections())
            i = 0
            done = False
            while i < len(nbrList) and not done:
                if nbrList[i].getColor() == 'white':
                    done = knightTour(n+1, path, nbrList[i], limit)
                i = i + 1
            if not done:  # 准备回溯
                path.pop()
                u.setColor('white')
        else:
            done = True
        return done

knightTour 递归函数接受 4 个参数： n 是搜索树的当前深度； path 是到当前为止访问过的顶点列表； u 是希望在图中访问的顶点； limit 是路径上的顶点总数。它首先检查基本情况。如果有一条包含 64 个顶点的路径，就从 knightTour 返回 True ，以表示找到了一次成功的周游。如果路径不够长，则通过选择一个新的访问顶点并对其递归调用 knightTour 来进行更深一层的探索。

1
2
3
4
5
6

```python
>>> kg = kinghtGraph(8)
>>> path = []
>>> v_5 = kg.getVertex(4)
>>> knightTour(0, path, v_5, 63)

性能一般的计算机，可能要等半个小时才能得到结果。用如下代码加速算法：

1
2
3
4
5
6
7
8
9
10
11
def order_by_avail(n):
    res_list = []
    for v in n.getConnections():
        if v.getColor() == 'white':
            c = 0
            for w in v.getConnections():
                if w.getColor() == 'white':
                    c = c + 1
            res_list.append((c, v))
    res_list.sort(key = lambda x:x[0])
    return [y[1] for y in res_list]

用 order_by_avail(u) 替换掉 knightTour 函数中第 4 行的 u.getConnections。 这一行保证接下来要访问的顶点有最少的合理走法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
>>> kg = kinghtGraph(8)
>>> path = []
>>> v_5 = kg.getVertex(4)
>>> knightTour(0, path, v_5, 63)
>>> for i in path:
...     print(i.getId())
...
4
14
31
46
63
53
47
62
52
58
...
42
27
17
0
10

选择合理走法最多的顶点作为下一个访问顶点的问题在于，它会使骑士在周游的前期就访问位于棋盘中间的格子。当这种情况发生时，骑士很容易被困在棋盘的一边，而无法到达另一边的那些没访问过的格子。首先访问合理走法最少的顶点，则可使骑士优先访问棋盘边缘的格子。这样做保证了骑士能够尽早访问难以到达的角落，并且在需要的时候通过中间的格子跨越到棋盘的另一边。

我们称利用这类知识来加速算法为启发式技术。人类每天都在使用启发式技术做决定，启发式搜索也经常被用于人工智能领域。

马踏棋盘问题是深度优先搜索的一种特殊情况。通用的深度优先搜索简单一些，它的目标是尽可能深地搜索，尽可能多地连接图中的顶点，并且在需要的时候进行分支。

一次深度优先搜索甚至能够创建多棵深度优先搜索树，我们称之为深度优先森林。深度优先森林还会使用 Vertex 类中的两个额外的实例变量：发现时间记录算法在第一次访问顶点时的步数，结束时间记录算法在顶点被标记为黑色时的步数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from pythonds.graphs import Graph
class DFSGrahp(Graph):
    def __init__(self):
        super().__init__()
        self.time = 0
    
    def dfs(self):
        for a_vertex in self:
            a_vertex.setColor('white')
            a_vertex.setPred(-1)
        for a_vertex in self:
            if a_vartex.getColor() == 'white':
                self.dfsvisit(a_vertex)
    
    def dfsvisit(self, start_vertex):
        start_vertex.setColor('gray')
        self.time += 1
        start_vertex.setDiscovery(self.time)
        for next_vertex in start_vertex.getConnections():
            if next_vertex.getColor() == 'white':
                next_vertex.setPred(next_vertex)
                self.dfsvisit(next_vertex)
        start_vertex.setColor('black')
        self.time += 1
        start_vertex.setFinish(self.time)

每个顶点的发现时间和结束时间都体现了括号特性，这意味着深度优先搜索树种的任一子节点都比该节点更晚的发现时间和更早的结束时间。