AOV无环图有向图 拓扑排序

1. 梗概

1. 本质上是一种有向无环图的遍历方法

2. 适用范围:

1. 对有向 无回路 的图(Activity On Vertex Network,简称AOV)
   1. 按流程遍历
      1. 类似工程, 需要要一步步把前提顶点遍历
   2. 遍历所有顶点
2. 判断图中是否有环/回路(⭐)

3. 算法思想:

1. 先遍历入度为0的顶点(前提)
2. 再把该顶点和相应的边忽略掉
3. 再次遍历入度为0的顶点(前提后的下一步)

4. 在c语言中的实现

细节梗概:

1. 该算法优先遍历新生成的0入度顶点
   1. 因为采用栈来保存入度为0的顶点
      1. 初始的几个0入度顶点入栈
      2. 遍历其中一个0入度顶点后, 又产生几个新的0入度顶点, 把这些新的顶点入栈
         1. 出栈的时候优先取新的0入度顶点 代码:

int TopologicalSort(AdjList *G){
//有环返回0,无环返回1
    ArcNode *e;
    int i, k, gettop;
    int top=0;
    int count=0;
    int *stack,*indegree;
    indegree=(int*)calloc(G->vexnum,sizeof(int));
    stack=(int*)calloc(G->vexnum,sizeof(int));
    /*统计所有顶点的入度*/
    for(i=0;i<G->vexnum;++i)
        indegree[i]=0;
    for(i=0;i<G->vexnum;++i){
        e=G->vertex[i].firstarc;
        for(;e;){
            ++indegree[e->adjvex];
            e=e->nextarc;
        }
    }
    /*把所有入度为0的顶点都入栈*/
    for(i=0;i<G->vexnum;++i)
        if(!(indegree[i]))
            stack[++top]=i;
    for(;top;){
        /*获得拓扑顺序*/
        gettop=stack[top--];
        //输出gettop
        count++;
        /*遍历出度顶点*/
        for(e=G->vertex[gettop].firstarc;e;){
            k=e->adjvex;
            /*删除入度,并判断删除后入度是否可以进栈*/
            if(!(--indegree[k]))
                stack[++top]=k;
            e=e->nextarc;
        }
    }
    free(indegree);
    free(stack);
    /*如果有环,就会有顶点没有排序到*/
    return !(count<G->vexnum);
}

5. 手动运算:

5.1. 先把图用简易逆邻接表表示出来

即只保留顶点数据, 不保留顶点序号, 且舍弃边的权值

5.2. 按算法步骤取入度为0的顶点

注意: 先遍历新生成的0入度顶点

5.3. 每取一个顶点, 就把逆邻接表中含该顶点的边都标上叉叉