按值对组键的字典递归

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。这些代码可能包含错误。如果找到它们，请指出它们。