常用数据结构图–拓扑排序
图
在数学中，一个图（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)
代码示例
#include#include struct Node { int value; int indegree; struct Node *next;};//初始化邻接表struct Node* initAdjList(int n) { struct Node* headers; headers = (struct Node*)malloc(sizeof(struct Node) * n); int i = 0; for(i; i < n; i++) { headers[i].next = NULL; headers[i].value = 0; headers[i].indegree = 0; } return headers;}void addAdj(struct Node* header, int m, int n) { struct Node* p = &header[m]; p->value++; while(p->next != NULL) p = p->next; p->next = (struct Node*)malloc(sizeof(struct Node)); p->next->value = n; p->next->next = NULL;}//打印邻接表void printAdjList(struct Node* header, int n) { int i = 0; for(i; i < n; i++) { struct Node* p = &header[i]; printf("Number of %d' adj : %d\t", i, p->value); while(p->next!= NULL) { printf("%d --->%d\t", i, p->next->value); p = p->next; } printf("\n"); }}//拓扑排序int* topSort(struct Node* headers, int n) { int* zeroStack = (int*)malloc(sizeof(int) * n); int* result = (int*)malloc(sizeof(int) * n); int count = 0; int pIndex = -1; int i = 0; while(i < n) { struct Node* p = &headers[i]; //入度为0，直接进栈 if(p->indegree == 0) zeroStack[++pIndex] = i; i++; } while(1) { //从top里面出栈一个Node Index int zeroIndex = zeroStack[pIndex--]; result[count++] = zeroIndex; struct Node* zeroNode = &headers[zeroIndex]; //将zeroNode的连接点，对应的头结点的值减一 while(zeroNode->next != NULL) { struct Node* q = &headers[zeroNode->next->value]; if(--q->indegree == 0) zeroStack[++pIndex] = zeroNode->next->value; zeroNode = zeroNode->next; } //栈空 if(pIndex < 0) break; } return result;}int main(){ int a[7][7] = { { 0,1,1,1,0,0,0}, { 0,0,0,0,1,1,0}, { 0,0,0,0,0,0,1}, { 0,0,1,0,0,1,1}, { 0,0,0,1,0,0,1}, { 0,0,0,0,0,0,0}, { 0,0,0,0,0,1,0} }; int n = 7; struct Node* headers = initAdjList(n); int i = 0; int j = 0; for(i = 0; i < n; i++) for(j = 0; j < n; j++) { if(a[i][j] == 1) addAdj(headers, i, j); } //生成各节点indegree for(i = 0; i < n; i++) { struct Node* p = &headers[i]; while(p->next != NULL) { headers[p->next->value].indegree++; p = p->next; } } int* q = topSort(headers, n); printAdjList(headers, n); for(i = 0; i < n; i++) { printf("%d \n", *q++ + 1); } return 0;}