我有一個包含以下結構的數千個元素的字典：
full_dict={'A': ['B','C','D','E'],
'B':['A','C','D','E','F','X']
'X':['W','Y','Z','S'],
'S':['W','K','T'],
...}
每個字母都是一個單詞。每個單詞都可以是另一個 dict 元素的鍵和值（與其他單詞一起）。
我試圖找到從一個詞到另一個詞的“路徑”。例如，從“A”到“S”的路徑是 ABXS，因為 S 位于 X、B 中的 X 和 A 中的 B 值之間。
目前，我正在使用此代碼：
query=['A','S']
if 'S' in full_dict['A']:
print ('Found during 1st iteration')
else:
for i in full_dict['A']:
if 'S' in full_dict[i]:
print ('Found during 2nd iteration')
else:
for ii in full_dict[i]:
etc.
我做了 10 次迭代，效果很好，但我想知道是否有更好的方法來做到這一點。先感謝您。
uj5u.com熱心網友回復：
您可以使用networkx包：
import networkx as nx
full_dict={'A': ['B','C','D','E'],
'B': ['A','C','D','E','F','X'],
'X': ['W','Y','Z','S'],
'S': ['W','K','T'],
}
g = nx.DiGraph() # directed graph
for k, v in full_dict.items():
g.add_edges_from((k, to) for to in v)
print(*nx.all_simple_paths(g, 'A', 'S')) # ['A', 'B', 'X', 'S']
（嵌套）回圈通常不會作業，因為它會涉及很多嵌套（充其量），最壞的情況是，我們通常不知道我們需要多少個嵌套。
因此，人們可以考慮遞回。但這可能很復雜，因為您可能需要在諸如打破潛在的無限回圈或記住中間結果（以減少計算）之類的事情上付出很多努力。
所以在我看來，最好的方法是一個可以輕松利用資料圖結構的包。
uj5u.com熱心網友回復：
如果您在生產中執行此操作并且需要高性能、優化、所有可能的路徑等，則外部庫很有用。
如果您將此作為練習或可以確保輸入干凈（單詞串列中沒有回圈）或不想要僅用于一個操作的外部庫的東西，那么您可以嘗試遞回：
full_dict = {
'A': ['B','C','D','E'],
'B': ['A','C','D','E','F','X'],
'X': ['W','Y','Z','S'],
'S': ['W','K','T'],
}
def find_path(source, target):
for key, words in full_dict.items():
if target in words:
yield target
if key == source: # check if it's source
yield source
else:
# otherwise, look for this key as new target
yield from find_path(source, key)
break # prevent further checking of remaining items
用法：
list(find_key('A', 'S'))
# ['S', 'X', 'B', 'A']
# get it in the right order, reverse it
list(find_key('A', 'S'))[::-1]
# ['A', 'B', 'X', 'S']
該方法在單詞串列中查找目標單詞，然后生成每個關鍵字。而不是檢查源中每個單詞可能的單詞串列 - 因為這會創建許多可能到達也可能無法到達目標的鏈。
有關yield運算式的更多資訊。
請注意，Python3 的遞回限制默認為 1000。所以如果詞鏈可能更長，要么增加限制，要么使用其他方法。將限制設定為 4 并使用此修改后的 dict full_dict = {'A': ['B', 'D', 'E'], 'B': ['A', 'D', 'E', 'F', 'X'], 'X': ['W', 'Y', 'Z', 'C'], 'C': ['W', 'K', 'T', 'S'], 'S': []}，您將達到 A 到 S 的限制，現在是 5 ( ['A', 'B', 'X', 'C', 'S'])的鏈。
uj5u.com熱心網友回復：
你可以使它成為一個遞回函式：
def findLink(path,target,links):
if not isinstance(path,list): path = [path] # start path with initial word
for linked in links.get(path[-1],[]): # go through links of word
if linked == target: return path [target] # done, return full path
if linked in path: continue # avoid circular linking
foundPath = findLink(path [linked], target,links) # dig deeper
if foundPath: return foundPath # reached end on that path
輸出：
full_dict={'A': ['B','C','D','E'],
'B':['A','C','D','E','F','X'],
'X':['W','Y','Z','S'],
'S':['W','K','T'] }
print(findLink('A','S',full_dict))
['A', 'B', 'X', 'S']
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/322600.html