关于最小生成树的应用

Question

已知带权无向图（如下所示），求最小生成树。Program2用图要求输出：(1)所有的边及权值，如：（‘a’,’b’,10）…(2)最小生成树所包含的边，如：（’a’,‘c’,‘weight’:8）…

Answer 1

prim算法

def findTree(G:dict):
    start = list(G.keys())[0]
    choice = [(start, i, j) for i, j in G[start].items()]
    choice.sort(key=lambda x:x[2])
    tree = list()
    seen = {start}
    while choice:
        node = choice.pop(0)
        if node[1] not in seen:
            seen.add(node[1])
            line = sorted([node[0],node[1]])
            line.append(node[2])
            tree.append(line)
            for i, j in G[node[1]].items():
                choice.append((node[1],i,j))
            choice.sort(key=lambda x:x[2])
    return tree

if __name__ == "__main__":
    graph = {
    "a":{"b":10, "c":8, "f":5},
    "b":{"a":10, "d":9, "f":7},
    "c":{"a":8, "e":10, "f":17},
    "d":{"b":9, "e":11, "f":12, "g":4},
    "e":{"c":10, "d":11, "f":3, "g":16},
    "f":{"a":5, "b":7, "c":17, "d":12, "e":3},
    "g":{"d":4, "e":16}
    }
    lines = set()
    for node, value in graph.items():
        for i, j in value.items():
            temp = sorted([node,i])
            temp.append(j)
            lines.add(tuple(temp))
    print(lines)
    tree = findTree(graph)
    print(tree)