数据结构(18)-图之拓扑排序

作者: xxxxxxxx_123 | 来源:发表于2020-05-16 10:42 被阅读0次

图之拓扑排序，即无环图的排序，无环图也就是图中没有回路。一般地，我们认为施工过程、生产流程、教学安排等一个项目可以分为若干个子项目的项目即为无环图。所以拓扑排序一般用于解决一个流程类的工程能够顺序进行的问题。

在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先级关系，这样的有向图我们称之为AOV网(Activty On Vertex Network)。AOV网中的弧表示活动之间存在先后顺序。

假设 $G=(V,E)$ 是一个具有 $n$ 个顶点的有向图， $V$ 中的顶点序列 $v_1，v_2...v_n$ 满足从顶点 $v_i$ 到 $v_j$ 有一条路径，且在顶点序列中， $v_i$ 必须在 $v_j$ 之前，则我们称这样的顶点序列为一个拓扑序列。而拓扑排序，则是对一个有向图构造拓扑序列的过程。构造的结果又两种，一个是网的全部顶点都被输出，则说明是不存在环的AOV网；一种是输出的顶点少了，则说明存在环，不是AOV网。

对AOV网进行拓扑排序的基本思路是：从AOV网中选择一个入度为0的顶点输出，然后删去次顶点，并且将以此顶点为尾的弧都删除，重复此步骤，知道输出全部顶点或者AOV网中不存在入度为0的顶点位置。由于我们要进行删除操作，使用邻接矩阵就会比较麻烦，而使用邻接表相对来说更方便一些。考虑到始终需要查找入度为0的顶点，我们需要在顶点数组的元素中添加一个字段来记录入度inDegree。顶点元素结构如下：

inDegree	data	firstedge
入度	数据	指向边表的第一个结点

下面我们通过一个具体的示例来看看代码的实现：

拓扑排序示例.png

根据这些数据结构，我们可以先生成一个邻接表。

typedef int TStatus;
// 顶点类型
typedef int VertexType;

typedef struct EdgeNode {
    // 邻接点域 存储邻接点对应的顶点下标
    int adjvex;
    struct EdgeNode *next;
} EdgeNode;

typedef struct VertexNode {
    VertexType data;
    // 指向边表的第一个结点
    EdgeNode *firstEdge;
    // 入度
    int inDegree;
} VertexNode, AdjList[MAX_VEX_COUNT];

typedef struct {
    // 顶点数组
    AdjList adjList;
    int vertexNum, edgeNum;
} AdjListGraph;

typedef struct {
    // 起点下标 终点下标
    int startIndex, endIndex;
} EdgeInfo;

void initEdgeInfos(int edgesNum, int starts[], int ends[], EdgeInfo edges[]) {
    for (int i = 0; i < edgesNum; i++) {
        EdgeInfo *eInfo = (EdgeInfo *)malloc(sizeof(EdgeInfo));
        eInfo->startIndex = starts[i];
        eInfo->endIndex = ends[i];
        edges[i] = *eInfo;
    }
}

void initAdjListGraph(AdjListGraph *graph, int vertexNum, int edageNum, VertexType vertexes[], EdgeInfo edges[]) {
    graph->vertexNum = vertexNum;
    graph->edgeNum = edageNum;
    
    // 写入顶点数组 先将firstEdge置为NULL
    for (int i = 0; i < vertexNum; i++) {
        graph->adjList[i].data = vertexes[i];
        graph->adjList[i].firstEdge = NULL;
        graph->adjList[i].inDegree = 0;
    }
    
    EdgeNode *eNode;
    for (int i = 0; i < edageNum; i++) {
        // 先生成边的结尾结点
        eNode = (EdgeNode *)malloc(sizeof(EdgeNode));
        eNode->adjvex = edges[i].endIndex;
        // 头插法
        eNode->next = graph->adjList[edges[i].startIndex].firstEdge;
        graph->adjList[edges[i].startIndex].firstEdge = eNode;
        graph->adjList[edges[i].endIndex].inDegree += 1;
    }
}

void printAdjListGraph(AdjListGraph graph) {
    for (int i = 0; i < graph.vertexNum; i++) {
        printf("\n");
        EdgeNode *eNode = graph.adjList[i].firstEdge;
        printf("顶点: %d 入度: %d 边表:", graph.adjList[i].data, graph.adjList[i].inDegree);
        while (eNode) {
            printf("%d->%d ", graph.adjList[i].data, graph.adjList[eNode->adjvex].data);
            eNode = eNode->next;
        }
    }
    printf("\n");
}

aov网邻接表.png

进行拓扑排序的时候，我们还需要一个辅助栈来存储入度为0的顶点，避免每次查找是都要去遍历顶点表找入度为0的顶点。

TStatus topologicalOrder(AdjListGraph *graph) {
    
    int *stack = (int *)malloc(sizeof(int) * graph->vertexNum);
    int top = -1;
    
    // 将入度为0的顶点入栈
    for (int i = 0; i < graph->vertexNum; i++) {
        if (graph->adjList[i].inDegree == 0) {
            top += 1;
            stack[top] = i;
        }
    }
    
    // 栈顶元素
    int stackTop;
    // 记录输出的顶点个数
    int count;
    EdgeNode *eNode;
    while (top != -1) {
        // 删除当前顶点
        stackTop = stack[top];
        top -= 1;

        printf("顶点：%d ", graph->adjList[stackTop].data);
        // 计数
        count += 1;
        // 删除以此顶点为尾的弧，即减去入度
        eNode = graph->adjList[stackTop].firstEdge;
        while (eNode) {
            if (!(--graph->adjList[eNode->adjvex].inDegree)) {
                // 将入度为0的顶点入栈
                stack[++top] = eNode->adjvex;
            }
            eNode = eNode->next;
        }
    }
    
    if (count < graph->vertexNum) {
        return T_ERROR;
    }
    
    return T_OK;
}

void topologicalOrderTest() {
    int vertexNumber = 14;
    int edgeNumber = 19;
    int starts[] = {0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 8, 9, 9, 10, 12};
    int ends[] = {11, 4, 5, 4, 8, 2, 5, 6, 2, 13, 7, 8, 12, 5, 7, 11, 10, 13, 9};

    EdgeInfo *eInfos = malloc(sizeof(EdgeInfo) * edgeNumber);
    initEdgeInfos(edgeNumber, starts, ends, eInfos);
    
    AdjListGraph graph;
    VertexType vertexes[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
    initAdjListGraph(&graph, vertexNumber, edgeNumber, vertexes, eInfos);
    printAdjListGraph(graph);
    
    TStatus st = topologicalOrder(&graph);
    printf("%s是AOV网\n", st == T_OK ? "": "不");
}

// 控制台输出：
顶点: 0 入度: 0 边表:0->5 0->4 0->11 
顶点: 1 入度: 0 边表:1->2 1->8 1->4 
顶点: 2 入度: 2 边表:2->6 2->5 
顶点: 3 入度: 0 边表:3->13 3->2 
顶点: 4 入度: 2 边表:4->7 
顶点: 5 入度: 3 边表:5->12 5->8 
顶点: 6 入度: 1 边表:6->5 
顶点: 7 入度: 2 边表:
顶点: 8 入度: 2 边表:8->7 
顶点: 9 入度: 1 边表:9->10 9->11 
顶点: 10 入度: 1 边表:10->13 
顶点: 11 入度: 2 边表:
顶点: 12 入度: 1 边表:12->9 
顶点: 13 入度: 2 边表:

顶点：3 顶点：1 顶点：2 顶点：6 顶点：0 顶点：4 顶点：5 顶点：8 顶点：7 顶点：12 顶点：9 顶点：11 顶点：10 顶点：13 

是AOV网

通过代码可以看出， $m$ 个顶点， $n$ 条弧的AOV网，入栈的时间复杂度为 $O(m)$ ，遍历链表的时间复杂度为 $O(n)$ ，整体的时间复杂度为 $O(m+n)$ 。