简单的说，从某个集合上的一个偏序得到该集合上的一个全序，这个操作称为拓扑排序。偏序指得是这个集合中的仅有部分元素可以比较，而全序指的是集合的全体成员之间均可以比较。
这种排序在生活中也很常见，比如上学期间学的课程：要学随机过程就必须学过概率论和高等数学，要学数值分析必须学过高等数学和线性代数，要学模电必须学过电路，等等。所以，假如课程很多的话，如何通过程序来求解一个合适的学习顺序呢？
首先得通过一定的数据结构来表示我们的问题。一种简单的方式，就是采用有向图。顶点表示活动，边表示活动优先关系。这种图也称为AOV（activity on vertex）网。之后的算法也很容易：
1.将图中所有入度为0的节点入队
2.将这些节点从图中删除
3.不断重复1、2，直到所有节点都入队。
4.依次输出队列中所有的元素。 下面我们看一下程序 #include #include //拓扑排序需要使用队列 #include "queue.h" //定义有向无环图的数据结构 typedef int** ADJACENTMATRIX; typedef struct directedAcyclineGraph { ADJACENTMATRIX matrix; int vertexNumber; int arcNumber; char* vertex; //标记这个节点是否被使用过 bool* hasUsed; }DAG; #define MAX 8 //基本操作 //初始化 DAG initGraph(int); //销毁 void destroyGraph(DAG* ); //添加 bool addArc(DAG* ,char,char); //删除 bool deleteArc(DAG* ,char,char); //打印邻接矩阵 void printGraph(DAG* ); //拓扑排序相关函数 int* find_all_InDgree_equal2Zero_node(DAG*,int*); void delete_InDgree_equal2Zero_node(DAG* g,int* sequence,int length); void topologicalSort(DAG*);
无相图的定义方式其实跟有向图差不多，之不过每次给两个节点增加边时，只增加一个方向的。在前面几次写程序的过程中，我先发图的遍历时，经常需要判断这个节点是否被访问过之类的事，为了解决这个问题，我给整个数据结构中增加了一个记录节点是否被访问的数组，这样看起来会简单一点。   DAG initGraph(int n) { DAG g; g.vertexNumber = n; g.arcNumber = 0; g.vertex = (char*)malloc(sizeof(char) * n); g.hasUsed = (bool*)malloc(sizeof(bool) * n); char start = 'A'; for(int i = 0; i < n;++i) { g.vertex[i] = start + i; g.hasUsed[i] = false; } g.matrix = (int**)malloc(sizeof(int*) * n); for(int i = 0; i < n;++i) g.matrix[i] = (int*)malloc(sizeof(int) * n); //邻接矩阵的初始为为最大值 for(int i = 0; i < n;++i) for(int j = 0; j < n;++j) g.matrix[i][j] = 0; return g; } void destroyGraph(DAG* g) { free(g->vertex); g->vertex = NULL; for(int i = 0; i < g->vertexNumber;++i) free(g->matrix[i]); free(g->matrix); g->matrix = NULL; g->arcNumber = -1; g->vertexNumber = -1; } bool addArc(DAG* g,char start,char end) { int i = start - 'A'; int j = end - 'A'; if(i < 0 || i > g->vertexNumber || j < 0 || j > g->vertexNumber) { printf("vertexes does not exsist! "); return false; } else { g->matrix[i][j] = 1; g->arcNumber++; return true; } } bool deleteArc(DAG* g,char start,char end) { int i = start - 'A'; int j = end - 'A'; if(i < 0 || i > g->vertexNumber || j < 0 || j > g->vertexNumber) { printf("vertexes does not exsist! "); return false; } if(0 == g->matrix[i][j] ) { printf("there is no arc between vertexes! "); return false; } else { g->matrix[i][j] = 0; g->arcNumber--; return true; } } void printGraph(DAG* g) { printf(" "); for(int i = 0; i < g->vertexNumber;++i) printf("%c ",g->vertex[i]); for(int i = 0; i < g->vertexNumber;++i) { printf(" "); printf("%c ",g->vertex[i]); for(int j = 0;j < g->vertexNumber;++j) printf("%d ",g->matrix[i][j]); } printf(" "); } void topologicalSort(DAG* g) { int cnt = g->vertexNumber; Queue q = initQueue(g->vertexNumber+1); while(cnt > 0) { int len; int* enqueueSequence = find_all_InDgree_equal2Zero_node(g,&len); for(int i = 0; i < len;++i) { enqueue(&q,&enqueueSequence[i]); printf("%d",enqueueSequence[i]); } cnt = cnt - len; //删除这些入度为0的节点，实际上就是把这些节点出去的路径置为0 delete_InDgree_equal2Zero_node(g,enqueueSequence,len); free(enqueueSequence); } //出队 while(!is_empty(&q)) { int vec; dequeue(&q,&vec); printf("%c",g->vertex[vec]); } } int* find_all_InDgree_equal2Zero_node(DAG* g,int *n) { //存放入度为0的节点的数组 int *InDgree_equal2Zero_node = (int*)malloc(sizeof(int) * MAX); //保存每个节点的入度 bool equal2Zero[MAX]; for(int i = 0; i < g->vertexNumber;++i) equal2Zero[i] = true; //对于每一个节点 for(int i = 0; i < g->vertexNumber;++i) { if(true == g->hasUsed[i]) { equal2Zero[i] = false; continue; } //遍历它的所有入度 for(int j = 0; j < g->vertexNumber;++j) { //如果有一个节点有入度 if(g->matrix[j][i] != 0) { equal2Zero[i] = false; break; } } } int cnt = 0; for(int i = 0; i < g->vertexNumber;++i) { if(true == equal2Zero[i]) { InDgree_equal2Zero_node[cnt] = i; g->hasUsed[i] = true; ++cnt; } } *n = cnt; return InDgree_equal2Zero_node; } void delete_InDgree_equal2Zero_node(DAG* g,int* sequence,int length) { char vec1 = 'A'; char vec2 = 'A'; //对于序列中的每个点 for(int i = 0; i < length;++i) { for(int j = 0; j < g->vertexNumber;++j) { if(g->matrix[sequence[i]][j] != 0) { deleteArc(g,vec1+sequence[i],vec2+j); //调试打印 printf("删除的路径为%c%c ",vec1+sequence[i],vec2+j); } } } }