数据结构 - 拓扑排序

2021年5月4日 1点热度 0条评论 来源: 陆讯

应用背景

学生选修课程问题
顶点——表示课程
有向弧——表示先决条件,若课程i是课程j的先决条件,则图中有弧(i,j)
学生应按怎样的顺序学习这些课程,才能无矛盾、顺利地完成学业——拓扑排序

     拓扑序列是有向无环图中各顶点构成的有序序列。该序列满足如下条件:如果图中一顶点vi到另一顶点vj存在一条路径,那么vj在此图的拓扑排序序列中位于vi之后。

有向无环图(DAG)和 AOV网

有向无环图”(Directed Acyclic Graph,简称DAG
AOV网 (Activity On Vertex network): 一个“可行的” AOV 网络必须是DAG。否则图中有回路,从而就不能确定回路中的活动究竟哪个先实施。
顶点表示活动,
弧表示活动间的优先关系,
注意:
AOV网中的弧表示活动之间存在某种制约关系:若

void ToplogicalSort ( Graph G, int TopNum[ ] )
{
    int Counter;    /* 拓扑序号,用以标识每个顶点输出的次序*/
    int v, w;
    int *InDegree = (int *)malloc( G.n * sizeof(int) );
    GetInDegree(G, InDegree);   /* 计算图G中各顶点的入度 */
    for( Counter = 0; Counter < G.n; Counter++ ) {
        v = FindNewVertexOfDegreeZero( );   
        /* 查找入度为0的顶点,若找到,则返回顶点在顶点数组的下标。若找不到入度为0的顶点,返回-1 */
        if ( v == -1 ) {
             printf( “图存在环路”);
             break;
        }
        TopNum[v] = Counter;
        for( G中关于v 的每个邻接点w )
           Indegree[w]--;  /* 与顶点v相连的各顶点的入度减1 */
    }
}
void ToplogicalSort ( GraphAdjList GL, int * TopNum )
{    
    Queue queue;    EdgeNode *p;     int Counter = 0;    int v, w;
     //int *InDegree = (int *)malloc( G.n * sizeof(int) );
   // GetInDegree(G, InDegree); /* 计算图G中各顶点的入度 */
     queue = InitQueue( GL->numVertexes ); /* 创建空队列 */
     for( v = 0; v <GL->numVertexes; v++ )
          if( GL->adjList[v].in==0 )        EnQueue( &queue, v );
     while( ! QueueEmpty(queue) ) {
           v = DeQueue( &queue);
           TopNum[v] = ++Counter;      /* 赋顶点拓扑排序序号 */
           for( p=GL->adjList[v].firstedge;p!=NULL;p=p->next)
              if( --GL->adjList[p->adjvex].in == 0 )
                  EnQueue( &queue, p->adjvex );
      }
      if( Counter != GL->numVertexes )      
          printf( "图存在环路\n" );
      DisposeQueue(&queue);    /* 释放队列空间*/
      //free(InDegree);
}

关键路径

    与AOV网相对应的是AOE(Activity On Edge) ,是边表示活动的有向无环图。
    顶点表示事件(Event),每个事件表示在它之前的活动已完成,在它之后的活动可以开始;
    弧表示活动,弧上的权值表示相应活动所需的时间或费用

AOV网与AOE网

拓扑排序主要是为解决一个工程能否顺利进行的问题。
关键路径是解决工程完成需要的最短时间问题。
AOV网与AOE网的区别:
AOV网,顶点表示活动,边描述活动之间的制约关系
AOE网,边上的权值表示活动持续的时间,
建立在活动之间制约关系没有矛盾的基础上,
讨论完成整个工程至少需要多少时间;或者为缩短完成工程所需时间,应当加快哪些活动等问题。

路径长度—路径上各活动持续时间之和
关键路径—从源点到汇点具有最大路径长度的路径
关键活动—关键路径上的活动。关键活动是影响整个工程的关键,延迟就会影响整个工期的活动。
最早发生时间—设v0是起点,从v0到vi的最长路径长度称为事件vi的最早发生时间,即是以vi为尾的所有活动的最早发生时间。

求AOE中关键路径和关键活动

⑴ 算法思想
① 利用拓扑排序求出AOE网的一个拓扑序列;
② 从拓扑排序的序列的第一个顶点(源点)开始,按拓扑顺序依次计算每个事件的最早发生时间ve(i) ;
从拓扑排序的序列的最后一个顶点(汇点)开始,按逆拓扑顺序依次计算每个事件的最晚发生时间vl(i) ;
求出各活动的最早发生时间e(i)和最晚发生时间l(e),同时求出ai的时间余量,时间余量=0的那些活动就是关键活动。

最短路径

用带权的有向图表示一个交通运输网,图中:
顶点:城市
边:城市间的交通联系
权:此线路的长度或沿此线路运输所花的时间或费用等
问题:
两地之间是否有通路?
在有多条通路的情况下,哪条最短?
将一条路径的起始顶点称为源点,最后一个顶点称为终点。

单源点最短路径

对于给定的有向图G=(V,E)及单个源点V0,求V0到G的其余各顶点的最短路径。
针对单源点的最短路径问题,Dijkstra提出了一种按路径长度递增次序产生最短路径的算法,即迪杰斯特拉(Dijkstra)算法。

求最短路径步骤

初使时令 S={V0},T={其余顶点},T中顶点对应的距离值
若存在 V0,Vi,为V0,Vi弧上的权值
若不存在 V0, Vi,为
从T中选取一个其距离值为最小的顶点W,加入S
对T中顶点的距离值进行修改:若加进W作中间顶点,从V0到Vi的距离值比不加W的路径要短,则修改此距离值
重复上述步骤,直到S中包含所有顶点,即S=V为止

算法实现
图用带权邻接矩阵存储
数组dist[ ]存放当前找到的从源点V0到每个终点的最短路径长度(这些路径中间只经过集合S中的顶点),其初态为图中直接路径权值
数组pre[ ]表示从V0到各终点的最短路径上,此顶点的前一顶点的序号;若从V0到某终点无路径,则用0作为其前一顶点的序号

    原文作者:陆讯
    原文地址: https://blog.csdn.net/wangzi11322/article/details/45456827
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。