数据结构图的拓扑排序总结

图

在数学中，一个图（Graph）是表示物件与物件之间的关系的数学对象，是图论的基本研究对象。

图是十分重要的数据结构，常常被应用于实际生活的应用之中。生活中常见的问题例如交通路线图、任务指定分配、工期计算、航空网络等，都可以使用图相关的理论来建立模型。

下面是《数据结构与算法分析》对图的若干定义

一个图（Graph）G = （V, E）由顶点（vertex）集和边（Edge）集E组成。每一条边就是一个点对（v，w），其中v，w属于集合V。有时也把边Edge叫做弧（arc）。如果点对是有序的，那么图就叫做是有序的（directed）。有向的图有时候叫做有向图。顶点v和w邻接（adjacent）当且仅当（v，w）属于E。在一个具有边（v，w）从而具有边（w，v）的无向图中，w和v邻接且v和w也邻接。有时候边还具有第三种成分，叫做权（weight）或值（cost）。

图的存储

一种简单存储图的方式时采用一个被称为邻接矩阵的二维数组a[i][j]，数组的大小为n * n，n 为图的顶点个数。其中如果顶点i到顶点j连通，那么a[i][j] = 1，否则a[i][j] = 0。这种存储方式的优点是简单直观，实现方便。缺点也很明显，所需要的存储空间巨大。

当含有n个顶点的图G中大多数顶点都不是连通，那么意味中n * n 邻接矩阵中有大量的元素为0，即此时邻接矩阵是稀疏矩阵。

另一种常见的存储方式称为邻接表（adjacent list），这种方式是申请一个大小为n 的数组head，数组元素head[i]，存放着由顶点i的所有邻接顶底组成的链表的头地址。此种存储方式的优点显而易见，相比于前一种方式，存储空间的大小明显减小。但是缺点是不直观，编码有难度。

拓扑排序

拓扑排序是对又向无圈图的顶点的一种排序，它使得如果存在一条从Vi 到Vj 的路径，那么在排序中Vj 必须出现在 Vi 的后面。

一种简单的求拓扑排序的算法先是找出任意一个入度为0的顶点。然后我们输出该顶点，并将它和它的边一起冲图中删除。然后，将其邻接的顶点的入度减去1。然后重复上述过程，直达图被完全删除。

不难看出，此种算法首先是外层循环 n 次，其次是内部循环中在选取入度为0 的顶点时候，会内部循环n次。因此总的时间复杂度会达到n * n。

另一种较好的改进方法是，将所有入度为0的顶点压入某个栈，然后每一次输出顶底元素A后，再将A的所有邻接顶点的入度减去1，如果某个邻接顶点的入度此时为0，那么将其继续入栈。重复上诉操作指导栈空。

可以看出，对每一个入度为0的顶点入栈的操作执行了n 次，n 为顶点数。对出栈的元素A，将其邻接顶点的入度减1，然后入栈的操作，最多执行了 m 次， m 为图边的条数。因此总的时间复杂度就会是线性的 O(n)

代码示例

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 
  5 struct Node {
  6     int value;
  7     int indegree;
  8     struct Node *next;
  9 };
 10 
 11 //初始化邻接表
 12 struct Node* initAdjList(int n) {
 13     struct Node* headers;
 14     headers = (struct Node*)malloc(sizeof(struct Node) * n);
 15     int i = 0;
 16     for(i; i < n; i++) {
 17         headers[i].next = NULL;
 18         headers[i].value = 0;
 19         headers[i].indegree = 0;
 20     }
 21     return headers;
 22 }
 23 
 24 void addAdj(struct Node* header, int m, int n) {
 25     struct Node* p = &header[m];
 26     p->value++;
 27     while(p->next != NULL)
 28         p = p->next;
 29     p->next = (struct Node*)malloc(sizeof(struct Node));
 30     p->next->value = n;
 31     p->next->next = NULL;
 32 }
 33 
 34 //打印邻接表
 35 void printAdjList(struct Node* header, int n) {
 36     int i = 0;
 37     for(i; i < n; i++) {
 38         struct Node* p = &header[i];
 39         printf("Number of %d' adj : %d	", i, p->value);
 40         while(p->next!= NULL) {
 41             printf("%d --->%d	", i, p->next->value);
 42             p = p->next;
 43         }
 44         printf("
");
 45     }
 46 }
 47 
 48 //拓扑排序
 49 int* topSort(struct Node* headers, int n) {
 50     int* zeroStack = (int*)malloc(sizeof(int) * n);
 51     int* result = (int*)malloc(sizeof(int) * n);
 52     int count = 0;
 53     int pIndex = -1;
 54     int i = 0;
 55     while(i < n) {
 56         struct Node* p = &headers[i];
 57         //入度为0，直接进栈
 58         if(p->indegree == 0)
 59             zeroStack[++pIndex] = i;
 60         i++;
 61     }
 62 
 63     while(1) {
 64         //从top里面出栈一个Node Index
 65         int zeroIndex = zeroStack[pIndex--];
 66         result[count++]  = zeroIndex;
 67         struct Node* zeroNode = &headers[zeroIndex];
 68         //将zeroNode的连接点，对应的头结点的值减一
 69         while(zeroNode->next != NULL) {
 70             struct Node* q = &headers[zeroNode->next->value];
 71             if(--q->indegree == 0)
 72                 zeroStack[++pIndex] = zeroNode->next->value;
 73             zeroNode = zeroNode->next;
 74         }
 75         //栈空
 76         if(pIndex < 0)
 77             break;
 78     }
 79 
 80     return result;
 81 }
 82 
 83 int main()
 84 {
 85     int a[7][7] = { {0,1,1,1,0,0,0},
 86                     {0,0,0,0,1,1,0},
 87                     {0,0,0,0,0,0,1},
 88                     {0,0,1,0,0,1,1},
 89                     {0,0,0,1,0,0,1},
 90                     {0,0,0,0,0,0,0},
 91                     {0,0,0,0,0,1,0}
 92                     };
 93     int n = 7;
 94     struct Node* headers = initAdjList(n);
 95     int i = 0;
 96     int j = 0;
 97     for(i = 0; i < n; i++)
 98         for(j = 0; j < n; j++) {
 99             if(a[i][j] == 1)
100                 addAdj(headers, i, j);
101     }
102 
103     //生成各节点indegree
104     for(i = 0; i < n; i++) {
105         struct Node* p = &headers[i];
106         while(p->next != NULL) {
107             headers[p->next->value].indegree++;
108             p = p->next;
109         }
110     }
111 
112     int* q = topSort(headers, n);
113     printAdjList(headers, n);
114     for(i = 0; i < n; i++) {
115         printf("%d 
", *q++ + 1);
116     }
117     return 0;
118 }