拓扑排序

作者: 土豆洋芋山药蛋 | 来源:发表于2016-12-01 00:42 被阅读95次

    先上一波图看看效果

    image
    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步:

    1. 输出顶点入度为0的值
    2. 让这个点消失(删除点及由它发出的边)
    3. 重复执行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;
        }
    }
    

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

    1. 输出顶点入度为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;
    }

    当看到这里的时候,就应该想如果最后一个顶点也这样输出的话,就会出现内存泄露了,所以当到最后一个顶点的时候,就特殊处理吧。
    
    ####然后通过循环就可以进行拓扑排序啦,别忘了用一个计数器来记录输出的个数,最后通过输出的个数来判断是否能进行拓扑排序。
    

    相关文章

      网友评论

      本文标题:拓扑排序

      本文链接:https://www.haomeiwen.com/subject/fvgtmttx.html