I’m trying to find an efficient algorithm that will find me the minimum spanning tree of an undirected, weighted graph of this particular form:
My idea was a recursive solution: Suppose the algorithm recieve the graph with n as a parameter,
if n==2 then: take the lower cost path between vo-->v1-->v2 and v0-->v2 if n==1 then: take the lower cost path between v0-->v2-->v1 (if v2 exists) and v0-->v1 else: - recursivly call the algorithm for n-1 - take the lower cost edge between v0-->vn and v(n-1)-->vn
I’m really not sure wheather this algorithm is correct, i was trying to prove this by induction and got a bit stuck at the base, which got me thinking maybe the algorithm is flawed.
Any suggestions would be much appreciated.