拓扑排序(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 去掉边<n,m>; 3.2.2 如果m没有依赖顶点，则把m放入Q; 注：顶点A没有依赖顶点，是指不存在以A为终点的边。
拓扑排序代码：
void topological_sort(Graph g) { if (has_circle(g)) { printf("该图有环，不能进行拓扑排序."); return ; } Queue q; init_queue(&q); int i, j,index; index = 0; int* ins; char* topos; int num; num = g.vex_num; ENode* node; ins = (int*)malloc(sizeof(int)*num); topos = (char*)malloc(sizeof(char)*num); memset(ins, 0,sizeof(int)*num); memset(topos, 0, sizeof(char)); for (i = 0; i < g.vex_num; i++) { node = g.vex[i].first_edge; while (node != NULL) { ins[node->ivex]++; node = node->next; } } for (i = 0; i < g.vex_num; i++) { if (ins[i] == 0) //把所有入度为0的顶点入队 { enqueue(i, &q); } } while (!is_empty(q)) { j = q_front(q); topos[index++] = g.vex[j].data; dequeue(&q); node = g.vex[j].first_edge; while (node != NULL) { ins[node->ivex]--; if (ins[node->ivex] == 0) { enqueue(node->ivex, &q); } node = node->next; } } printf("top_sort_result:\n\n\t"); int flag = 1; for (i = 0; i < g.vex_num; i++) { if (flag) { flag = 0; printf("%c", topos[i]); } else { printf("->%c", topos[i]); } } free(ins); free(topos); }
完整代码实现：
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<ctype.h> #define MAXVEX 100 #define TRUE 1 #define FALSE 0 #define gray -1 #define white 0 #define black 1 //int loop_num; //环 数量 int color[MAXVEX]; //-1 表示灰色 0表示白色 1 表示黑色 bool is_dag = true;//是否是有向无环图 //int link_component; // 连通分量 数量 typedef char VertexType; typedef struct QNode { int front, rear; int data[MAXVEX]; int size; }Queue; typedef struct ENode { int ivex;//顶点 索引 struct ENode* next; }ENode; typedef struct VNode { VertexType data; // 顶点 信息 ENode* first_edge; }VNode; typedef struct Graph { VNode vex[MAXVEX]; int vex_num, edge_num; }Graph; void init_queue(Queue *q) { q->front = q->rear = 0; q->size = 0; } int is_empty(Queue q) { return q.front == q.rear; } int is_full(Queue q) { return (q.rear + 1) % MAXVEX == q.front; } void enqueue(int x, Queue *q) { if (!is_full(*q)) { q->data[q->rear] = x; q->rear = (q->rear + 1) % MAXVEX; q->size++; } } void dequeue(Queue *q) { if (!is_empty(*q)) { q->front = (q->front + 1) % MAXVEX; q->size--; } } int q_front(Queue q) { return q.data[q.front]; } char read_char() { char ch; do { ch = getchar(); } while (!isalpha(ch)); return ch; } int get_pos(Graph g, char ch) { int i; for (i = 0; i < g.vex_num; i++) { if (g.vex[i].data == ch) return i; } return -1; } void link_last(ENode* list, ENode* last) { ENode* p; p = list; while (p->next != NULL) { p = p->next; } p->next = last; } void create_graph(Graph *g) { int i; //printf("请输入顶点数与边数:\n"); scanf("%d%d", &g->vex_num, &g->edge_num); //printf("请输入顶点信息:\n"); for (i = 0; i < g->vex_num; i++) { g->vex[i].data = read_char(); g->vex[i].first_edge = NULL; } //printf("请输入边的信息:\n"); char c1, c2; int p1, p2; for (i = 0; i < g->edge_num; i++) { c1 = read_char(); c2 = read_char(); p1 = get_pos(*g, c1); p2 = get_pos(*g, c2); ENode* node1; node1 = (ENode*)malloc(sizeof(ENode)); if (node1 == NULL) return; node1->next = NULL; node1->ivex = p2; if (g->vex[p1].first_edge == NULL) {//错把p1 写成i了 g->vex[p1].first_edge = node1; } else { link_last(g->vex[p1].first_edge, node1); } } } void print_graph(Graph g) { ENode* p; int i; for (i = 0; i < g.vex_num; i++) { printf("顶点%c出度边 ：\n", g.vex[i].data); p = g.vex[i].first_edge; while (p != NULL) { printf("(%c, %c)", g.vex[i].data, g.vex[p->ivex].data); p = p->next; } printf("\n"); } } void dfs(Graph g, int i) { ENode* p; color[i] = gray; p = g.vex[i].first_edge; while (p != NULL) { if (color[p->ivex] == white) { dfs(g, p->ivex); } else if(color[p->ivex] == gray){ is_dag = false; } p = p->next; } color[i] = black; } int has_circle(Graph g) { int i; ENode* p; for (i = 0; i < g.vex_num; i++) { color[i] = white; } //loop_num = 0; for (i = 0; i < g.vex_num; i++) { if (color[i] == white) { dfs(g, i); // loop_num++; } } if (!is_dag) return 1; else return 0; } void topological_sort(Graph g) { if (has_circle(g)) {//首先判断是否有环 也可以利用索引 与顶点数进行比较 最后确定是否有环 printf("该图有环，不能进行拓扑排序."); return ; } Queue q; init_queue(&q); int i, j,index; index = 0; int* ins; char* topos; int num; num = g.vex_num; ENode* node; ins = (int*)malloc(sizeof(int)*num); topos = (char*)malloc(sizeof(char)*num); memset(ins, 0,sizeof(int)*num); memset(topos, 0, sizeof(char)); for (i = 0; i < g.vex_num; i++) {// 计算每个顶点的入度 node = g.vex[i].first_edge; while (node != NULL) { ins[node->ivex]++; node = node->next; } } for (i = 0; i < g.vex_num; i++) { if (ins[i] == 0) //把所有入度为0的顶点入队 { enqueue(i, &q); } } while (!is_empty(q)) { j = q_front(q); topos[index++] = g.vex[j].data;//放进排序结果 dequeue(&q); node = g.vex[j].first_edge; while (node != NULL) { ins[node->ivex]--; if (ins[node->ivex] == 0) {//如果 入度为0 入队 enqueue(node->ivex, &q); } node = node->next; } } printf("top_sort_result:\n\n\t"); int flag = 1; for (i = 0; i < g.vex_num; i++) { if (flag) { flag = 0; printf("%c", topos[i]); } else { printf("->%c", topos[i]); } } free(ins); free(topos); } int main() { Queue q; init_queue(&q); Graph g; create_graph(&g); //print_graph(g); printf("\n"); topological_sort(g); getchar(); getchar(); return 0; }
