Week 8 Notes: Minimum Spanning Trees / Prim's

[varmichelle]

Prim's Algorithm (Finding the Minimum Spanning Tree) O(N^2)

Algorithm: Pick a starting node, at each step pick the cheapest edge (smallest weight) and add the node to the current tree. Repeat for n-1 steps.

1. Initialize distances to infinity
   for x in 1 to N: dist[x] = INF

2. Set distance to root node to 0
   dist[start] = 0 // start can be any node

3. Pick the minimum edge
   loop through all x from 1 to N and find minimum dist that's not visited

4. Mark visited
   visited[node] = true

5. Update neighbors
   loop through neighbors of the node: dist[j] = min(dist[j], mat[x][j])