python - 在邻接列表中插入一个新条目

Question

我在两组实体之间维护了一个邻接列表

dict1={'x1':[y1,y2],'x2':[y2,y3,y4]...}
dict2={'y1':[x1],'y2':[x1,x2],'y3':[x2]....}

给定一个新条目，推荐的更新字典的方法是什么。
假设条目是“x3”：[y2，y4]。
请注意，x3 不一定总是一个新顶点。

Answer 1

首先，我建议defaultdict引用一个不存在的索引会将其初始化为一个空列表。

from collections import defaultdict

dict1 = defaultdict(list)
dict1['x1'] = ['y1','y2']
dict1['x2'] = ['y2','y3','y4']
dict2 = defaultdict(list)
dict2['y1'] = ['x1']
dict2['y2'] = ['x1','x2']
dict2['y3'] = ['x2']

然后什么时候'x3':[y2,y4]进来：

dict1['x3'] = set(dict1['x3']+[y2,y4])
for y in dict1['x3']:
    dict2[y] = set(dict2[y]+'x3')

用于set消除重复值。显然，上述某些值比硬编码值更具动态性。

注意：这并没有更快，实际上可能更慢，但是 defaultdict 是避免 KeyError 的更好方法，并且您绝对不想在 adj 列表中引入重复值，因为这会损害性能，甚至可能正确性，适用于该图的任何算法。

Answer 2

为什么你不能用简单的方式来做呢？

dict1[x3] = [y2, y4]
for yi in dict1[x3]:
    if yi in dict2.keys():
        dict2[yi].append(x3)
    else:
        dict2[yi] = [x3]

Answer 3

update()下面代码中的函数怎么样：

dict1={'x1':['y1','y2'],'x2':['y2','y3','y4']}

def mkdict2():
    dict2={}
    for x,ylist in dict1.items():
        for y in ylist:
            dict2[y] = list(dict2.get(y,[])) + [x]
    return dict2

dict2 = mkdict2()

print (dict1)
print (dict2)

def update(x,ylist):
    dict1[x] = list(dict1.get(x,[])) + ylist
    for y in ylist:
        dict2[y] = list(dict2.get(y,[])) + [x]

update('x3',['y2','y4'])

print (dict1)
print (dict2)

这给出了输出：

 {'x1': ['y1', 'y2'], 'x2': ['y2', 'y3', 'y4']}
 {'y3': ['x2'], 'y2': ['x1', 'x2'], 'y1': ['x1'], 'y4': ['x2']}
 {'x1': ['y1', 'y2'], 'x2': ['y2', 'y3', 'y4'], 'x3': ['y2', 'y4']}
 {'y3': ['x2'], 'y2': ['x1', 'x2', 'x3'], 'y1': ['x1'], 'y4': ['x2', 'x3']}

我总是对持有两个包含相同数据的数据结构感到紧张，以防它们变得不一致，因此我最初使用mkdict2()to generate dict2。dict1