廣度優先搜索/深度優先搜索還是定向圖？

Question

我一直在努力與此一段時間了。給定一組節點：

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找到最快的路線，（我想我可能會用在讓孩子功能類似的東西）

，但我不知道循環的最佳方式/遞歸地在圖上運行。我應該使用字典並使用鍵/ val或列表。或設置...

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)) 

在這種情況下：

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

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

Answer 1

在使用程序語言進行編碼之前，您需要正確提取問題。

首先，你需要考慮你的圖形的屬性，如週期/非週期，定向/非定向等。

然後，你需要選擇一個方式來相應地解決您的問題。例如如果它是一個非循環的，無向和連通的圖，那麼您可以將該圖表示爲tree，並使用BFS或DFS來遍歷它。

最後，在您思考完所有這些之後，您可以更輕鬆地將它放入代碼中。就像你已經做的一樣，你可以給每個節點一個存儲所有鄰居的列表，並使用BFS遍歷樹。

Answer 2

我不認爲一個普通的樹結構有道理用於表示您的數據，因爲它是順序的，但不一定是排序/排序的。使用任一嘗試（前綴或基數樹）或（可能更好）有向圖可能更合適。

Answer 3

我想你可能會讓事情比他們需要的更復雜。考慮一下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'] 

Answer 4

謝謝大家，問題解決了。我需要寫的功能如下。

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