[Math] the total weight of the minimal spanning tree

graph theory

Here are the weights for the edges in a weighted complete graph. The numbers in the table give the weight
of the edge joining each pair of vertices. First use Prim’s algorithm to find a minimal spanning tree in this
weighted graph. Then use Kruskal’s algorithm to achieve the same thing.

PICTURE of table
enter image description here

What is the total weight of the minimal spanning tree?

I have no idea how to approach this question or what the question is asking of me.

Best Answer

Prim:

  1. start with a,
  2. find minimum weight of connected element to a, that is c (4),
  3. find minimum weight of connected element to {a, c}, that is f (11)
  4. continue to find h (5),
  5. now it becomes slightly more difficult because you also have to look vertically, but find: d (17), b (12), e (9), g (31)

Double check if I did correctly and add the numbers. If you needed the edges also, do slightly more administration..

Kruskal looks for minimum weight edges and adds as long as no cycle is formed.

We'd find (ac), (fh), (be), (cf), (bd), (df), (fg) respectively.

Related Question