2

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

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

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

                          A
                          |
                          B
                 _________|_________
                 |                  |
                 C                  E
            _____|_____             |
            |    |     |            C
            D    E     F        ____|____
                                |        |
                                D        F

我可以在哪里看到：

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 函数中使用了类似的东西）

但我不知道循环/递归运行图形的最佳方法。我应该使用字典并使用键/值还是列表。或者套...

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 因为元组实际上会包含一个浮点数，但目前我正试图让事情变得简单。

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'})
4

4 回答 4

1

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

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

然后你需要选择一种方法来相应地解决你的问题。例如，如果它是一个无环、无向和连通图，那么您可以将图表示为一棵树并使用 BFS 或 DFS 来遍历它。

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

于 2012-06-11T21:26:16.683 回答
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']
于 2012-06-12T10:46:55.593 回答
0

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

于 2012-06-11T21:24:01.357 回答
0

我认为你可能会让事情变得比他们需要的更复杂。想想你所代表的数据类型，就像 xvatar 所说的那样。

对于基本的有向图，字典是有意义的。只需存储父级：子级列表。

nodes = [ ('A','B'),
          ('B','C'),
          ('C','D'),
          ('C','E'),
          ('B','E'),
          ('C','F') ]

from collections import defaultdict
d = defaultdict(list)
for node in nodes:
    d[node[0]].append(node[1])

从任何根节点查找所有可访问的子节点很简单：

def getchildren(root, graph, path=[]):
    path = path + [root]
    for child in graph[root]:
        if child not in path:  #accounts for cycles
            path=getchildren(child, graph, path)
    return path

调用时：

>>> print getchildren('A',d)
['A', 'B', 'C', 'D', 'E', 'F']
>>> print getchildren('C',d)
['C', 'D', 'E', 'F']
于 2012-06-11T21:43:25.903 回答