从图中扩展路径

Question

我知道有一些模块可以处理这种结构，但我更喜欢自己学习东西是怎么运作的。

所以……我一直在尝试从一个图中扩展路径，比如下面这个例子：

g = dict(
    s=['a','d','s'],
    a=['s','d','b'],
    d=['s','a','e'],
    b=['a','e','c'],
    e=['d','b','f'],
    f=['e','g'],
    c=['b'],
    g=['f'])

到目前为止，我可以查看给定节点的邻居，方法是：

def vecinosDe(n = ''):
    return g[n]

我希望每次调用一个函数时，给它一个图中的节点作为参数，它能返回与这个节点相连的其他节点的列表。
然后把这个生成的列表再传回同一个函数，返回与这个列表中的节点相连的节点，依此类推，直到到达'g'节点。
我也知道需要检查与给定节点相连的节点是否有循环（递归）。

这是我目前写的代码：

def expandir(n = '', lista = []):
    lista.append([n]) #or lista = lista + [n]?
    for v in g[n]:
        for i in range(len(lista)): #?
            lista[i].append(v)
    return lista

这是我遇到的情况，我知道这不太好，哈哈。

>>> expandir('s')
[['s', 'd', 'a', 's']]
>>> expandir('d')
[['S', 'D', 'A', 'S', 'S', 'A', 'E'], ['D', 'S', 'A', 'E']]

在第二个循环的某个地方，我觉得我应该检查是否有一个节点等于我想要扩展的节点，也就是给定的节点。在这里我卡住了。
试试这个？

if n == v:  #?

我还在想，这可能需要某种递归，对吧？但我希望能得到一些建议，继续把这个拼图拼起来。:P

我应该返回一个列表，还是一个列表的列表？怎么做呢？:S
有什么建议吗？ :)
提前谢谢你们！

Answer 1

这是我对这个问题的看法：

graph = g # from your code

def findPath(graph, node, path=tuple(), end='g'):
    for key in graph[node]:
        next = path + (key,)
        if key == end:
            raise Exception("Found it! Path is: %s" % '.'.join(path))
        elif key in path:
            pass # avoid loops
        else:
            # print next # if you want to see what it's doing
            findPath(graph, key, next, end)
    else: # no break/raise at this level
        if len(path) == 0: print "no path found."

findPath(graph, 's')

我觉得你主要的问题是[除了变量名真的太难读了 :)]，就是你的路径（lista）有一个默认参数是[]。这样不好，因为默认参数是可变的

我还在想，这可能需要某种递归，对吧？不过我希望能得到一些建议，继续把这个难题拼凑起来。:P

没错，当你看到树形结构时，就要想到递归。:)

Answer 2

在这个链接 http://eloquentjavascript.net/chapter7.html 中，有一个非常好的JavaScript示例，讲的是路径搜索的内容。它会一步一步教你如何用JavaScript来开发这个算法。读一读这个内容，可以帮助你理解它是怎么工作的。

Answer 3

这是对 @tangentstorm的回答 的一个修改版，使用生成器来避免显式抛出异常：

def pathiter(adjacent_vertexes, start, end, path=None):
    if path is None: path = (start,)

    for vertex in adjacent_vertexes[start]:
        if vertex == end:
            yield path + (vertex,)
        elif vertex not in path:
            for p in pathiter(adjacent_vertexes, vertex, end, path + (vertex,)):
                yield p

示例：

end = 'g'
for v in g:
    path = next(pathiter(g, v, end), None)
    if path is not None:
        print ' → '.join(path)
    else:
        print "no path between %s and %s" % (v, end)

输出

a → s → d → e → f → g
c → b → a → s → d → e → f → g
b → a → s → d → e → f → g
e → f → g
d → s → a → b → e → f → g
g → f → g
f → g
s → a → d → e → f → g

你可以打印出所有路径：

for v in graph:
    print "%s ⇢ %s:" % (v, end)
    path = None
    for path in pathiter(graph, v, end):
        print '\t'+' → '.join(path)
    if path is None:
        print "no path between %s and %s" % (v, end)

输出

a ⇢ g:
    a → s → d → e → f → g
    a → d → e → f → g
    a → b → e → f → g
c ⇢ g:
    c → b → a → s → d → e → f → g
    c → b → a → d → e → f → g
    c → b → e → f → g
b ⇢ g:
    b → a → s → d → e → f → g
    b → a → d → e → f → g
    b → e → f → g
e ⇢ g:
    e → f → g
d ⇢ g:
    d → s → a → b → e → f → g
    d → a → b → e → f → g
    d → e → f → g
g ⇢ g:
    g → f → g
f ⇢ g:
    f → g
s ⇢ g:
    s → a → d → e → f → g
    s → a → b → e → f → g
    s → d → a → b → e → f → g
    s → d → e → f → g