[Oops.] Vague definition of safe edge (WRT min. spanning trees)

[raenye]

Please verify that the error is present in the most recent revision before reporting. Yes, at http://jeffe.cs.illinois.edu/teaching/algorithms/book/07-mst.pdf

Chapter number or note title: 07-mst

Page number: 259, bottom.

Error description: A safe edge is defined as follows:

An edge is safe if it is the min-weight edge with exactly one endpoint in some component of F.

But F is spanning, so each of the endpoints belongs to some component of F (though not necessarily the same one).

Suggested fix (if any): Stress the order: (1) choose a component of F; (2) consider non-useless edges touching this component; (3) select such edge of minimal weight.

[echuber2]

[Edit 2: Oops, F is indeed defined as a spanning forest of the entire graph from the beginning in the algorithm. My objection here is misguided in light of that.] ~I'm not sure I see what the imprecision is. F is not necessarily spanning by definition until the algorithm is finished, because it is a subgraph of an MST. It only becomes spanning once it is as large as it can be (when it becomes the MST). So, at any given time, a particular edge may have no endpoints in any component of F, and thus it's not "safe" (although it may become safe later during the run of the algorithm). Also, note the "exactly one endpoint" part there, which is crucial (you can't pick an edge that has two endpoints already in [edit 1: the same component of] F, as it would close a loop).~

[echuber2]

Had to edit my comment above for correctness, as noted. waves to email folks

[echuber2]

So, now I see your point that here F does include all vertices from the beginning as a forest, and the word "some" could indeed seem misleading if it suggests that there's a possibility of an edge having an endpoint that is not in F (i.e., the reader could interpret that if exactly one endpoint is in "some" component of F, the other endpoint must be in "not any" component of F).

For an alternative fix, how would this be?

An edge is safe if it is the min-weight edge of which the two endpoints are in different components of F.

[raenye]

An edge is safe if it is the min-weight edge of which the two endpoints are in different components of F.

This sounds to me as the definition of Kruskal, rather than the generic method. My suggested fix above shouldn't probably be used verbatim, but it ought to be clear that the minimum is taken over edges incident to a particular component rather than all edges between components.

Perhaps define an edge as safe for a component C and then safe would mean safe for some component C?