I was reading https://en.wikipedia.org/wiki/Reverse-delete_algorithm regarding finding MST in an undirected and connected graph G.
Where the algorithm works like this:
Start with graph G, which contains a list of edges E.
Go through E in decreasing order of edge weights.
For each edge, check if deleting the edge will further disconnect the graph.
Perform any deletion that does not lead to additional disconnection.
I'm interested in knowing is there an algorithm that starts from Empty set and returns MST.
Something maybe similar to this:
Go through E in increasing order of edge weights.
For each edge, check something... and select it if the check was true
ie some how selecting the minimum edge each time, I'm thinking maybe we should check if the new edge doesn't cause a cyclic path in the graph we have built till now then take it, is my algorithm correct?
Once the algorithm ends for sure we will have a connected graph and not only but an spanning tree, the question is it a MST?
What you've described is exactly Kruskal's algorithm, and it does indeed find an MST. At each step, we add the lowest-cost edge that does not create a cycle.