数据结构与算法-拓扑排序

1. 思路

1. 每次需要判断一个顶点的入度，入度为零，说明这个顶点之前没有其他前置顶点了。
   • 入度为零，则用一个数据结构来存储。
     • C语言可以用栈、队列。
     • Swift可以考虑直接用数组。
2. 从入度为零的顶点中取一个出来， 断开它指向的其它顶点。(这里入度是关键，只需要入度减少就行)
3. 如果被指向的顶点入度减一之后为零，则把该顶点加入到栈、队列或数组中(以后的备选顶点)。
4. 备选顶点空了之后，判断最大备选顶点数和总顶点数是否相等。
   • 全部顶点都被输出了，才是拓扑排序，否则存在环。

2. 基础数据结构

这里使用邻接表实现。

• 需要记录、更新入度。
• 遍历边表更快(不涉及不相连的顶点)。

#define MAXVEX 14

//边表结点
typedef struct EdgeNode {
    //邻接点域，存储该顶点对应的下标
    int adjvex;
    //用于存储权值，对于非网图可以不需要
    int weight;
    //链域，指向下一个邻接点
    struct EdgeNode *next;
} EdgeNode;

//顶点表结点
typedef struct VertexNode {
    //顶点入度
    int in;
    //顶点域，存储顶点信息
    int data;
    //边表头指针
    EdgeNode *firstedge;
} VertexNode, AdjList[MAXVEX];

2. 实现

Status TopologicalSort(GraphAdjList GL){
    // 创建一个栈
    int top = -1;
    int *stack = (int *)malloc(sizeof(int) * GL->numVertices);
    
    // 先把所有入度为0的顶点入栈
    for(int i = 0; i < GL->numVertices; i++)
        if(GL->adjList[i].in == 0)
            stack[++top] = i;
    
    EdgeNode *edge; // 辅助遍历边
    int idx; // 顶点的索引
    int count = 0; // 统计遍历顶点的个数，所有顶点都被访问过，拓扑排序才正确
    while (top > -1) {
        idx = stack[top--]; // 拿到栈顶顶点索引，同时出栈
        count++; // 计数+1
        printf(" -> %d", GL->adjList[idx].data); // 输出一下
        
        edge = GL->adjList[idx].firstedge; // 获取边表头结点
        while (edge) {
            idx = edge->adjvex; // 获取顶点索引
            if (--GL->adjList[idx].in == 0) { // 入度-1，同时如果结果==0，则入栈
                stack[++top] = idx;
            }
            edge = edge->next; // 继续遍历
        }
    }
    printf("\n");
    // 所有顶点都被访问过，拓扑排序才正确
    if (count != GL->numVertices) {
        return ERROR;
    }
    return OK;
}