CODEWITHSUNDEEP
algorithmgraphminimum-spanning-tree
Ashot
Ashot

Reputation: 10959

Recursive minimal spanning tree algorithms

Is this a right algorithm for finding minimal spanning tree.

Divide Graph into 2 equally connected parts. Find its minimal spanning trees. Connect them using the smallest edge that connects them. I am trying to get counterexample of this algorithm, but can't.

Upvotes: 3

Views: 3309

Answers (2)

Emilio Amaya
Emilio Amaya

Reputation: 11

You have described a divide and conquer algorithm which will not work when determining an MST. Sneftel provided a good counter-example and recursively dividing the graph into two connected parts would be extremely costly.

Instead, a good approach to finding an MST would be to use a greedy algorithm such as Prim's algorithm. We know a greedy algorithm will work because this problem exhibits optimal substructure. For this algorithm, you will want to represent your graph as an adjacency list. First, start at an arbitrary node and add it to a visited list. Add all edges from this node into a min-heap. Include the cheapest edge in your MST and add the connecting node to your visited list. From that node add all edges to your min-heap and then select the cheapest edge to a node that has yet to be visited. Continue doing so until all nodes are visited. Once that is done you have your MST.

You can use other data structures to store the graph and the visited edges, but the ones I have outlined above will maximize the runtime. If we analyze the run-time with these data structures we can see that the runtime is O(E log V) which is the time to update the cost of the elements and maintaining your heap after an edge has been removed. More specifically O(log V) to fix the heap and that is done E number of times.

I also found this quick 2-minute video that outlines Prim's algorithm with an example: Prim's Algorithm in 2 Minutes

I hope this information is helpful!

Upvotes: 1

Sneftel
Sneftel

Reputation: 41454

Consider a four-node graph, connected in a square, with the left edge having cost 10 and all other edges having cost 1. If you divide the graph into left and right for your recursive step, you will end up with a spanning tree of cost 12, instead of cost 3.

MST is not well-adapted to "divide-and-conquer" algorithms. The closest thing is probably the Reverse-Delete algorithm; whenever you fail to remove an edge (because it would disconnect the graph), you can think of the remaining steps as executing recursively on the two sides of that edge.

Upvotes: 6

Related Questions