图的拓扑排序算法

拓扑排序：对一个有向图构造拓扑序列的过程。

关键概念定义

拓扑序列：设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列v1，v2，……，vn，若满足从顶点vi到vj有一条路径，则在顶点序列中顶点vi必须出现在vj之前。符合这样定义的序列叫拓扑序列。

AOV网：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，就是AOV网。

拓扑排序算法思路：从AOV网中选择一个入度为0的顶点输出，然后删除此顶点，并删除此顶点为尾的弧，重复此步骤，直到输出全部顶点或者AOV网中不存在入度为0的顶点为止。

// 图的拓扑排序算法
#include <stdio.h>
#include <malloc.h>

#define MAXEDGE 20 // 最大边数
#define MAXVEX 14 // 最大顶点数

#define OK 1 // 执行成功
#define ERROR 0 // 执行失败

typedef int Status; // 执行状态

// 邻接矩阵结构
typedef struct {
    int vexs[MAXVEX]; // 顶点表
    int arc[MAXVEX][MAXVEX]; // 边表
    int numNodes, numEdges; // 图中当前的顶点数，边数
} MGraph;

/**************** 用到的邻接表结构 ****************/

// 边表节点
typedef struct EdgeNode {
    int adjvex; // 邻接点域，存储该顶点对应的下标
    int weight; // 用来存储权值（非网图可没有）
    struct EdgeNode *next; // 指向下一个邻接点
} EdgeNode;

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

// 邻接表结构
typedef struct {
    AdjList adjList;// 顶点表数组
    int numNodes, numEdges; // 图中当前顶点数，边数
} graphAdjList, *GraphAdjList;

/*************************************************/

/**
 * 生成邻接矩阵（图）
 * @param G 邻接矩阵（图）
 */
void CreateMGraph(MGraph *G) {
    int i, j; // 用于遍历元素

    G->numEdges = MAXEDGE; // 设置边数
    G->numNodes = MAXVEX; // 设置顶点数

    // 初始化图的顶点表
    for (i = 0; i < G->numNodes; i++) {
        G->vexs[i] = i;
    }

    // 初始化图的边表
    for (i = 0; i < G->numNodes; i++) {
        for (j = 0; j < G->numNodes; j++) {
            G->arc[i][j] = 0; // 设置所有边的默认值为0
        }
    }

    // 设置特定边的权（值为1表示该位置有边）
    G->arc[0][4] = 1;
    G->arc[0][5] = 1;
    G->arc[0][11] = 1;

    G->arc[1][2] = 1;
    G->arc[1][4] = 1;
    G->arc[1][8] = 1;

    G->arc[2][5] = 1;
    G->arc[2][6] = 1;
    G->arc[2][9] = 1;

    G->arc[3][2] = 1;
    G->arc[3][13] = 1;

    G->arc[4][7] = 1;

    G->arc[5][8] = 1;
    G->arc[5][12] = 1;

    G->arc[6][5] = 1;

    G->arc[8][7] = 1;

    G->arc[9][10] = 1;
    G->arc[9][11] = 1;

    G->arc[10][13] = 1;

    G->arc[12][9] = 1;
}

/**
 * 使用邻接矩阵生成邻接表
 * @param G 邻接矩阵
 * @param GL 邻接表
 */
void CreateALGraph(MGraph G, GraphAdjList *GL) {
    int i, j; // 用于遍历元素
    EdgeNode *e; // 边表节点

    *GL = (GraphAdjList) malloc(sizeof(graphAdjList)); // 为邻接表表分配存储空间

    (*GL)->numNodes = G.numNodes; // 设置邻接表的顶点数
    (*GL)->numEdges = G.numEdges; // 设置邻接表的边数

    // 建立顶点表
    for (i = 0; i < G.numNodes; i++) {
        (*GL)->adjList[i].in = 0; // 设置下标为i位置的顶点入读为0
        (*GL)->adjList[i].data = G.vexs[i]; // 存入该顶点的权值
        (*GL)->adjList[i].firstEdge = NULL; // 设置顶点对应的边表为空
    }

    // 建立边表
    for (i = 0; i < G.numNodes; i++) {
        for (j = 0; j < G.numNodes; j++) {
            if (G.arc[i][j] == 1) {
                e = (EdgeNode *) malloc(sizeof(EdgeNode)); // 为边表节点分配存储空间
                e->adjvex = j; // 设置邻接序号为j
                e->next = (*GL)->adjList[i].firstEdge; // 新节点指针指向边表的头节点
                (*GL)->adjList[i].firstEdge = e; // 让新节点成为边表的头节点
                (*GL)->adjList[j].in++; // 边终点所指向的节点入度加1
            }
        }
    }
}

/**
 * 拓扑排序
 * 若邻接表无回路，则输出拓扑排序序列并返回OK，若有回路则返回ERROR
 * @param GL 邻接表
 * @return 执行状态
 */
Status TopologicalSort(GraphAdjList GL) {
    EdgeNode *e; // 边表节点
    int i, k, gettop; // i用于遍历元素，k用来获取顶点下标，gettop用来获取栈顶元素下标
    int top = 0; // 用于栈指针下标
    int count = 0; // 用于统计输出顶点的个数
    int *stack; // 存储入度为0的顶点的栈

    stack = (int *) malloc(GL->numNodes * sizeof(int)); // 为栈分配存储空间

    // 将所有入度为0的顶点入栈
    for (i = 0; i < GL->numNodes; i++) {
        if (GL->adjList[i].in == 0) { // 顶点入度为0
            stack[++top] = i; // 将该节点入栈
        }
    }

    // 未把所有入度为0的顶点出栈
    while (top != 0) {
        gettop = stack[top--]; // 获取入度为0的栈的栈顶元素
        printf("%d -> ", GL->adjList[gettop].data); // 打印该元素的顶点信息
        count++; // 输入顶点个数加1

        // 遍历该顶点的边表
        for (e = GL->adjList[gettop].firstEdge; e; e = e->next) {
            k = e->adjvex; // 获取下个顶点（边终点所指向的节点）的下标

            // 将边终点所指向的节点的入度减1，如果该顶点入读为0，将顶点入栈
            if (!(--GL->adjList[k].in)) {
                stack[++top] = k; // 将顶点入栈
            }
        }
    }
    printf("\n");

    // 输出的顶点数小于邻接表的顶点数，邻接表中有回路，拓扑排序失败
    if (count < GL->numNodes) {
        return ERROR;
    } else { // 邻接表中无回路，拓扑排序成功
        return OK;
    }
}

int main() {
    MGraph G; // 邻接矩阵
    GraphAdjList GL; // 邻接表
    Status status; // 执行状态

    CreateMGraph(&G); // 创建邻接矩阵
    CreateALGraph(G, &GL); // 使用邻接矩阵创建邻接表

    status = TopologicalSort(GL); // 将邻接表进行拓扑排序，获取执行状态
    printf("status: %s", status == OK ? "执行成功" : "执行失败");

    return 0;
}

运行结果