我正在阅读有向无环图，我无法通过重新标记来理解拓扑顺序的概念。
我对拓扑顺序的一般理解是，我们找到顶点的顺序，以便我们从没有输入边的那个移动到路径上的下一个，依此类推，直到我们完成 DAG 中的所有顶点。
但我不明白重新标记有什么帮助。我的意思是重新标记顶点有什么意义？我们真的不这样打破图表吗？
任何人都可以用它的应用示例简单地解释一下吗？
问问题
513 次
1 回答
2
如果没有参考，我无法确定，但在这种情况下重新标记通常意味着改变顶点的顺序。这并不意味着改变图的拓扑结构（边和顶点），它意味着改变排序顺序。
您也可以将其视为为图形生成置换矩阵或向量。这将创建与原始图同构的图，但其中顶点 1,2,3...,n 对应于排序顺序
于 2012-05-19T20:55:31.730 回答