iOS算法——图的拓扑排序

2022-01-14 14:46:59 浏览数 (2)

拓扑排序基础篇

1.1 什么是有向无环图？

一个 无环的有向图称为有向无环图（Directed Acycline Graph），简称DAG图，所以直接看图。

图中最左边的是有向树，中间的是有向无环图，最右则的是有向图（因为图中BED三个顶点之间构成一个有向环，ACEB也存在环路）。

1.2 什么是 “活动” ？

所有的工程或者某种流程都可以分为若干个小的工程或者阶段，我们称这些小的工程或阶段为“活动”。打个比方，如何把一只大象装到冰箱里，很简单，分三步。第一，打开冰箱门；第二，将大象装进去；第三，关上冰箱门。这三步中的每一步便是一个 “活动” 。

1.3 什么是AOV网？

在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系的有向图 称为顶点表示活动的网（Activity On Vertex Network），简称AOV网。

AOV网中的弧表示活动之间存在的某种制约关系，比如上面说到将大象装入冰箱，必须先打开冰箱门，才能将大象装进去，大象装进去才能关上冰箱门，从而完成我们的任务。还有一个经典的例子那就是选课，通常我们是学了C语言程序设计，才能学习数据结构，这里的制约关系就是课程之间的优先关系。

1.4 什么是拓扑序列?

设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列V0,V1......Vn满足若从顶点Vi到Vj有一条路径，则在顶点序列中顶点Vi必在顶点Vj之前。则我们称这样的顶点序列为一个拓扑序列。

1.5 什么是拓扑排序呢？

所谓的拓扑排序，其实就是对一个有向无环图构造拓扑序列的过程。当然这里的说法不够正式，也是为了理解方便，拓扑排序的官方定义是这样的：由某个集合上的一个偏序得到该集合上的一个全序的操作过程称为拓扑排序。

拓扑排序算法解析

拓扑排序的算法步骤很简单，就是两步：

  • (1) 在有向图中选一个没有前驱的顶点且输出之。
  • (2) 从图中删除该顶点和所有以它为尾的弧。
  • 重复上述两步，直至全部顶点均已输出，或者当前图不存在无前驱的顶点为止，后一种情况说明有向图中存在环。

2.1 有向无环图的拓扑排序

  • 第一步：在有向图中选择一个没有前驱的顶点并输出；观察图中的顶点，发现顶点V1和顶点V6都是没有前驱的顶。假设我们先输出顶点V1（当然也可以先输出V6，从此处也就可以看出拓扑序列可以有多个）。此时拓扑序列为[V1];
  • 第二步：从图中删除顶点V1和所有以它为尾的弧。
  • 之后的步骤就是重复一二两步，我们接着看。
  • 第三步：在有向图中选择一个没有前驱的顶点并输出；图中没有前驱的顶点为V6和顶点V3（同样的道理，我们可以选择这两个顶点的任何一个，假设我们选择顶点V6）。此时拓扑序列为[V1,V6];
  • 第四步：删除顶点V6和所有以它为尾的弧。
  • 第五步：在有向图中选择一个没有前驱的顶点并输出；图中没有前驱的顶点为V4和顶点V3（同样的道理，我们可以选择这两个顶点的任何一个，假设我们选择了顶点V4）。此时拓扑序列为[V1,V6,V4];
  • 第六步：删除顶点V4和所有以它为尾的弧。
  • 第七步：在有向图中选择一个没有前驱的顶点并输出；图中没有前驱的顶点为V3。此时拓扑序列为[V1,V6,V4,V3];
  • 第八步：删除顶点V3和所有以它为尾的弧。
  • 第九步：在有向图中选择一个没有前驱的顶点并输出；图中没有前驱的顶点为V2和V5（同样的道理，我们可以选择这两个顶点的任何一个，假设我们选择了顶点V2） 。此时拓扑序列为[V1,V6,V4,V3,V2];
  • 第10步：删除顶点V2和所有以它为尾的弧。
  • 第11步：在有向图中选择一个没有前驱的顶点并输出；图中没有前驱的顶点为V5，选择并输出，此时所有的顶点均已经输出，算法结束，我们就得到了下图中的一个拓扑序列 ，整个过程便叫做 拓扑排序。

2.2 有向有环图的拓扑排序解析

  • 第一步：在有向图中选择一个没有前驱的顶点并输出；图中没有前驱的顶点为A；此时拓扑序列为[A];
  • 第二步：删除顶点A和所有以它为尾的弧。
  • 第三步：在有向图中选择一个没有前驱的顶点并输出；图中没有前驱的顶点为C。此时拓扑序列为[A,C];
  • 第四步：删除顶点B和所有以它为尾的弧。
  • 第五步：在有向图中选择一个没有前驱的顶点并输出；发现当前图不存在无前驱的顶点，但拓扑序列中并未输出所有的顶点，所以剩下的顶点构成了环，也证明了该有向图存在环。

2.3 拓扑排序算法实现

代码语言：javascript复制
// 拓扑排序算法
// 若GL无回路，则输出拓扑排序序列并返回OK，否则返回ERROR
Status TopologicalSort(GraphAdjList GL)
{
   EdgeNode *e;
   int i, k, gettop;
   int top = 0;  // 用于栈指针下标索引
   int count = 0;  // 用于统计输出顶点的个数
   int *stack;   // 用于存储入度为0的顶点

   stack = (int *)malloc(GL->numVertexes * sizeof(int));

   for( i=0; i < GL->numVertexes; i   )
   {
      if( 0 == GL->adjList[i].in )
      {
         stack[  top] = i; // 将度为0的顶点下标入栈
      }
   }

   while( 0 != top )
   {
      gettop = stack[top--]; // 出栈
      printf("%d -> ", GL->adjList[gettop].data);
      count  ;    

      for( e=GL->adjList[gettop].firstedge; e; e=e->next )
      {
         k = e->adjvex;
   // 注意：下边这个if条件是分析整个程序的要点！
   // 将k号顶点邻接点的入度-1，因为他的前驱已经消除
   // 接着判断-1后入度是否为0，如果为0则也入栈
         if( !(--GL->adjList[k].in) ) 
         {
            stack[  top] = k;
         }
      }
   }

   if( count < GL->numVertexes ) // 如果count小于顶点数，说明存在环
   {
      return ERROR;
   }
   else
   {
      return OK;
   }
}

（滑动显示更多）

关键路路径算法

3.1 关键路路径求解过程⼏几个核⼼心参数

  • 事件最早发生的时间etv(earliest time of vertex):即顶点Vk 的最早发⽣生时间;
  • 事件最晚发⽣时间ltv(latest time of vertex): 即顶点Vk 的最晚发生时间,也就是每个顶点对应的事件最晚需要开始的时间,超出此时间将会延误整个工期;
  • 活动的最早开工时间ete(earliest time of edge); 即弧Ak 的最早发⽣生时间;
  • 活动的最晚开工时间lte(latest time of edge); 即弧Ak 的最晚发⽣生时间,也就是不推迟⼯期的最晚开工时间;

3.2 AOE ⽹网关键名称解释

  • 路径上各个活动所持续的时间之和称为路径长度
  • 从源点到汇点具有最⼤的路径叫关键路径
  • 在关键路路径上的活动叫关键活动

3.3 AOV网的存储结构（邻接表）

使用AOV网来存储图信息

代码语言：javascript复制
//边表结点
  typedef struct EdgeNode
{
//邻接点域，存储该顶点对应的下标
int adjvex;
//⽤用于存储权值，对于⾮非⽹网图可以不不需要
int weight;
//链域，指向下⼀一个邻接点
struct EdgeNode *next;
}EdgeNode;
//顶点表结点
  typedef struct VertexNode
{
//顶点⼊入度
  int in;
//顶点域，存储顶点信息
  int data;
//边表头指针
  EdgeNode * firstedge;
 }VertexNode, AdjList[MAXVEX];

 typedef struct
{
    AdjList adjList;
     //图中当前顶点数和边数
    int numVertexes ,numEdges;
 }graphAdjList,*GraphAdjList;

（滑动显示更多）

3.4 最早发⽣时间etv求解

求事件的最早发⽣时间etv的过程,就是从头到尾去找拓扑序列列的过程. 所以在求解关键路径之前, 我们需要调用⼀次拓扑排序的序列去计算etv和拓扑序列列表.

etv计算公式推演, P[k]表示所有到达顶点Vk的弧的集合

  • 当k=0时，etv[k]=0;
  • 当k!=0时且<Vi,Vk>属于P[k], etv[k] = max {etv[i] len<Vi,Vk>};
代码语言：javascript复制
//拓扑排序
Status TopologicalSort(GraphAdjList GL){

    //若GL无回路,则输出拓扑排序序列且返回状态OK, 否则返回状态ERROR;
    EdgeNode *e;
    int i,k,gettop;
    //栈指针下标;
    int top = 0;
    //用于统计输出的顶点个数.作为拓扑排序是否存在回路的判断依据;
    int count = 0;
    //建栈,将入度in = 0的顶点入栈;
    int *stack = (int *)malloc(GL->numVertexes * sizeof(int));

    //遍历顶点表上入度in = 0 入栈
    for (i = 0; i < GL->numVertexes;i  ) {
        //printf("%d %dn",i,GL->adjList[i].in);
        if ( 0 == GL->adjList[i].in ) {
            stack[  top] = i;
        }
    }

    //* stack2 的栈指针下标
    top2 = 0;
    //* 初始化拓扑序列栈
    stack2 = (int *)malloc(sizeof(int) * GL->numVertexes);
    //* 事件最早发生时间数组
    etv = (int *)malloc(sizeof(GL->numVertexes * sizeof(int)));
    //* 初始化etv 数组
    for (i = 0 ; i < GL->numVertexes; i  ) {
        //初始化
        etv[i] = 0;
    }

    printf("TopologicSort:t");
    while (top != 0) {
        gettop = stack[top--];
        printf("%d -> ", GL->adjList[gettop].data);
        count  ;

        //将弹出的顶点序号压入拓扑排序的栈中;
        stack2[  top2] = gettop;

        //例如gettop为V0 ,那么与V0相连接的结点就有etv[1] = 3; etv[2] = 4;
        //例如gettop为V1 ,那么与V1连接的结点就有etv[4]= 3 6=9; etv[3] = 8;
        //例如gettop为V2 ,那么与V2连接的结点就有etv[5]= 4 7=11; etv[3] = 12;
        //例如gettop为V3 ,那么与V3连接的结点就有etv[4]= 12 3=15;
        for(e = GL->adjList[gettop].firstedge; e; e = e->next)
        {
            k = e->adjvex;

            //将i顶点连接的邻接顶点入度减1,如果入度减一后为0,则入栈
            if(!(--GL->adjList[k].in))
                stack[  top] = k;

            //求各顶点事件的最早发生的时间etv值
            //printf("etv[gettop] e->weight = %dn",etv[gettop] e->weight);
            //printf("etv[%d] = %dn",k,etv[k]);
            if ((etv[gettop]   e->weight) > etv[k]) {
                etv[k] = etv[gettop]   e->weight;
            }
        }

    }
    printf("n");

    //打印etv(事件最早发生时间数组)
//    for (i = 0; i < GL->numVertexes; i  ) {
//        printf("etv[%d] = %dn",i,etv[i]);
//    }
//    printf("n");

    if(count < GL->numVertexes)
        return ERROR;
    else
        return OK;
    return OK;
}

（滑动显示更多）

3.5 关键路路径算法解析ltv数组求解

事件最晚发⽣生时间ltv(latest time of vertex): 即顶点Vk 的最晚发⽣生时间,也就是每个顶点对应的事件最晚需要开始的时间,超出此时间将会延误整个⼯期;

ltv计算公式推演, S[k]表示所有到达顶点Vk的弧的集合

  • 将ltv数组初始化成etv最后一个事件的时间
  • 当k=n-1时，ltv[k]=etv[k];
  • 当k<n-1时且<Vi,Vk>属于S[k], ltv[k] = min {ltv[i] - len<Vi,Vk>};
代码语言：javascript复制
    //事件最晚发生时间数组
    ltv = (int *)malloc(sizeof(int) * GL->numVertexes);

    //初始化ltv数组
    for (i = 0; i < GL->numVertexes; i  ) {
        //初始化ltv数组. 赋值etv最后一个事件的值
        ltv[i] = etv[GL->numVertexes-1];
        //printf("ltv[%d] = %dn",i,ltv[i]);
    }

    //计算ltv(事件最晚发生时间) 出栈求ltv
    while (top2 != 0) {

        //出栈(栈顶元素)
        gettop = stack2[top2--];

        //找到与栈顶元素连接的顶点; 例如V0是与V1和V2连接
        for (e = GL->adjList[gettop].firstedge; e; e = e->next) {
            //获取与gettop 相连接的顶点
            k = e->adjvex;
            //计算min(ltv[k]-e->weight,ltv[gettop])
            if (ltv[k] - e->weight < ltv[gettop]) {
                //更新ltv 数组
                ltv[gettop] = ltv[k] - e->weight;
            }
        }
    }

（滑动显示更多）

3.6 关键路路径算法 求取ete以及lte过程解析

  • 活动的最早开工时间ete(earliest time of edge); 即弧Ak的最早发⽣生时间;
  • ete 就是表示活动 <Vk, Vj> 的最早开工时间, 是针对这条弧来说的. 而这条弧的弧尾顶点Vk的事件发⽣了, 它才可以发生. 因此ete = etv[k];
  • 活动的最晚开工时间lte(latest time of edge); 即弧Ak 的最晚发⽣生时间,也就是不推迟⼯期的最晚开工时间;
  • lte 表示活动<Vk, Vj> 的最晚开⼯工时间, 但此活动再晚也不不能等Vj 事件发⽣生才开始,⽽而是必须在Vj 事件之前发⽣生. 所以lte = ltv[j] - len<Vk, Vj>.
  • 拓扑序列: 指的是事件在执⾏的顺序
  • 关键活动: 指的是从开始到结束具有最大长度的路径叫关键路径,⽽而关键路径上的的活动叫做关键活动
代码语言：javascript复制
    //求解ete,lte 并且判断lte与ete 是否相等.相等则是关键活动;
    //2层循环(遍历顶点表,边表)
    for(j=0; j<GL->numVertexes;j  )
    {
        for (e = GL->adjList[j].firstedge; e; e = e->next) {
            //获取与j连接的顶点;
            k = e->adjvex;
            //ete 就是表示活动 <Vk, Vj> 的最早开工时间, 是针对这条弧来说的.而这条弧的弧尾顶点Vk 的事件发生了, 它才可以发生. 因此ete = etv[k];
            ete = etv[j];
            //lte 表示活动<Vk, Vj> 的最晚开工时间, 但此活动再晚也不能等Vj 事件发生才开始,而是必须在Vj 事件之前发生. 所以lte = ltv[j] - len<Vk, Vj>.
            lte = ltv[k]-e->weight;
            //如果ete == lte 则输出j,k以及权值;
            if (ete == lte) {
                printf("<%d-%d> length:%dn",GL->adjList[j].data, GL->adjList[k].data, e->weight);
            }
        }
    }

（滑动显示更多）

3.7 关键路径完整实现

代码语言：javascript复制
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXEDGE 30
#define MAXVEX 30
#define INFINITYC 65535

typedef int Status;    /* Status是函数的类型,其值是函数结果状态代码，如OK等 */

/* 邻接矩阵结构 */
typedef struct
{
    int vexs[MAXVEX];
    int arc[MAXVEX][MAXVEX];
    int numVertexes, numEdges;
}MGraph;

/* 邻接表结构****************** */
//边表结点
typedef struct EdgeNode
{
    //邻接点域，存储该顶点对应的下标
    int adjvex;
    //用于存储权值，对于非网图可以不需要
    int weight;
    //链域，指向下一个邻接点
    struct EdgeNode *next;
}EdgeNode;

//顶点表结点
typedef struct VertexNode
{
    //顶点入度
    int in;
    //顶点域，存储顶点信息
    int data;
    //边表头指针
    EdgeNode *firstedge;
}VertexNode, AdjList[MAXVEX];

typedef struct
{
    AdjList adjList;
    //图中当前顶点数和边数
    int numVertexes,numEdges;
}graphAdjList,*GraphAdjList;

/* **************************** */

/* 关于AOE网图的存储代码段-Begin */
//1.完成AOE网图关于邻接矩阵的存储
void CreateMGraph(MGraph *G)/* 构件图 */
{
    int i, j;
    /* printf("请输入边数和顶点数:"); */
    G->numEdges=13;
    G->numVertexes=10;

    for (i = 0; i < G->numVertexes; i  )/* 初始化图 */
    {
        G->vexs[i]=i;
    }

    for (i = 0; i < G->numVertexes; i  )/* 初始化图 */
    {
        for ( j = 0; j < G->numVertexes; j  )
        {
            if (i==j)
                G->arc[i][j]=0;
            else
                G->arc[i][j]=INFINITYC;
        }
    }

    G->arc[0][1]=3;
    G->arc[0][2]=4;
    G->arc[1][3]=5;
    G->arc[1][4]=6;
    G->arc[2][3]=8;
    G->arc[2][5]=7;
    G->arc[3][4]=3;
    G->arc[4][6]=9;
    G->arc[4][7]=4;
    G->arc[5][7]=6;
    G->arc[6][9]=2;
    G->arc[7][8]=5;
    G->arc[8][9]=3;

}


//2.将邻近矩阵转化成邻接表
void CreateALGraph(MGraph G,GraphAdjList *GL){

    int i,j;
    EdgeNode *e;

    *GL = (GraphAdjList)malloc(sizeof(graphAdjList));

    (*GL)->numVertexes=G.numVertexes;
    (*GL)->numEdges=G.numEdges;

    //读入顶点信息，建立顶点表
    for(i= 0;i <G.numVertexes;i  )
    {
        (*GL)->adjList[i].in=0;
        (*GL)->adjList[i].data=G.vexs[i];
        //将边表置为空表
        (*GL)->adjList[i].firstedge=NULL;
    }

    //建立边表
    for(i=0;i<G.numVertexes;i  )
    {
        for(j=0;j<G.numVertexes;j  )
        {
            if (G.arc[i][j]!=0 && G.arc[i][j]<INFINITYC)
            {
                e=(EdgeNode *)malloc(sizeof(EdgeNode));
                //邻接序号为j
                e->adjvex=j;
                e->weight=G.arc[i][j];
                //将当前顶点上的指向的结点指针赋值给e
                e->next=(*GL)->adjList[i].firstedge;
                //将当前顶点的指针指向e
                (*GL)->adjList[i].firstedge=e;
                (*GL)->adjList[j].in  ;

            }
        }
    }
}
/* 关于AOE网图的存储代码段-End! */
int *etv,*ltv; /* 事件最早发生时间和最迟发生时间数组，全局变量 */
int *stack2;   /* 用于存储拓扑序列的栈 */
int top2;       /* 用于stack2的指针*/

//拓扑排序
Status TopologicalSort(GraphAdjList GL){

    //若GL无回路,则输出拓扑排序序列且返回状态OK, 否则返回状态ERROR;
    EdgeNode *e;
    int i,k,gettop;
    //栈指针下标;
    int top = 0;
    //用于统计输出的顶点个数.作为拓扑排序是否存在回路的判断依据;
    int count = 0;
    //建栈,将入度in = 0的顶点入栈;
    int *stack = (int *)malloc(GL->numVertexes * sizeof(int));

    //遍历顶点表上入度in = 0 入栈
    for (i = 0; i < GL->numVertexes;i  ) {
        //printf("%d %dn",i,GL->adjList[i].in);
        if ( 0 == GL->adjList[i].in ) {
            stack[  top] = i;
        }
    }

    //* stack2 的栈指针下标
    top2 = 0;
    //* 初始化拓扑序列栈
    stack2 = (int *)malloc(sizeof(int) * GL->numVertexes);
    //* 事件最早发生时间数组
    etv = (int *)malloc(sizeof(GL->numVertexes * sizeof(int)));
    //* 初始化etv 数组
    for (i = 0 ; i < GL->numVertexes; i  ) {
        //初始化
        etv[i] = 0;
    }

    printf("TopologicSort:t");
    while (top != 0) {
        gettop = stack[top--];
        printf("%d -> ", GL->adjList[gettop].data);
        count  ;

        //将弹出的顶点序号压入拓扑排序的栈中;
        stack2[  top2] = gettop;

        //例如gettop为V0 ,那么与V0相连接的结点就有etv[1] = 3; etv[2] = 4;
        //例如gettop为V1 ,那么与V1连接的结点就有etv[4]= 3 6=9; etv[3] = 8;
        //例如gettop为V2 ,那么与V2连接的结点就有etv[5]= 4 7=11; etv[3] = 12;
        //例如gettop为V3 ,那么与V3连接的结点就有etv[4]= 12 3=15;
        for(e = GL->adjList[gettop].firstedge; e; e = e->next)
        {
            k = e->adjvex;

            //将i顶点连接的邻接顶点入度减1,如果入度减一后为0,则入栈
            if(!(--GL->adjList[k].in))
                stack[  top] = k;

            //求各顶点事件的最早发生的时间etv值
            //printf("etv[gettop] e->weight = %dn",etv[gettop] e->weight);
            //printf("etv[%d] = %dn",k,etv[k]);
            if ((etv[gettop]   e->weight) > etv[k]) {
                etv[k] = etv[gettop]   e->weight;
            }
        }

    }
    printf("n");

    //打印etv(事件最早发生时间数组)
//    for (i = 0; i < GL->numVertexes; i  ) {
//        printf("etv[%d] = %dn",i,etv[i]);
//    }
//    printf("n");

    if(count < GL->numVertexes)
        return ERROR;
    else
        return OK;
    return OK;
}

//求关键路径, GL为有向网,则输出G的各项关键活动;
void CriticalPath(GraphAdjList GL){
    EdgeNode *e;
    int i,gettop,k,j;

    //声明活动最早发生时间和最迟发生时间变量;
    int ete,lte;

    //求得拓扑序列,计算etv数组以及stack2的值
    TopologicalSort(GL);

    //打印etv数组(事件最早发生时间)
    printf("etv:n");
    for(i = 0; i < GL->numVertexes; i  )
        printf("etv[%d] = %d n",i,etv[i]);
    printf("n");

    //事件最晚发生时间数组
    ltv = (int *)malloc(sizeof(int) * GL->numVertexes);

    //初始化ltv数组
    for (i = 0; i < GL->numVertexes; i  ) {
        //初始化ltv数组. 赋值etv最后一个事件的值
        ltv[i] = etv[GL->numVertexes-1];
        //printf("ltv[%d] = %dn",i,ltv[i]);
    }

    //计算ltv(事件最晚发生时间) 出栈求ltv
    while (top2 != 0) {

        //出栈(栈顶元素)
        gettop = stack2[top2--];

        //找到与栈顶元素连接的顶点; 例如V0是与V1和V2连接
        for (e = GL->adjList[gettop].firstedge; e; e = e->next) {
            //获取与gettop 相连接的顶点
            k = e->adjvex;
            //计算min(ltv[k]-e->weight,ltv[gettop])
            if (ltv[k] - e->weight < ltv[gettop]) {
                //更新ltv 数组
                ltv[gettop] = ltv[k] - e->weight;
            }
        }
    }

    //打印ltv 数组
    printf("ltv:n");
    for (i = 0 ; i < GL->numVertexes; i  ) {
        printf("ltv[%d] = %d n",i,ltv[i]);
    }

    printf("n");
    //求解ete,lte 并且判断lte与ete 是否相等.相等则是关键活动;
    //2层循环(遍历顶点表,边表)
    for(j=0; j<GL->numVertexes;j  )
    {
        for (e = GL->adjList[j].firstedge; e; e = e->next) {
            //获取与j连接的顶点;
            k = e->adjvex;
            //ete 就是表示活动 <Vk, Vj> 的最早开工时间, 是针对这条弧来说的.而这条弧的弧尾顶点Vk 的事件发生了, 它才可以发生. 因此ete = etv[k];
            ete = etv[j];
            //lte 表示活动<Vk, Vj> 的最晚开工时间, 但此活动再晚也不能等Vj 事件发生才开始,而是必须在Vj 事件之前发生. 所以lte = ltv[j] - len<Vk, Vj>.
            lte = ltv[k]-e->weight;
            //如果ete == lte 则输出j,k以及权值;
            if (ete == lte) {
                printf("<%d-%d> length:%dn",GL->adjList[j].data, GL->adjList[k].data, e->weight);
            }
        }
    }

}

（滑动显示更多）

3.8 结果预期

edge time vi

0 人点赞