python - 从图中展开路径

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

在第二个 for 循环中的某些代码中，我认为我应该检查是否有一个节点等于我要扩展的节点，给定的节点。这就是我卡住的地方。
试试这个？

if n == v:  #?

另外我在想这可能需要某种递归，对吧？但我想要一些提示来继续拼凑拼图。 :P

我应该返回一个列表，一个列表的列表吗？...如何？ :S
有小费吗？ :)
提前致谢

Answer 1

这是对 @tangentstorm's answer 的修改通过使用生成器避免引发显式异常:

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