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

みなさん、ありがとうございました。問題は解決しました。私が書く必要のある関数は次のとおりです。

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 に答える
1

プログラム言語でコーディングする前に、問題を適切に抽象化する必要があります。

まず、循環/非循環、有向/無向など、グラフのプロパティについて考える必要があります。

次に、それに応じて問題を解決する方法を選択する必要があります。たとえば、非循環で無向の接続グラフの場合、グラフをツリーとして表現し、 BFS または DFS を使用してトラバースできます。

最後に、これらすべてを熟考した後は、はるかに簡単にコードに組み込むことができます。すでに行ってきたことと同様に、各ノードにすべての近隣ノードを格納するリストを与え、BFSを使用してツリーをトラバースできます。

于 2012-06-11T21:26:16.683 に答える
0

通常のツリー構造は、データを表すのに意味があるとは思いません。データが連続しているが、必ずしも順序付け/ソートされているとは限らないためです。試行 (プレフィックスまたは基数ツリーのいずれか) または (おそらくより良い) 有向グラフのいずれかを使用する方がおそらくより適切です。

于 2012-06-11T21:24:01.357 に答える
0

必要以上に物事を複雑にしている可能性があると思います。xvatar が言ったように、あなたが表現しているデータのタイプについて考えてください。

基本的な有向グラフの場合、辞書は理にかなっています。parent: 子のリストを格納するだけです。

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 に答える