Trancy

杂:补充知识点

哈密顿图:是无向图中,从一个节点可以一次经过且只经过一次图中所有的节点,这样的图叫做哈密顿图。
哈密顿回路的条件是: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)

热度(1)