拓扑排序 - 简书

拓扑排序

先上一波图看看效果

image

DAG与AOV？

DAG(Directed Acyclic Grap)指的是“有向无环图”，通常也称为“流程图”。

当我们要完成一个工程的时候，我们可以先将大的工程分成几个独立的子工程，将子工程d当作“活动”，每个活动之间有先决条件的关系（时间上有着相互制约的关系），就是说活动的执行有一定的顺序。将“活动”看成顶点，以弧表示活动之间的优先关系，这样的图称为“AOV”网（Activity On Vertex NetWork）。

拓扑排序是什么，有什么用？

如果要执行活动A，必须执行活动B，执行B就要执行C，要执行C就要执行A，这样形成一个环的话，就陷入了死循环，那我们怎么知道到底有没有环呢？这时候就出现了拓扑排序，也就是说拓扑排序将检测AOV图中是否有环，求一个有向图拓扑排序序列的过程就是拓扑排序。

实现拓扑排序实例。

先来看看用到的结构体吧

#include <stdlib.h>
#include<stdio.h>
#define MAXVEX 20
#define NON -1
typedef char VexType;
typedef float AdjType;

/* 边表中的结点 */
typedef struct EdgeNode {
    int endvex;         // 相邻顶点字段 ,一条边的另一个顶点
    AdjType weight;     //边的权，非带权图可以省略 
    struct EdgeNode *nextedge;  // 链字段 ,连接到下一条边
}*PEdgeNode, *EdgeList;

/*顶点中的信息*/
typedef struct {
    VexType vertex;     // 顶点信息 
    EdgeList edgelist;  //后面所有的边和组成的边
} VexNode;  // 顶点表中的结点 

/*点的集合和边表中链接信息构成了图*/                     
typedef struct {
    int n;              // 图的顶点个数 
    VexNode vexs[MAXVEX];
} GraphList;

拓扑排序只需3步：

输出顶点入度为0的值
让这个点消失（删除点及由它发出的边）
重复执行1和2直到输出无连接边的顶点

当然执行这些之前，你得有个图啊（摊手），已经有图的童鞋请跳过这一步。(下面是插入方法的主要代码)

/*插入顶点及连接的信息*/
void insert(GraphList* p, int a, int b) {//a，b是将要连接的两个顶点
    EdgeList pp;//链接边 
    
    //给顶点赋值
    p->vexs[a].vertex = a;
    //如果指向NON，则说明是最后一个节点
    if (b == NON)
    {
        p->vexs[a].edgelist = NULL;
        return;
    }

    PEdgeNode temp;//边的节点
    temp = (PEdgeNode)malloc(sizeof(EdgeNode));
    temp->endvex = b;
    temp->nextedge = NULL;
    pp = p->vexs[a].edgelist;//将连接边复制给pp

    if (pp == NULL)//连接两个顶点
        p->vexs[a].edgelist = temp;
    else {//将新边连接到后边
        while (pp->nextedge != NULL)
            pp = pp->nextedge;
        pp->nextedge = temp;
    }
}

咳咳，现在开始拓扑排序了。

输出顶点入度为0的值
首先你得找到哪些点入度为0(统计入度)

    /*统计入度*/
    Indegree = (int *)malloc(GL->n * sizeof(int));//存储入度
    for (i = 0; i<GL->n; i++)
        Indegree[i] = 0;
    for (i = 0; i < GL->n; i++)
    {
        EdgeList p = GL->vexs[i].edgelist;
        while (p != NULL)
        {
            Indegree[p->endvex]++;
            p = p->nextedge;
        }
    }//所有点的入度已经存储完毕
        ```
  然后就把入度为0的顶点揪出来吧**(入度为0的揪出来放到stack里面)**

for (j = 0; j < GL->n; j++)//初始化stack栈
{
stack[j] = -1;
}
/*
*将入度为0的节点入栈
*/
for (i = 0; i < GL->n; i++)
{
if (Indegree[i] == 0)
{
stack[top] = i;
top++;
}
}
top--;//top在执行完之后多加了一个

终于可以输出入度为0的点了吧。

printf("%d ", GL->vexs[gettop].vertex);//输出顶点自身

只有一句话吗？
2. 让已经输出的顶点就消失吧。

//输出顶点信息以后减少相应链接点的入度，标志着这个点从此消失
Indegree[GL->vexs[gettop].edgelist->endvex]--;
e = GL->vexs[gettop].edgelist->nextedge;
while (e != NULL)
{
Indegree[e->endvex]--;
e = e->nextedge;
}

当看到这里的时候，就应该想如果最后一个顶点也这样输出的话，就会出现内存泄露了，所以当到最后一个顶点的时候，就特殊处理吧。

####然后通过循环就可以进行拓扑排序啦，别忘了用一个计数器来记录输出的个数，最后通过输出的个数来判断是否能进行拓扑排序。

最后编辑于：2017.11.23 21:49:23