Python下字典存储的图结构求边对称差异的实现方法

直接遍历两个图的所有顶点，对比每个顶点对应的边列表差异即可，不需要把列表转成集合作为字典键，完全规避unhashable type: 'list'错误，且无需引入任何第三方库：

def get_graph_sym_diff(g1, g2):
    # 取两个图的顶点并集，覆盖所有可能存在的顶点
    all_vertices = set(g1.keys()) | set(g2.keys())
    diff_g1 = {}
    diff_g2 = {}
    for vertex in all_vertices:
        # 顶点不存在时默认边列表为空
        g1_edges = g1.get(vertex, [])
        g2_edges = g2.get(vertex, [])
        # 转集合对比边是否有差异
        if set(g1_edges) != set(g2_edges):
            diff_g1[vertex] = g1_edges
            diff_g2[vertex] = g2_edges
    return diff_g1, diff_g2

测试用例 #

使用你提供的样例数据测试：

graph1 = {'1': ['3'],'2': [],'3': ['1', '7'],'7':['3']}
graph2 = {'1': ['3'],'2': ['3'],'3': ['1', '2'],'7':[]}

graph1_minus_graph2, graph2_minus_graph1 = get_graph_sym_diff(graph1, graph2)
print("graph1-graph2 =", graph1_minus_graph2)
print("graph2-graph1 =", graph2_minus_graph1)

输出结果完全符合你的预期：

graph1-graph2 = {'2': [], '3': ['1', '7'], '7': ['3']}
graph2-graph1 = {'2': ['3'], '3': ['1', '2'], '7': []}

特殊场景调整 #

如果你的图结构允许同一对顶点之间存在多条重复边，需要识别重复边的差异，只需要将对比逻辑中的集合对比改为排序后列表对比即可：

# 替换原来的if判断行
if sorted(g1_edges) != sorted(g2_edges):

内容的提问来源于stack exchange，提问作者Suneha K S