0%

# [Update] Minimum spanning tree

## Prime

From Wikipedia

1. Associate with each vertex v of the graph a number C[v] (the cheapest cost of a connection to v) and an edge E[v] (the edge providing that cheapest connection). To initialize these values, set all values of C[v] to +∞ (or to any number larger than the maximum edge weight) and set each E[v] to a special flag value indicating that there is no edge connecting v to earlier vertices.

2. Initialize an empty forest F and a set Q of vertices that have not yet been included in F (initially, all vertices).

3. Repeat the following steps until Q is empty:

``````a. Find and remove a vertex v from Q having the minimum possible value of C[v]
b. Add v to F and, if E[v] is not the special flag value, also add E[v] to F
c. Loop over the edges vw connecting v to other vertices w. For each such edge, if w still belongs to Q and vw has smaller weight than C[w], perform the following steps:
1). Set C[w] to the cost of edge vw
2). Set E[w] to point to edge vw
``````