Strictly in the context of computer science, what is the difference between a sp
ID: 650091 • Letter: S
Question
Strictly in the context of computer science, what is the difference between a spanning tree, and minimum spanning tree? I read this posts but was unsatisfied with the answer because it did not seem relevant to computer science. My professor in my algorithms class makes the distinction between a spanning tree and a regular tree; but never says what the difference really is. The only thing I notice is that he uses the word spanning tree when he is talking about graphs.
Is a spanning tree simply when a graph takes on a tree structure? In other words, the raw data structure under the hood is a graph, but it takes on some characteristics of a tree? Or is it something else?
Explanation / Answer
Given a graph G, a spanning tree is a subgraph of G that (i) is a tree, and (ii) has all the vertices in G.
There can be many spanning trees for G. If you put weights on the edges, one of these spanning trees will have a minimal sum of weights. This is the minimal spanning tree.
Regular (sub)tree is just subgraph which is a tree - it doesn't have all the nodes in G: it satisfies property (i) above, but not necessarily property (ii).