摘要: 下面我先说以下拓扑排序：
严蔚敏《数据结构》上的定义是：由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
直观的说偏序指集合中仅有部分成员之间可比较，而全序指集合中全体成员之间均可比较。
拓扑排序的具体做法是：
1.在有向图中选择一个没有前驱（入度为0）的顶点，输出
2.从图中删除该顶点和所有以它为尾的弧，并更新相关点的入度
3.重复1，2步，直到所有顶点都被输出，或者发现图中存在回路。
阅读全文
posted @
2012-08-16 19:19 小鼠标 阅读(1776) |
评论 (0) |
编辑 收藏