字典遞歸按值分組鍵

Question

我想根據模型從一個簡單的網絡中的節點模型和一個簡單的網絡中的節點，它似乎像一個遞歸函數的工作，但我沒有任何運氣的一組字典鍵。

下面是一個簡單的表：

ID fromNode toNode 
a  1   2 
b  2   3 
c  3   4 
d  5   6 
e  6   7 
f  7   8 

從中我創建字典：

dict = {'a':(1,2), 'b':(2,3), 'c':(3,4), 'd':(5,6), 'e':(6,7), 'f':(7,8)} 

函數結果應該是類似以下列表：

list = (('a','b','c'),('d','e','f')) 

因爲'a'轉到'b'，'b'轉到'c'等等。

（PS我希望能夠解決這個問題，而無需使用圖論。）

Answer 1

如果我理解正確的話，你想從字典中表示所有斷開連接圖。

def find(dic): 
    graphes = [] 
    IDs = list(dic) 
    while IDs: 
     fromNode = dic[IDs[-1]][0] 
     graph = [] 
     graphes.append(graph) 
     findHelper(fromNode, graph, dic, IDs) 
    # merge the broken lists 
    connect = [] 
    for i in range(len(graphes)): 
     for j in range(len(graphes)): 
      if dic[graphes[i][-1]][-1] == dic[graphes[j][0]][0]: 
       connect.append((i, j)) 
    if connect: 
     for pair in connect: 
      graphes[pair[0]] = graphes[pair[0]] + graphes[pair[1]] 
     for k in connect: 
      if k[0] > pair[1]: 
       k[0] -= 1 
      if k[1] > pair[1]: 
       k[1] -= 1 
      graphes.pop(pair[1]) 

    return tuple((tuple(i) for i in graphes)) 


def findHelper(fromNode, graph, dic, IDs): 
    ID = "" 
    for i in range(len(IDs)): 
     idf = IDs[i] 
     if dic[idf][0] == fromNode: 
      ID = idf 
      toNode = dic[idf][1] 
      IDs.pop(i) 
      break 
    if ID: 
     graph.append(ID) 
     findHelper(toNode, graph, dic, IDs) 

上面的代碼可能工作。

上面的代碼雖然不是所有的id都被徵用，但是從dic中獲得一個id並檢查它是否可以找到到另一個節點的路徑：如果是，它們形成一個列表並搜索下一個節點;否則它自己形成一個列表。然後，它檢查已經形成的列表是否被拆分。例如，對於{「a」：（1,2），「b」：（2,3）}，在這個階段，代碼將產生[[「a」]，[「b」]]。代碼檢測情況並將它們合併到[[「a」，「b」]]。最後代碼將列表轉換爲元組並返回。

P.S.代碼可能包含錯誤。請指出，如果你找到他們。