CODEWITHSUNDEEP
algorithmgraphtreeminimum-spanning-tree
Ronak Agrawal
Ronak Agrawal

Reputation: 1066

Trying to create an algo that creates a spanning tree with least number of edges removed from a unweighed graph

I am trying to create an algo that will get a spanning tree with root node such that, the spanning tree will have least number of edges removed from Original Graph G.

Thanks in advance

Upvotes: 1

Views: 65

Answers (1)

Abhishek Bansal
Abhishek Bansal

Reputation: 12715

For any connected graph, the spanning tree always contains n-1 edges where n is the number of nodes in the graph. So you will have to remove all the remaining edges. (If I have understood your question correctly)

Even for disconnected graphs, the number of edges in a spanning tree is defined by the number of components and number of nodes in each component.

Upvotes: 3

Related Questions