First, the algorithm computes a minimum spanning tree of the graph. Note that this can be done using the procedures of Chapter 23. It can also be done by performing a breadth first search, and restricting to the edges between v and pi(v) for every v.
However saying that this is a MST is technically incorrect. An MST is defined as
A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.
Or in CLRS as
an acyclic subset T subset(E) that connects all of the vertices and whose total weight (sum all w(u,v) in T) is minimized.
Although it does have the property that the path from the source node s to any v is δ(s,v), since there are no weights this is not a minimum spanning tree. It is just a spanning tree with a special property from the BFS done it relative to one specific starting node. Whereas an actual MST is the same regardless of any 'source' which may be used to find it.
I would like to change the wording in the solution to this problem, Apologies if i should have just created a PR, but this is the first time I will have contributed to a repo and don't know the process.
The answer currently states that
However saying that this is a MST is technically incorrect. An MST is defined as
Or in CLRS as
Although it does have the property that the path from the source node s to any v is δ(s,v), since there are no weights this is not a minimum spanning tree. It is just a spanning tree with a special property from the BFS done it relative to one specific starting node. Whereas an actual MST is the same regardless of any 'source' which may be used to find it.
I would like to change the wording in the solution to this problem, Apologies if i should have just created a PR, but this is the first time I will have contributed to a repo and don't know the process.