在Python中寻找有向图路径

Question

我是一名Python初学者。因为我想从基础开始学习，所以请给我一些适合我水平的建议，避免使用高级的构造或图形库。

我有一个有向图，如下所示：

test= {
'a':    [['b'],     ['Starfleet Commander', 'Ninja Hamsters', 'Seahorse Adventures']], 
'b':    [['c'],     ['Call of Arms', 'Dwarves and Swords', 'The Movie: The Game']], 
'c':    [['e','d'],     ['Seven Schemers', 'Pirates in Java Island', 'Dwarves and Swords']], 
'd':    [[],    ['Seahorse Adventures', 'Ninja Hamsters', 'Super Mushroom Man']],
'e':    [[],            ['Seven Schemers', 'Pirates in Java Island', 'Dwarves and Swords']], 
}

现在我创建了一个递归方法，用来返回一个起点和终点之间的路径：

def path_to_friend(network, source, destination):
if source == destination:
    return [destination]
else:
    for new_source in network[source][0]:

            #print 'source> '+ source + '; new source> ' + new_source
            try:
                return [source] + path_to_friend(network, new_source, destination)
            except TypeError, e:
                print source, new_source, destination, e
                pass

然后我调用这个函数：

print path_to_friend(test, 'a', 'd')

但是当递归跟随到节点' e'时，它没有值，这就导致了错误。返回的错误信息是：

只能把列表（而不是“NoneType”）连接到列表中

如果把图中' c'的条目改成：

'c':    [['d','e'],     ['Seven Schemers', 'Pirates in Java Island', 'Dwarves and Swords']]

那么在到达'd'之前' e'就不会出现错误。

问题是，这些信息对我来说还不够，我无法理解为什么我的代码会产生这个错误。我对这门语言的一些基本概念还没有搞明白。

请给我一些建议。

Answer 1

你需要用递归的方法来解决这个问题吗？如果不需要的话，你可以使用广度优先搜索（BFS）。可以看看这个 解决问题的方法。

Answer 2

你的代码这里有很多问题。首先，如果在节点A和节点B之间没有路径，函数会返回None。

接下来，在下一次递归中，你试图添加[source] + path_to_friend(network, new_source, destination)，这实际上等同于[source] + None，所以会失败并引发你刚才遇到的错误。为了解决这个问题，我们只需要在把结果添加到最终结果之前，先检查一下path_to_friend的结果。

def path_to_friend(network, source, destination):
    if source == destination:
        return [destination]
    else:
        for new_source in network[source][0]:

                #print 'source> '+ source + '; new source> ' + new_source
                sub_path = path_to_friend(network, new_source, destination)
                if sub_path is not None:
                    return [source] + sub_path

第二个问题是，如果网络中存在循环，你可能会遇到无限循环的情况：

比如节点A访问节点B，而节点B又访问节点A……

为了解决这个问题，我们会使用一个集合来记录已经访问过的节点，并把这个集合传递给函数。

def path_to_friend(network, source, destination, visited=None):
    if source == destination:
        return [destination]
    else:
        visited = visited or set()
        for new_source in network[source][0]:
                if new_source not in visited: # check if the next node was already visited
                    visited.add(new_source) # add the next node to the list of visited nodes
                    #print 'source> '+ source + '; new source> ' + new_source
                    sub_path = path_to_friend(network, new_source, destination, visited)
                    if sub_path is not None:
                        return [source] + sub_path