对于下面提到的勘误,这个建议的解决方案是否正确?
Is this suggested solution for the below mentioned erratum correct?
5-2.Do下图G
的拓扑排序
此问题来自 "The Algorithm Design Manual (2nd Edition)",作者是 Steven Skiena。
因为,这个图不是DAG,拓扑排序是做不了的。
在本书的勘误表中,建议反转边缘 (F,H)
但这将使顶点 "H" 无法访问。那这个solution怎么可能
"A, B, D, E, C, H, G, I, J, F"。
解决方案有效,因为 H
没有在 H
之前提到的后继者,也没有在 H
之后提到的前任者。
这并不比图表
A <- B -> C
(其中B
是"unreachable")可以拓扑排序为
B, A, C
5-2.Do下图G
的拓扑排序此问题来自 "The Algorithm Design Manual (2nd Edition)",作者是 Steven Skiena。 因为,这个图不是DAG,拓扑排序是做不了的。 在本书的勘误表中,建议反转边缘 (F,H) 但这将使顶点 "H" 无法访问。那这个solution怎么可能 "A, B, D, E, C, H, G, I, J, F"。
解决方案有效,因为 H
没有在 H
之前提到的后继者,也没有在 H
之后提到的前任者。
这并不比图表
A <- B -> C
(其中B
是"unreachable")可以拓扑排序为
B, A, C