search

Claudia4 / Traveling-Salesman

TSP with Branch-and-Bound algorithm by Held and Karp
0 stars 1 forks source link

Minimum spanning tree algorithm #2

Closed Claudia4 closed 6 years ago

Claudia4 commented 6 years ago

Will we use Kruskal's or Prim's algorithm?

pro Kruskal: required edges can be used as basis for tree con Kruskal: I'm not sure about runtime

pro Prim: runtime seems better con Prim: how to enforce required edges?

AnnaA11 commented 6 years ago

Prim is easier to implement using UnionFind. One can enforce edges by setting the costs to zero and forbid edges by setting the costs to infinity.

AnnaA11 commented 6 years ago

sorry I meant Kruskal

Claudia4 commented 6 years ago

Had to change to Prim because of runtime...