Search code examples
c++algorithmminimum-spanning-tree

Prim's algorithm for dynamic locations

Suppose you have an input file:

<total vertices>
<x-coordinate 1st location><y-coordinate 1st location>
<x-coordinate 2nd location><y-coordinate 2nd location>
<x-coordinate 3rd location><y-coordinate 3rd location>
...

How can Prim's algorithm be used to find the MST for these locations? I understand this problem is typically solved using an adjacency matrix. Any references would be great if applicable.

Solution

  • If you already know prim, it is easy. Create adjacency matrix adj[i][j] = distance between location i and location j