常用数据结构图--拓扑排序

常用数据结构图–拓扑排序

图

在数学中，一个图（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;
}