杂：补充知识点
哈密顿图：是无向图中，从一个节点可以一次经过且只经过一次图中所有的节点，这样的图叫做哈密顿图。
哈密顿回路的条件是：1.是一个封闭的图形 2.任意一对节点之间皆可达。
经过图（有向图或无向图）中所有顶点一次且仅一次的通路称为哈密顿通路。
[任意一点都满足]经过图中所有顶点一次且仅一次的回路称为哈密顿回路。
具有哈密顿回路的图称为哈密顿图，具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图。
平凡图是哈密顿图。
拓扑排序
定义：在一个有向图中，对于任意一对点如果存在u到v的路径，那么在拓扑排序后u一定在v前面。
偏序/全序
偏序：任意两个之间要么是确定关系，某某在某某之前；要么是不确定关系，【一定不存在矛盾关系】（即环路，所以强调无环）
全序：在偏序的基础上，满足任意两点之间的关系是确定的。
++一个图能被拓扑排序的充要条件是它！是！一！个！有向！无环！图！
拓扑排序唯一性的条件是，所有节点都有全序关系。
【一】无前趋的顶点优先的拓扑排序方法
该方法的每一步总是输出当前无前趋(即人度为零)的顶点，其抽象算法可描述为：
NonPreFirstTopSort(G){//优先输出无前趋的顶点
while(G中有人度为0的顶点)do{
从G中选择一个人度为0的顶点v且输出之；
从G中删去v及其所有出边；
}
if(输出的顶点数目<|V(G)|)
//若此条件不成立，则表示所有顶点均已输出，排序成功。
Error("G中存在有向环，排序失败！")；
}
注意：
无前趋的顶点优先的拓扑排序算法在具体存储结构下，为便于考察每个顶点的人度，可保存各顶点当前的人度。为避免每次选入度为0的顶点时扫描整个存储空
间，可设一个栈或队列暂存所有入度为零的顶点：
在开始排序前，扫描对应的存储空间，将人度为零的顶点均入栈(队)。以后每次选人度为零的顶点时，只需做出栈(队)操作即可。
【二】同理，还有无后继顶点优先的拓扑排序
【三】算法求精
在对该算法求精时，可用逆邻接表作为G的存储结构。设置一个向量outdegree[0..n-1]或在逆邻接表的顶点表结点中增加1个出度域来保存各顶点当前的出度；
设置一个栈或队列来暂存所有出度为零的顶点。除了增加一个栈或向量T来保存输出的顶点序列外，该算法完全类似于NonPreFirstTopSort。
ps：woc逆邻接表出度域这么low的你管它叫优化？！
【四】利用深度优先遍历对DAG拓扑排序
当从某顶点v出发的DFS搜索完成时，v的所有后继必定均已被访问过(想像它们均已被删除)，此时的v相当于是无后继的顶点，因此在DFS算法返回之前输出顶点v
即可得到 DAG的逆拓扑序列。
其中第一个输出的顶点必是无后继(出度为0)的顶点，它应是拓扑序列的最后一个顶点。若希望得到的不是逆拓扑序列，同样可增加T来保存输出的顶点。若假设
T是栈，并在DFSTraverse算法的开始处将T初始化，
利用DFS求拓扑序列的抽象算法可描述为：
void DFSTopSort(G，i，T){
//在DisTraverse中调用此算法，i是搜索的出发点，T是栈
int j；
visited[i]=TRUE； //访问i
for(所有i的邻接点j)//即<i，j>∈E(G)
if(!visited[j])
DFSTopSort(G，j，T)；
//以上语句完全类似于DFS算法
Push(&T，i)； //从i出发的搜索已完成，输出i
}
只要将深度优先遍历算法DFSTraverse中对DFS的调用改为对DFSTopSort的调用，即可求得拓扑序列T。其具体算法不难从上述抽象算法求精后得到。
若C中存在有向环，则不能正常工作。
评论(1)