图论，特别是图的ADT(抽象数据类型)在数学和计算机科学中使用是非常广泛的。图由顶点(节点)和边(可能是有方向的/加权重的)组成，边连接顶点，这种数据结构可以有效的解决一些领域的问题。算法设计里面，最常用的就是用来解决两个顶点之间是否存在一条路径可以到达，或者说，是否存在。图的边权重和方向都可能是算法设计者要考虑的。在这篇文章中，我将会探索两个简单的算法，深度优先查找和广度优先查找，要达到如下突出的目标:
- 找到所有的顶点在所有的连通域
- 返回在两个顶点之间所有可用的的路径
- 在BFS的情况下，返回最短路径。(长度的计算是根据边的数量多少)
图
为了清楚的讨论每个算法，我创建了一个连接图，有6个顶点和6个incident边，这个图是无向的，和没有给边分配权重的。长度会基于路径之间的经过的顶点数量计算。有两个常用的方式来代表两个一个图，第一个是使用相邻矩阵(对密集图)，第二个方式是使用相邻列表（对稀疏图），这里选择相邻列表实现，使用字典存储顶点，并且值为一个set类型集合用来表示该顶点相邻节点。由于图是无向的，每个边都存储在相邻集的两个入射节点中。
graph = {'A': set(['B', 'C']),
'B': set(['A', 'D', 'E']),
'C': set(['A', 'F']),
'D': set(['B']),
'E': set(['B', 'F']),
'F': set(['C', 'E'])}
看下面这张图的刻画，你会留意到在 ‘F’ 和 ‘C/E’的相邻节点包含一个循环，这是故意包括的，以便为算法提供在两个所需节点之间返回多个路径的选项。
graph.png
Depth-First Search
第一个要讨论的算法是深度优先查找，正如名字那样蕴意着，顺着一个顶点的分支一直找下去知道回溯。这种特点，使得可以使用迭代或者递归实现这个算法，下面是大概流程：
- 标记当前顶点为已经访问
- 探索所有相邻节点，前提是不在已经查找的列表里面。
Connected Component
下面的实现是使用栈(FILO)的数据结构构造，函数会返回在连接域中所有可用的顶点数据。使用Python的set类型的减法操作符重载来删除set里面的数据，从而达到只添加不重复的相邻顶点。
def dfs(graph, start):
visited, stack = set(), [start]
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
stack.extend(graph[vertex] - visited)
return visited
dfs(graph, 'A') # {'E', 'D', 'F', 'A', 'C', 'B'}
第二种实现的功能和第一个是相同的，但是，这次我们使用更简洁的递归实现。由于Python的语法，默认参数只会创建一次，我们需要在每次用户调用的时候创建一个新的数据集，另一个Python语言的内部机制是,函数的参数传递是通过引用传递，所以不用在每次递归重新创建就可以访问可变集合的数据。
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
for next in graph[start] - visited:
dfs(graph, next, visited)
return visited
dfs(graph, 'C') # {'E', 'D', 'F', 'A', 'C', 'B'}
Paths
我们可以调整之前两个实现，来返回开始顶点到目标顶点之间的所有可能路径。下面的实现也是使用的栈(FILO)的数据结构，会使用迭代来解决。当遇到目标路径，就会使用yield。使用python的generator可以只计算你想得到的路径。
def dfs_paths(graph, start, goal):
stack = [(start, [start])]
while stack:
(vertex, path) = stack.pop()
for next in graph[vertex] - set(path):
if next == goal:
yield path + [next]
else:
stack.append((next, path + [next]))
list(dfs_paths(graph, 'A', 'F')) # [['A', 'C', 'F'], ['A', 'B', 'E', 'F']]
下面的实现是使用递归的方法，使用 ‘yield from’来返回路径。
def dfs_paths(graph, start, goal, path=None):
if path is None:
path = [start]
if start == goal:
yield path
for next in graph[start] - set(path):
yield from dfs_paths(graph, next, goal, path + [next])
list(dfs_paths(graph, 'C', 'F')) # [['C', 'F'], ['C', 'A', 'B', 'E', 'F']]
Breath-First Search
另一个算法叫做广度优先搜索算法，它和DFS算法返回的结果是一样的，只不过BFS会保证先返回最近的路径。BFS使用递归的话会比较棘手，所以这里只描述了迭代的版本实现。探寻每一个顶点的步骤其实和DFS实现是一样的，但是，要把栈(FILO)替换为队列(FIFO),来达到广度优先。这个步骤会保证第一个得到的路径是最短的，当在以路径经过的顶点数量为计算路径长度标准的时候。
Connected Component
和迭代版本的DFS实现类似，只需要把栈结构变为队列的结构（把pop()变为pop(0)）。
def bfs(graph, start):
visited, queue = set(), [start]
while queue:
vertex = queue.pop(0)
if vertex not in visited:
visited.add(vertex)
queue.extend(graph[vertex] - visited)
return visited
bfs(graph, 'A') # {'B', 'C', 'A', 'F', 'D', 'E'}
Paths
这个实现也是可以根据之前的DFS实现再次简单的更改的，栈改为队，它先返回的路径总是会最短的。
def bfs_paths(graph, start, goal):
queue = [(start, [start])]
while queue:
(vertex, path) = queue.pop(0)
for next in graph[vertex] - set(path):
if next == goal:
yield path + [next]
else:
queue.append((next, path + [next]))
list(bfs_paths(graph, 'A', 'F')) # [['A', 'C', 'F'], ['A', 'B', 'E', 'F']]
我们知道BFS生成器方法会先返回最短的路径，所以我们可以创建一个有用的函数，简单的返回最短路径，如果没找到就返回None。当我们使用生成器的时候，理论上它提供的性能是差不多的性能，就像在BFS实现中分解和返回第一个匹配路径一样。
def shortest_path(graph, start, goal):
try:
return next(bfs_paths(graph, start, goal))
except StopIteration:
return None
shortest_path(graph, 'A', 'F') # ['A', 'C', 'F']
Resources
- Depth-and Breadth-First Search
- Connected component
- Adjacency matrix
- Adjacency list
- Python Gotcha: Default arguments and mutable data structures
- PEP 380
- Generators
orig:https://eddmann.com/posts/depth-first-search-and-breadth-first-search-in-python/
网友评论