In the proof of correctness I read of prim's algorithm here, triangle inequality was not used once. So prim's algorithm should be valid for non-metric graphs(those that do not satisfy triangle inequality) too. So you can apply prim's algorithm to find the MST for a connected weighted undirected graph.
Is there a minimum spanning tree in a non-planar graph?
-
31-05-2022 - |
Question
Is there a minimum spanning tree in a non-planar graph? I have read about prim algorithm and triangle inequality and my graph doesn't satisfy the triangle inequality?
Solution
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow