数学建模习题6.3

import heapq

def prim(graph, start):
num_nodes = len(graph)
visited = [False] * num_nodes
min_heap = [(0, start, -1)]
mst_cost = 0
mst_edges = []

while min_heap:  
    weight, u, parent = heapq.heappop(min_heap)  
    if visited[u]:  
        continue  
    visited[u] = True  
    mst_cost += weight  
    if parent != -1:  
        mst_edges.append((parent, u, weight))  

    for v in range(num_nodes):  
        if not visited[v] and graph[u][v] != 0:  
            heapq.heappush(min_heap, (graph[u][v], v, u))  

return mst_cost, mst_edges  

graph = [
[0,20,0,0,15,0],
[20,0,20,60,25,0],
[0,20,0,30,18,0],
[0,60,30,0,35,10],
[0,0,0,10,15,0]
]

mst_cost, mst_edges = prim(graph, 0)
print("Prim's MST Cost:", mst_cost)
print("Prim's MST Edges:", mst_edges)

print("2023310143005")