前言#

现实生活中，我们完成一件事会存在先后顺序，而在完成一个重要的项目的时候，我们会给这些事情安排一个进行顺序。这些事情之间，通常会受到一定的条件约束，如其中某些活动必须在另一些活动完成之后才能开始。我们要如何安排这些顺序，就是这一章会涉及的了。

本章内容为拓扑排序，是书本《Data Structures and Algorithm Analysis in C》的第九章的1~2节。

图论基础内容#

在学习拓扑排序之前，我们需要先了解一些图论的基础内容。

在 线性表 中，数据元素之间是被串起来的，仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继。在 树形结构 中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关，且它们这一层之间的元素也基本没什么关系。

但是就像现实中一样，人与人之间关系就非常复杂，我认识的朋友，可能他们之间也互相认识，这就不是简单的一对一、一对多，研究人际关系很自然会考虑多对多的清况。

于是就出现了新的数据结构——图。 在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。

我们定义： 图(Graph) 是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为： G (V,E) ，其中， G 表示一个图， V 是图G 中顶点（Vertex）的集合， E 是图G 中边（Edge）的集合。

注意，在图结构中，不允许没有顶点，即V是非空集合。而E可以为空集，说明V之间没有边连接，它们没有联系。

接下来是一些图中的定义。

拓扑排序#

介绍完图论的一些简单基础知识后，就到了无环的图应用——拓扑排序。在拍摄电影的时候，这个项目会有很多的事件，我们将它们做成一个流程图，如下：

在这些活动之间，通常会受到一定的条件约束，如其中某些活动必须在另一些活动完成之后才能开始。例如场景拍摄不可能在人员到位进驻场地前，因为现在场地都没有怎么拍。因此这样的工程图，一定是 无环的有向图。

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

此时在有向图中顶点Vi到Vj有一条路径，意思为Vi -> Vj，而不蕴含Vj -> Vi。此时因为在一个项目中，故此时存在先后顺序，顶点序列中顶点Vi必在顶点Vj之前。

拓扑排序 ，其实就是 对一个有向图构造拓扑序列的过程 。这个过程会让项目中 全部顶点 输出，而排序的结果不一定唯一，合理的输出均正确。

拓扑排序的基本思路是： 从无圈图中选择一个入度为0的顶点，然后删去此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或者无圈图中不存在入度为0的顶点为止。

我们一般使用邻接表来存储图，至于入度为0的顶点如何处理我们有如下方案：

1. 写一个Indegree()函数，在每次删除顶点和它的弧后，用于找到入度为0的顶点，并用数组存储。
2. 用一个全局的数组、 栈或队列 储存入度为0的顶点们，在每次删除顶点和它的弧后，检查调整入度的节点入度是否为0，为0则加入到队列中。

第一种方案明显是耗费更多时间的，因为每次查找都要扫描所有的顶点。而第二种方案是为了避免每个查找时都要去遍历顶点表找有没有入度为0的顶点，我们存储结构的选取就很关键。

一般情况下，我们会选取 队列 作为存储入度为0的顶点编号，而使用 栈 存储也是可以的。它们两种不同的存储方法可能会带来不同的拓扑序列，它们都是正确的。

故拓扑排序算法我们一般如下设计：

1. 建图，初始化图。
2. 建队列或栈，把入度为0的顶点编号放入队列或栈中。
3. 出队或出栈首元素，并把那个元素放入数组中。
4. 扫描首元素相邻的邻接点，并把它们的入度-1，如果该邻接点入度-1后入度为0，则将该点入队或入栈。
5. 重复2操作，直到队列或栈为空。

接下来我们就用两种不同的存储方法实现拓扑排序。

首先是这两种方法统一的图的存储：

1
typedef struct Edge_Node /* 边表结点  */
2
{
3
  int adjvex;    /* 邻接点域，存储该顶点对应的下标 */
4
  struct Edge_Node *next; /* 链域，指向下一个邻接点 */
5
}EdgeNode;
6

7
typedef struct Vertex_Node /* 顶点表结点 */
8
{
9
    int in; /* 顶点入度 */
10
  int data; /* 顶点域，存储顶点信息 */
11
  EdgeNode *firstedge;/* 边表头指针 */
12
}VertexNode, *AdjList;
13

14
typedef struct
15
{
16
  AdjList adjList;
17
  int numVertexes; /* 图中当前顶点数 */
18
}graphAdjList,*GraphAdjList;

我们此时用一个域 in ，来记录入度，这样就不用反复计算了。

接下来是创建邻接表：

1
GraphAdjList CreateGraph(int ver[], int **edge, int n)
2
{
3
    /*ver[]为顶点的数组，**edge为边的数组，n为顶点数*/
4
    GraphAdjList G=(GraphAdjList)malloc(sizeof(graphAdjList));
5
    if(G == NULL)
6
    {
7
        printf("No space!\\n");
8
        exit(-1);
9
    }
10
    G->numVertexes=n;
11
    G->adjList=(AdjList)malloc(sizeof(VertexNode) * n);
12
    for(int i=0;i<n;i++)
13
    {
14
        G->adjList[i].data=ver[i];
15
        G->adjList[i].firstedge=NULL;
16
        G->adjList[i].in=0;
17
    }
18
    for(int i=0;i<n;i++)
19
        for(int j=0;j<n;j++)
20
        {
21
            if(edge[i][j] == 1)
22
            {
23
                EdgeNode *e=(EdgeNode *)malloc(sizeof(EdgeNode));
24
                e->adjvex=j;
25
                e->next=G->adjList[i].firstedge->next;
26
                G->adjList[i].firstedge->next=e;     /* 插入到链表首部 */
27
                G->adjList[j].in++;
28
            }
29
        }
30
    return G;
31
}

1
void TopologicalSort_Queue(int *A, GraphAdjList G)
2
{
3
    int count=0;
4
    Queue Q=CreateQueue();
5
    for(int i=0;i<G->numVertexes;i++)    /* 将入度为0的顶点入队 */
6
    {
7
        if(!G->adjList[i].in)
8
            Enqueue(i,Q);
9
    }
10
    while(!IsEmpty(Q))
11
    {
12
        int v=FrontAndDequeue(Q);    /* 出队并得到队首元素 */
13
        A[count++]=v;
14
        EdgeNode *p=G->adjList[v].firstedge->next;
15
        while(p)
16
        {
17
            int t=p->adjvex;
18
            G->adjList[t].in--;    /* 将顶点t的邻接点的入度减1 */
19
            if(!G->adjList[t].in)    /*如果当前顶点入度减1后为0，则入队 */
20
                Enqueue(t,Q);
21
            p=p->next;
22
        }
23
    }
24
    if(count < G->numVertexes)
25
    {
26
        printf("Error, the graph has loops\\n.");
27
        return;
28
    }
29
}

1
void TopologicalSort_Stack(int *A, GraphAdjList G)
2
{
3
    int count=0;
4
    Stack S=create();
5
    for(int i=0;i<G->numVertexes;i++)    /* 将入度为0的顶点入栈 */
6
    {
7
        if(!G->adjList[i].in)
8
            push(S,i);
9
    }
10
    while(!IsStackEmpty(S))
11
    {
12
        int v=pop(S);    /* 出栈并得到队首元素 */
13
        A[count++]=v;
14
        EdgeNode *p=G->adjList[v].firstedge->next;
15
        while(p)
16
        {
17
            int t=p->adjvex;
18
            G->adjList[t].in--;    /* 将顶点t的邻接点的入度减1 */
19
            if(!G->adjList[t].in)    /*如果当前顶点入度减1后为0，则入栈 */
20
                S=push(S,t);
21
            p=p->next;
22
        }
23
    }
24
    if(count < G->numVertexes)
25
    {
26
        printf("Error, the graph has loops\\n.");
27
        return;
28
    }
29
}

后记#

以上则为拓扑排序的内容，队列和栈带来的拓扑序列结果不一定相同，但都正确。此刻我们涉及到的是无权的图，在有权图中的拓扑排序往往会存在一些条件，我们需要根据那些条件来设计拓扑排序算法。