拓扑排序 - 简书

基本概念

定义：由某个集合上的一个偏序得到该集合上的全序的过程。

离散数学相关概念

偏序：若集合X上的关系R是自反的、反对称的和传递的、则称R是集合X上的偏序关系。
全序：设R是集合X上的偏序。如果对每个x，y∈X必有xRy或yRx，则称R是集合X上的全序关系。

偏序与全序的有向图

由上图所示在（b）图表示全序，而（a）的有向图上人为地加上一个表示V₂<V₃的弧（表示V₂领先于V₃）则（a）表示的亦为全序，这个全序称为拓补有序，由偏序定义得到拓补有序的操作便是拓补排序。
表示偏序的有向图可以用来表示流程图。图中的每一条边表示两个子工程之间的次序关系。

AOV网（Activity on vertex Network）

定义：用顶点表示活动，用弧表示活动间的优先关系的有向图称为定点表示活动的网。顾名思义。

在网中，若从顶点i到另一顶点j之间有一条有向路径，则称i为j的前驱，j为i的后继。
在AOV网中不应该出现有向环，因为存在环意味着某项活动会以自己为先决条件，这是不对的。因此要对给定的AOV网进行判断是否有环。检测方法就是对AOV网进行拓补排序，若所有顶点都在拓补有序序列中，则AOV网中必没有环。

拓补排序的实现

在有向图中选择没有前驱的点的顶点并将其输出。
从图中删除该顶点和所有以它为尾的弧。
重复上面的两部，直到所有顶点均已经输出。

采用邻接表作有向图的存储结构。
声明存放顶点入度的数组 Indegree，入度为零的顶点即为没有前驱的顶点。
删除顶点以及以它为尾的弧的操作，则可更换为弧头顶点入度减一的操作。
为了避免重复检测入度为零的情况。另设一个线性表（栈或队列，根据题内特殊要求而定，就拓补排序定义而言无差别）暂存所有在删除弧操作后产生的新的入度为零的点。

复杂度分析

对于有n个顶点和e条弧的有向图而言总的时间复杂度为O（n+e）

代码

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 40
//图的邻接矩阵表示方式
typedef enum {DG,DN,UDG,UDN} GraphKind;
typedef struct ArcNode{
    int adjvexNum; //该弧所指向的顶点在图的定点结构体组中的下角标
    struct ArcNode *nextarc;
}ArcNode;
typedef struct VexNode{
    ArcNode *firstarc;
    char data;
}VexNode,AdjList[MAX_VERTEX_NUM];
typedef struct {
    AdjList vertice;
    int vexnum,arcnum;  // 图当前顶点数和边数
    GraphKind kind; //图的种类类型
}MGraph;
int Visited[MAX_VERTEX_NUM] = {0};
int Indegree[MAX_VERTEX_NUM] = {0};
void Insert(char a,char b,MGraph &G){
    int vex1,vex2;
    for(int i = 0; i < G.vexnum; i++){
        if(a == G.vertice[i].data){
            vex1 = i;
        }
        if(b == G.vertice[i].data){
            vex2 = i;
        }
    }
    Indegree[vex2]++;
        ArcNode *arcNode = (ArcNode*)malloc(sizeof(ArcNode)); //初始化所有边 
        arcNode->nextarc = NULL;
        arcNode->adjvexNum = vex2;
        
        if(G.vertice[vex1].firstarc == NULL){    //将边加入到邻接表 
            G.vertice[vex1].firstarc = arcNode;
        }
        else{
            ArcNode *t = NULL;
            ArcNode *pre = NULL;
            for(t = G.vertice[vex1].firstarc;t != NULL;t = t->nextarc){
                pre = t;
            }
            pre->nextarc = arcNode;
        }
}

void CreateGraph(MGraph &G){
    //scanf("%d %d",&G.vexnum,&G.arcnum);
    G.vexnum = 11;
    G.arcnum = 21;
    for(int i = 0; i < G.vexnum; i++) {  //初始化所有顶点
        G.vertice[i].firstarc = NULL;
    }
    G.vertice[0].data = 'S';
    G.vertice[1].data = 'A';
    G.vertice[2].data = 'B';
    G.vertice[3].data = 'C';
    G.vertice[4].data = 'D';
    G.vertice[5].data = 'E';
    G.vertice[6].data = 'F';
    G.vertice[7].data = 'G';
    G.vertice[8].data = 'H';
    G.vertice[9].data = 'I';
    G.vertice[10].data = 'T';
    //for(int k = 0; k < G.arcnum; k++){
    // int vex1,vex2,weight;  //输入一条边的起点和终点以及这条边的权值 
    //  scanf("%d %d",&vex1,&vex2); 
    //}
    char a[21]={
        'S','S','S','A','A','B','C','D','D','E','E','E','F','F','G','G','G','H','H','I','I'
    };
    char b[21]={
    'A','D','G','B','E','C','T','A','E','C','F','I','C','T','D','E','H','E','I','F','T'
    };
    for(int i = 0; i < G.arcnum; i++){
            Insert(a[i],b[i],G);
    }
}
typedef struct Node{
    int data;
}QNodes[100];
typedef struct Queue{
    int head;
    int tail;
    QNodes qNodes;
}Queue;
void TopologicalSort(MGraph G){
    int TopNum[MAX_VERTEX_NUM] = {0};
    Queue queue;
    queue.tail = 0;
    queue.head = 0;
    int counter = 0;
    for(int i = 0; i < G.vexnum;i++) {
        if(Indegree[i] == 0) {
            queue.qNodes[queue.tail].data = i;
            queue.tail++;
        }
    }
        while(queue.tail != queue.head){
            int p = queue.qNodes[queue.head].data;
            queue.head++;
            TopNum[counter] = p;
            counter++;
            for(ArcNode *t = G.vertice[p].firstarc;t;t = t->nextarc){
                Indegree[t->adjvexNum]--;
                if(!Indegree[t->adjvexNum]){
                    queue.qNodes[queue.tail].data = t->adjvexNum;
                    queue.tail++;
                }
            }
        }
    for(int i = 0; i < counter; i++){
          printf("%c,",G.vertice[TopNum[i]].data);
    } 
}
int main(){
    MGraph graph;
    CreateGraph(graph);
    TopologicalSort(graph);
}