python中的 DFS 与 BFS

文章来源：https://eddmann.com/posts/depth-first-search-and-breadth-first-search-in-python/

这篇文章写的还是蛮好的，至少在Google中搜索关键字： BFS DFS Python， 其中的第一篇就是这个blog

Graph theory and in particular the graph ADT (abstract data-type) is widely explored and implemented in the field of Computer Science and Mathematics. Consisting of vertices (nodes) and the edges (optionally directed/weighted) that connect them, the data-structure is effectively able to represent and solve many problem domains. One of the most popular areas of algorithm design within this space is the problem of checking for the existence or (shortest) path between two or more vertices in the graph. Properties such as edge weighting and direction are two such factors that the algorithm designer can take into consideration. In this post I will be exploring two of the simpler available algorithms, Depth-First and Breath-First search to achieve the goals highlighted below:
图论，特别是图的抽象数据类型在计算机科学和数学领域得到了广泛的探索和实施。 数据结构由顶点（节点）和连接它们的边（可选择定向/加权）组成，可以有效地表示和解决许多问题域。 这个空间内最流行的算法设计领域之一是检查图中两个或更多顶点之间存在或（最短）路径的问题。 诸如边缘权重和方向等性质是算法设计者可以考虑的两个这样的因素。 在这篇文章中，我将探索两个更简单的可用算法，Depth-First和Breath-First搜索来实现下面强调的目标：

• Find all vertices in a subject vertices connected component.

• Return all available paths between two vertices.

• And in the case of BFS, return the shortest path (length measured by number of path edges).

• 查找所有的连接到目标顶点的组件中的全部顶点

• 返回两个顶点之间的所有可行的路径

• 在BFS的情况下，返回最短路径（长度为路径边的数目）

The Graph

图

So as to clearly discuss each algorithm I have crafted a connected graph with six vertices and six incident edges. The resulting graph is undirected with no assigned edge weightings, as length will be evaluated based on the number of path edges traversed. There are two popular options for representing a graph, the first being an adjacency matrix (effective with dense graphs) and second an adjacency list (effective with sparse graphs). I have opted to implement an adjacency list which stores each node in a dictionary along with a set containing their adjacent nodes. As the graph is undirected each edge is stored in both incident nodes adjacent sets.
为了清楚地讨论每个算法，我制作了六个顶点和六个入射边的连通图。 生成的图形是无向的，也没有指定的边缘权重，因为将根据遍历的路径边缘的数量来评估长度。 有两种常用的表示图的方法，第一种是邻接矩阵（对密集图有效），第二种是邻接列表（对稀疏图有效）。 我选择实现一个邻接列表，它将每个节点与一个包含其相邻节点的集合一起存储在字典中。 由于图是无向的，每个边都存储在两个事件节点相邻的集合中。

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'])}

Looking at the graph depiction below you will also notice the inclusion of a cycle, by the adjacent connections between ‘F’ and ‘C/E’. This has been purposely included to provide the algorithms with the option to return multiple paths between two desired nodes.

查看下图的描述，您还会注意到“F”和“C / E”之间的相邻连接形成一个闭环。 这是故意包括的，以便为算法提供在两个所需节点之间返回多个路径的选项。

image

Depth-First Search

深度优先搜索

The first algorithm I will be discussing is Depth-First search which as the name hints at, explores possible vertices (from a supplied root) down each branch before backtracking. This property allows the algorithm to be implemented succinctly in both iterative and recursive forms. Below is a listing of the actions performed upon each visit to a node.

我将讨论的第一个算法是深度优先搜索，正如名称提示的，在回溯之前探索每个分支的可能顶点（通过提供的根节点）。此属性允许以迭代和递归形式简洁地实现算法。下面列出了每次访问节点时执行的操作。

• Mark the current vertex as being visited.
• Explore each adjacent vertex that is not included in the visited set.
• 标记当前节点为已经访问过。
• 探索每个未包含在已访问节点集合的相邻节点

Connected Component

连接组件

The implementation below uses the stack data-structure to build-up and return a set of vertices that are accessible within the subjects connected component. Using Python’s overloading of the subtraction operator to remove items from a set, we are able to add only the unvisited adjacent vertices.

下面的实现使用堆栈数据结构来构建，然后返回一组可在与主题连接组件中访问的顶点。 使用Python的减法运算符重载来从集合中删除元素，我们只能添加未访问的相邻顶点。

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'}

The second implementation provides the same functionality as the first, however, this time we are using the more succinct recursive form. Due to a common Python gotcha with default parameter values being created only once, we are required to create a new visited set on each user invocation. Another Python language detail is that function variables are passed by reference, resulting in the visited mutable set not having to reassigned upon each recursive call.

第二个实现提供了与第一个实现相同的功能，但是，这次我们使用更简洁的递归形式。 由于只有一次创建默认参数值的常见Python问题，我们需要在每次用户调用时创建一个新的访问集。 另一个Python语言细节是函数变量通过引用传递，导致访问的可变集不必在每次递归调用时重新分配。

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    for it in graph[start] - visited:
        dfs(graph, it, visited)
    return visited

dfs(graph, 'C') # {'E', 'D', 'F', 'A', 'C', 'B'}

Paths

路径

We are able to tweak both of the previous implementations to return all possible paths between a start and goal vertex. The implementation below uses the stack data-structure again to iteratively solve the problem, yielding each possible path when we locate the goal. Using a generator allows the user to only compute the desired amount of alternative paths.

我们能够调整前面的两个实现，以返回开始和目标顶点之间的所有可能路径。 下面的实现再次使用堆栈数据结构来迭代地解决问题，在我们找到目标时产生每个可能的路径。 使用生成器将允许用户计算期望数量的替代路径。

def dfs_paths(graph, start, goal):
    stack = [(start, [start])]
    while stack:
        (vertex, path) = stack.pop()
        for it in graph[vertex] - set(path):
            if it == goal:
                yield path + [it]
            else:
                stack.append((it, path + [it]))

list(dfs_paths(graph, 'A', 'F')) # [['A', 'C', 'F'], ['A', 'B', 'E', 'F']]

The implementation below uses the recursive approach calling the ‘yield from’ PEP380 addition to return the invoked located paths. Unfortunately the version of Pygments installed on the server at this time does not include the updated keyword combination.
下面的实现使用递归方法调用'yield from'PEP380 add来返回调用的定位路径。 不幸的是，此时服务器上安装的Pygments版本不包含更新的关键字组合。

def dfs_paths(graph, start, goal, path=None):
    if path is None:
        path = [start]
    if start == goal:
        yield path
    for it in graph[start] - set(path):
        yield from dfs_paths(graph, next, goal, path + [it])

list(dfs_paths(graph, 'C', 'F')) # [['C', 'F'], ['C', 'A', 'B', 'E', 'F']]

Breath-First Search

广度优先搜索

An alternative algorithm called Breath-First search provides us with the ability to return the same results as DFS but with the added guarantee to return the shortest-path first. This algorithm is a little more tricky to implement in a recursive manner instead using the queue data-structure, as such I will only being documenting the iterative approach. The actions performed per each explored vertex are the same as the depth-first implementation, however, replacing the stack with a queue will instead explore the breadth of a vertex depth before moving on. This behavior guarantees that the first path located is one of the shortest-paths present, based on number of edges being the cost factor.

另一种称为广度优先搜索的算法使我们能够返回与深度优先搜索相同的结果，但增加了保证首先返回最短路径的能力。 使用队列数据结构以递归方式实现此算法有点棘手，因此我将仅记录迭代方法。 每个探索顶点执行的操作与深度优先实现相同，但是，使用队列替换堆栈将改为在移动之前探索顶点深度的宽度。 此行为可确保位于的第一条路径是存在的最短路径之一，基于作为成本因子的边数。

Connected Component

连接组件

Similar to the iterative DFS implementation the only alteration required is to remove the next item from the beginning of the list structure instead of the stacks last.

与迭代DFS实现类似，唯一需要的更改是从列表结构的开头而不是最后一个堆栈中删除下一个项目。

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

This implementation can again be altered slightly to instead return all possible paths between two vertices, the first of which being one of the shortest such path.

可以再次稍微改变该实现，以返回两个顶点之间的所有可能路径，其中第一个是最短的这种路径之一。

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

Knowing that the shortest path will be returned first from the BFS path generator method we can create a useful method which simply returns the shortest path found or ‘None’ if no path exists. As we are using a generator this in theory should provide similar performance results as just breaking out and returning the first matching path in the BFS implementation.

知道将从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']