Python深度优先搜索(包括循环) [英] Depth First Search in Python (including cycles)

问题描述

所以我在StackOverflow中看到了以下有关Python中DFS算法的帖子(非常有用):

so i saw the following post in StackOverflow regarding DFS algorithm in Python(very helpful):

此python吗代码使用深度优先搜索(DFS)来查找所有路径?

我还有一个需要分析的图形(以找到两个节点之间的每条可能的路径)，但是我还需要在其中包括周期.例如，如果我有一个这样的图形:

I also have a graph that need to analyze (to find every possible path between two nodes), but I need to include the cycles there also. For example, if I have a graph like this:

graph = {'Start': ['1'],
             '1': ['2'],
             '2': ['3','End'],
             '3': ['2','End']}

我想要以下输出:

Start, 1, 2, 3, End
Start, 1, 2, End
Start, 1, 2, 3, 2, End
Start, 1, 2, 3, 2, 3, End

有没有办法更改以下代码来做到这一点?

Is there any possible way to change the following code in order to do this?

def find_all_paths(graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return [path]
        if not graph.has_key(start):
            return []
        paths = []
        for node in graph[start]:
            if node not in path:
                paths += find_all_paths(graph, node, end, path)
        return paths

print find_all_paths(graph, 'Start', 'End')

推荐答案

如注释中所述，如果允许任意循环，则算法没有理由终止.您可以做的是允许最大路径长度，并消除所有过长的路径:

As mentioned in the comment, your algorithm has no reason to terminate if you allow arbitrary cycles. What you could do is allow for a maximum path length and dismiss all paths that are too long:

def find_all_paths(graph, start, end, path=[], max_length=10):
    if len(path) >= max_length:
        return []
    path = path + [start]
    if start == end:
        return [path]
    if start not in graph:
        return []
    paths = []
    for node in graph[start]:
        paths += find_all_paths(graph, node, end, path, max_length=max_length)
    return paths

与

graph = {'Start': ['1'],
         '1': ['2'],
         '2': ['3','End'],
         '3': ['2','End']}

print find_all_paths(graph, 'Start', 'End', max_length=10)

您的算法打印:

[['Start', '1', '2', '3', '2', '3', '2', '3', '2', 'End'], ['Start', '1', '2', '3', '2', '3', '2', '3', 'End'], ['Start', '1', '2', '3', '2', '3', '2', 'End'], ['Start', '1', '2', '3', '2', '3', 'End'], ['Start', '1', '2', '3', '2', 'End'], ['Start', '1', '2', '3', 'End'], ['Start', '1', '2', 'End']]

编辑:

将 not graph.has_key 替换为更具Python风格的 start not in graph

Replaced not graph.has_key with the more pythonic start not in graph

这篇关于Python深度优先搜索(包括循环)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！