拓扑排序算法-ag真人游戏

拓扑排序介绍

拓扑排序(topological order)是指，将一个有向无环图(directed acyclic graph简称dag)进行排序进而得到一个有序的线性序列。

这样说，可能理解起来比较抽象。下面通过简单的例子进行说明！
例如，一个项目包括a、b、c、d四个子部分来完成，并且a依赖于b和d，c依赖于d。现在要制定一个计划，写出a、b、c、d的执行顺序。这时，就可以利用到拓扑排序，它就是用来确定事物发生的顺序的。

在拓扑排序中，如果存在一条从顶点a到顶点b的路径，那么在排序结果中b出现在a的后面。

拓扑排序的算法图解

拓扑排序算法的基本步骤：

1. 构造一个队列q(queue) 和 拓扑排序的结果队列t(topological)；
2. 把所有没有依赖顶点的节点放入q；
3. 当q还有顶点的时候，执行下面步骤：
3.1 从q中取出一个顶点n(将n从q中删掉)，并放入t(将n加入到结果集中)；
3.2 对n每一个邻接点m(n是起点，m是终点)；
3.2.1 去掉边;
3.2.2 如果m没有依赖顶点，则把m放入q;
注：顶点a没有依赖顶点，是指不存在以a为终点的边。

以上图为例，来对拓扑排序进行演示。

缺少图

第1步：将b和c加入到排序结果中。
    顶点b和顶点c都是没有依赖顶点，因此将c和c加入到结果集t中。假设abcdefg按顺序存储，因此先访问b，再访问c。访问b之后，去掉边和，并将a和d加入到队列q中。同样的，去掉边和，并将f和g加入到q中。
    (01) 将b加入到排序结果中，然后去掉边和；此时，由于a和d没有依赖顶点，因此并将a和d加入到队列q中。
    (02) 将c加入到排序结果中，然后去掉边和；此时，由于f有依赖顶点d，g有依赖顶点a，因此不对f和g进行处理。
第2步：将a,d依次加入到排序结果中。
    第1步访问之后，a,d都是没有依赖顶点的，根据存储顺序，先访问a，然后访问d。访问之后，删除顶点a和顶点d的出边。
第3步：将e,f,g依次加入到排序结果中。

因此访问顺序是：b -> c -> a -> d -> e -> f -> g

扑排序的代码说明

拓扑排序是对有向无向图的排序。下面以邻接表实现的有向图来对拓扑排序进行说明。

1. 基本定义

// 邻接表中表对应的链表的顶点
typedef struct _enode
{
    int ivex;                   // 该边所指向的顶点的位置
    struct _enode *next_edge;   // 指向下一条弧的指针
}enode, *penode;
// 邻接表中表的顶点
typedef struct _vnode
{
    char data;              // 顶点信息
    enode *first_edge;      // 指向第一条依附该顶点的弧
}vnode;
// 邻接表
typedef struct _lgraph
{
    int vexnum;             // 图的顶点的数目
    int edgnum;             // 图的边的数目
    vnode vexs[max];
}lgraph;

(01) lgraph是邻接表对应的结构体。 vexnum是顶点数，edgnum是边数；vexs则是保存顶点信息的一维数组。
(02) vnode是邻接表顶点对应的结构体。 data是顶点所包含的数据，而firstedge是该顶点所包含链表的表头指针。
(03) enode是邻接表顶点所包含的链表的节点对应的结构体。 ivex是该节点所对应的顶点在vexs中的索引，而nextedge是指向下一个节点的。

2. 拓扑排序

/*
 * 拓扑排序
 *
 * 参数说明：
 *     g -- 邻接表表示的有向图
 * 返回值：
 *     -1 -- 失败(由于内存不足等原因导致)
 *      0 -- 成功排序，并输入结果
 *      1 -- 失败(该有向图是有环的)
 */
int topological_sort(lgraph g)
{
    int i,j;
    int index = 0;
    int head = 0;           // 辅助队列的头
    int rear = 0;           // 辅助队列的尾
    int *queue;             // 辅组队列
    int *ins;               // 入度数组
    char *tops;             // 拓扑排序结果数组，记录每个节点的排序后的序号。
    int num = g.vexnum;
    enode *node;
    ins  = (int *)malloc(num*sizeof(int));  // 入度数组
    tops = (char *)malloc(num*sizeof(char));// 拓扑排序结果数组
    queue = (int *)malloc(num*sizeof(int)); // 辅助队列
    assert(ins!=null && tops!=null && queue!=null);
    memset(ins, 0, num*sizeof(int));
    memset(tops, 0, num*sizeof(char));
    memset(queue, 0, num*sizeof(int));
    // 统计每个顶点的入度数
    for(i = 0; i < num; i  )
    {
        node = g.vexs[i].first_edge;
        while (node != null)
        {
            ins[node->ivex]  ;
            node = node->next_edge;
        }
    }
    // 将所有入度为0的顶点入队列
    for(i = 0; i < num; i   )
        if(ins[i] == 0)
            queue[rear  ] = i;          // 入队列
    while (head != rear)                // 队列非空
    {
        j = queue[head  ];              // 出队列。j是顶点的序号
        tops[index  ] = g.vexs[j].data; // 将该顶点添加到tops中，tops是排序结果
        node = g.vexs[j].first_edge;    // 获取以该顶点为起点的出边队列
        // 将与"node"关联的节点的入度减1；
        // 若减1之后，该节点的入度为0；则将该节点添加到队列中。
        while(node != null)
        {
            // 将节点(序号为node->ivex)的入度减1。
            ins[node->ivex]--;
            // 若节点的入度为0，则将其"入队列"
            if( ins[node->ivex] == 0)
                queue[rear  ] = node->ivex;  // 入队列
            node = node->next_edge;
        }
    }
    if(index != g.vexnum)
    {
        printf("graph has a cycle\n");
        free(queue);
        free(ins);
        free(tops);
        return 1;
    }
    // 打印拓扑排序结果
    printf("== topsort: ");
    for(i = 0; i < num; i   )
        printf("%c ", tops[i]);
    printf("\n");
    free(queue);
    free(ins);
    free(tops);
    return 0;
}

说明：
(01) queue的作用就是用来存储没有依赖顶点的顶点。它与前面所说的q相对应。
(02) tops的作用就是用来存储排序结果。它与前面所说的t相对应。

拓扑排序的完整源码和测试程序

拓扑排序源码(list_dg.c)