从图表中扩展路径

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

这是我的看法：

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

是的，当你看到一棵树时，想想递归。:)