广度优先搜索/深度优先搜索还是有向图？

Question

我已经为此挣扎了一段时间了。给定一组节点：

nodes = { ('A','B'),
          ('B','C'),
          ('C','D'),
          ('C','E'),
          ('B','E'),
          ('C','F') }

实现以下目标的最佳方法是什么：

^{pr2}$

我可以看到：

the routes from A -> B:
A -> B
the routes from A -> C: 
A -> B -> C
A -> B -> E -> C
the routes from A -> D:
A -> B -> C -> D
A -> B -> E -> C -> D

etc...

我这么做的原因，纯粹是因为我想知道如何去做。在

我知道bfs会找到最快的路径（我想我可能会在get children函数中使用类似的方法）

但我不知道循环/递归运行该图的最佳方法。我应该使用字典来处理key/vals还是list。或设置。。。在

def make_graph(nodes):
    d = dict()
    for (x,y,*z) in nodes:
        if x not in d: d[x] = set()
        if y not in d: d[y] = set()
        d[x].add(y)
        d[y].add(x)
    return d

我在这里使用*z，因为元组实际上会包含一个float，但是现在我试图保持简单。在

def display_graph(nodes):
    for (key,val) in make_graph(nodes).items():
        print(key, val)

# A {'B'}
# C {'B', 'E', 'D', 'F'}
# B {'A', 'C', 'E'}
# E {'C', 'B'}
# D {'C'}
# F {'C'}

getchildren函数用于查找节点根的所有可能的端点：

def getchildren(noderoot,graph):
    previousnodes, nextnodes = set(), set()
    currentnode = noderoot
    while True:
        previousnodes.add(currentnode)
        nextnodes.update(graph[currentnode] - previousnodes)
        try:
            currentnode = nextnodes.pop()
        except KeyError: break
    return (noderoot, previousnodes - set(noderoot))

在这种情况下，A：

print(getchildren('A', make_graph(nodes)))

# ('A', {'C', 'B', 'E', 'D', 'F'})

Answer 1

谢谢大家，问题解决了。我需要编写的函数如下。在

def trace_graph(k, graph):
    """ takes a graph and returns a list of lists showing all possible routes from k """
    paths = [[k,v] for v in graph[k]]
    for path in paths:
        xs = path[:-1]
        x  = path[-1]
        for v in graph[x]:
            if v not in xs and path + [v] not in paths:
                paths.append(path + [v])
    paths.sort()
    return paths


for path in trace_graph('A', make_graph(nodes)):
    print(path)


['A', 'B']
['A', 'B', 'C']
['A', 'B', 'C', 'D']
['A', 'B', 'C', 'E']
['A', 'B', 'C', 'F']
['A', 'B', 'E']
['A', 'B', 'E', 'C']
['A', 'B', 'E', 'C', 'D']
['A', 'B', 'E', 'C', 'F']

Answer 2

在用程序语言编写代码之前，您需要正确地抽象问题。在

首先，您需要考虑图的属性，例如循环/非循环、有向/无向等。。在

然后你需要选择相应的方法来解决你的问题。e、 如果它是一个无环、无向连通的图，那么你可以用tree来表示它，并使用BFS或DFS来遍历它。在

最后，在您考虑了所有这些之后，您可以更容易地将其放入代码中。像您已经做的一样，您可以给每个节点一个存储所有邻居的列表，并使用BFS遍历树。在

Answer 3

我认为一个普通的树结构对于表示数据没有意义，因为它是顺序的，但不一定是有序的/排序的。使用tries（前缀树或基数树）或（可能更好）有向图可能更合适。在