常用数据结构图–拓扑排序
图
在数学中,一个图(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 <stdio.h>
- #include <stdlib.h>
-
-
- 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;
- }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119