当前位置：首页 > article >正文

数据结构(6.4_6)——拓扑排序

article 2024/12/22 0:16:29

AOV网

AOV网：用顶点表示活动的网。

用DAG图(有向无环图)表示一个工程，顶点表示活动，有向边<Vi,Vj>表示活动Vi必须先于vj进行

拓扑排序（找到做事的先后顺序）

对有回路的图进行拓扑排序

拓扑排序的实现代码

回顾：入度即为以顶点为终点的边的数目

#include <stdio.h>

// 假设已经定义了Graph结构体和相关函数

bool TopologicalSort(Graph G) {
    // 初始化一个栈S，用于存储入度为0的顶点
    InitStack(S);

    // 遍历所有顶点，寻找入度为0的顶点并将其压入栈S
    for (int i = 0; i < G.vexnum; i++)
        if (indegree[i] == 0) // 如果顶点i的入度为0
            Push(S, i); // 将顶点i压入栈S

    // 初始化计数器，用于记录已经输出的顶点数
    int count = 0;

    // 当栈S不为空时，循环执行以下操作
    while (!IsEmpty(S)) {
        // 弹出栈顶元素，并将其赋值给变量i
        Pop(S, i);
        // 将顶点i记录在输出数组print中，并增加计数器
        print[count++] = i;

        // 遍历顶点i的所有邻接顶点
        for (p = G.vertices[i].firstarc; p; p = p->nextarc) {
            // 获取顶点i指向的顶点v
            v = p->adjvex;
            // 将顶点v的入度减一
            if (!(--indegree[v]))
                // 如果顶点v的入度减为0，则将其压入栈S
                Push(S, v);
        }
    }//while循环结束

    // 如果输出的顶点数小于图中顶点的总数，说明有向图中有回路，拓扑排序失败
    if (count < G.vexnum)
        return false;
    else
        // 否则，拓扑排序成功
        return true;
}

代码思路：

通过for循环将所有度为0结点的indgree[]下标压入栈中，并初始化print[]数组，使其所有元素为-1，方便记录，再将count指向第一个print数组元素，任何进行while判断，如果栈不为空，则将栈顶元素i弹出栈并进入print数组，count指向下一个数组元素，再通过for循环遍历图中i的所有邻结点，将其度-1，若度为零则将度为0的indree数组元素压入栈中，重复直到栈中没有元素，若print数组中的元素小于图中顶点总数，则有向图中有回路。

拓扑排序的时间复杂度

逆拓扑排序

#include <stdio.h>

// 假设已经定义了Graph结构体和相关函数，以下是逆拓扑排序的代码

bool ReverseTopologicalSort(Graph G){
    // 初始化一个栈S，用于存储出度为0的顶点
    InitStack(S);
    
    // 遍历所有顶点，寻找出度为0的顶点并将其压入栈S
    for (int i = 0; i < G.vexnum; i++)
        if (outdegree[i] == 0) // 如果顶点i的出度为0
            Push(S, i); // 将顶点i压入栈S
    
    // 初始化计数器，用于记录已经输出的顶点数
    int count = 0;
    
    // 当栈S不为空时，循环执行以下操作
    while (!IsEmpty(S)) {
        // 弹出栈顶元素，并将其赋值给变量i
        Pop(S, i);
        // 将顶点i记录在输出数组print中，并增加计数器
        print[count++] = i;
        
        // 遍历顶点i的所有邻接顶点
        for (p = G.vertices[i].firstarc; p; p = p->nextarc) {
            // 获取顶点i指向的顶点v
            v = p->adjvex;
            // 将顶点v的出度减一
            if (!(--outdegree[v]))
                // 如果顶点v的出度减为0，则将其压入栈S
                Push(S, v);
        }
    }//while循环结束
    
    // 如果输出的顶点数小于图中顶点的总数，说明有向图中有回路，逆拓扑排序失败
    if (count < G.vexnum)
        return false;
    else
        // 否则，逆拓扑排序成功
        return true;
}

使用邻接矩阵进行拓扑排序

#include <stdio.h>

// 假设已经定义了Graph结构体和相关函数，以下是逆拓扑排序的代码

// Graph结构体可能如下定义
typedef struct {
    int vexnum;       // 顶点数
    int **arc;        // 邻接矩阵
    int *outdegree;   // 每个顶点的出度数组
} Graph;

bool ReverseTopologicalSort(Graph G) {
    int stack[G.vexnum]; // 使用数组作为栈，存储出度为0的顶点
    int top = -1;        // 栈顶指针
    int count = 0;       // 记录已经输出的顶点数
    int print[G.vexnum]; // 存储逆拓扑排序的结果
    int i, j;

    // 初始化栈和输出数组
    for (i = 0; i < G.vexnum; i++) {
        if (G.outdegree[i] == 0) {
            stack[++top] = i; // 出度为0的顶点入栈
        }
    }

    // 当栈不为空时，执行以下操作
    while (top != -1) {
        i = stack[top--]; // 出栈
        print[count++] = i; // 输出顶点i
        
        // 遍历邻接矩阵的第i行
        for (j = 0; j < G.vexnum; j++) {
            // 如果顶点i到顶点j有边，则减少顶点j的出度
            if (G.arc[i][j]) {
                G.outdegree[j]--;
                // 如果顶点j的出度变为0，则将其入栈
                if (G.outdegree[j] == 0) {
                    stack[++top] = j;
                }
            }
        }
    }

    // 如果输出的顶点数小于图中顶点的总数，说明有向图中有回路，逆拓扑排序失败
    if (count < G.vexnum) {
        return false;
    } else {
        // 否则，逆拓扑排序成功
        return true;
    }
}