Prim Growth Order

Problem

Record the order in which nodes join Prim's minimum spanning tree grown from node 0.

Push candidate edges into a heap keyed by (weight, node) so ties always pick the smallest node index, and ignore stale entries for visited nodes. edges is an undirected [u, v, w] list with positive weights. If the graph is disconnected, return an empty list instead of a partial order.

Hint

Heap entries are (weight, node); skip any node that already joined the tree.

Test cases

case 1

in: [4,[[0,1,1],[1,2,2],[2,3,3],[0,3,10]]]

expected: [0,1,2,3]

case 2

in: [4,[[0,1,5],[0,2,1],[1,3,1],[2,3,5]]]

expected: [0,2,1,3]

case 3

in: [3,[[0,1,2]]]

expected: []

case 4

in: [3,[[0,1,1],[1,2,1],[0,2,5]]]

expected: [0,1,2]

case 5

in: [1,[]]

expected: [0]

Starter codePython

import heapq

def prim_growth_order(n, edges):
    # Your code here
    pass

5 test cases · run your code against them in the editor