数算---拓扑排序

概念

设G=(V,E) 是一个具有n个顶点的有向图，V中的顶点序号V，V2，....，Vn, 若满足从顶点Vi到Vj有一条路径，如果顶点序列Vi 必须在Vj之前，则我们称这样的顶点序列为拓扑序列，即顶点间有个先后排序问题。
如下的OC和Swift代码编译的过程，存在由编译器前端（Clang\Swift）和编译器后端（LLVM）两部分组成，存在先后顺序。

所谓的拓扑排序，其实就是对一个有向图构造拓扑序列的过程。构造的结果有两种情况：

1. 如果此网中的全部顶点被输出，则说明它是不存在环（回路）的AOV网。
2. 如果输出的顶点数少了，说明这个网存在环（回路），不是AOV网。

思路

如下图中的V0～V13共14个顶点，为有向图，下面就为此图进行拓扑排序：

有向图的数据结构表示用邻接表的方式更适合拓扑的计算过程。根据上图中顶点间的指向，得到下面的邻接表，并用数组将每个顶点的指向情况保存起来，从V0到V3的顺序保存：

基本思路：从AOV网中选择一个入度为0的顶点输出，然后删除此顶点，并删除指向此顶点的狐，直到输出全部顶点或AOV网中不存在入度为0的顶点为止。
在这个过程中，我们还需要借助一个栈来帮助我们存放入度为0的顶点。

1. 创建一个栈，用来存储入度in为0的顶点序号（0～13）；
2. 遍历AOV图中顶点表，判断入度为0的顶点全部入栈。

过程

1. 初始化栈，将V0,V1,V3 入栈，遍历栈，输出栈顶（gettop = 3，并且count = 1），3为V3的序号，即数组中的下标3。循环遍历V3对应的弧链表，找到与V3顶点连接的2个顶点V13和V2，并将其入度减1，则V13和V2的入度in为1。出栈V3的序号3，打印输出3。

   
   
   

   入度减1可以理解为将V3与当前顶点连接的弧删除。继而孤立V3，也就是V3已经遍历过了，可以删除。

   
   

2. 此时栈中还有V0，V1，利用上面同样方法针对V1操作，输出栈顶gettop = 1, count = 2, 遍历顶点V1 连接的弧链表，发现与V2，V4，V8顶点相连接，并将这三个顶点的入度减1，此时V2入度0，V4，V8入度为1， 因为V2入度为0，则将V2序号2入栈。

   
   

3. 如上方式依次对栈顶顶点操作，然后入栈入度为0的顶点。得到最终结果：

   
   最终结果
   

   此时所有输出结果为：3-->1-->2-->6-->0-->4-->5-->8-->7-->12-->9-->10-->13-->11

根据count是否等于顶点总个数来判断是否所有的顶点都已经输出，等于则表示找到了拓扑结构。

代码

#include "stdio.h"
#include "stdlib.h"

#include "math.h"
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXEDGE 20
#define MAXVEX 14
#define INFINITYC 65535

/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Status;

/*邻接矩阵结构 */
typedef struct
{
    int vexs[MAXVEX];
    int arc[MAXVEX][MAXVEX];
    int numVertexes, 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 numVertexes,numEdges;
}graphAdjList,*GraphAdjList;


/*1.构成AOV网图*/
void CreateMGraph(MGraph *G)/* 构件图 */
{
    int i, j;
    
    /* printf("请输入边数和顶点数:"); */
    G->numEdges=MAXEDGE;
    G->numVertexes=MAXVEX;
    
    /* 初始化图 */
    for (i = 0; i < G->numVertexes; i++)
    {
        G->vexs[i]=i;
    }
    
    /* 初始化图 */
    for (i = 0; i < G->numVertexes; i++)
    {
        for ( j = 0; j < G->numVertexes; j++)
        {
            G->arc[i][j]=0;
        }
    }
    
    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;
    
}

/*2.将AOV网图借助邻近矩阵转换成邻接表结构*/
void CreateALGraph(MGraph G,GraphAdjList *GL)
{
    int i,j;
    EdgeNode *e;
    
    //创建图
    *GL = (GraphAdjList)malloc(sizeof(graphAdjList));
    //对图中的顶点数.弧数赋值
    (*GL)->numVertexes=G.numVertexes; 
    (*GL)->numEdges=G.numEdges;
    
    //读入顶点信息，建立顶点表
    for(i= 0;i <G.numVertexes;i++)
    {
        (*GL)->adjList[i].in=0;
        (*GL)->adjList[i].data=G.vexs[i];
        //将边表置为空表
        (*GL)->adjList[i].firstedge=NULL;
    }
    
    //建立边表
    for(i=0;i<G.numVertexes;i++)
    {
        for(j=0;j<G.numVertexes;j++)
        {
            if (G.arc[i][j]==1)
            {
                //创建空的边表结点
                e=(EdgeNode *)malloc(sizeof(EdgeNode));
                //邻接序号为j
                e->adjvex=j;
                // 将当前顶点上的指向的结点指针赋值给e
                e->next=(*GL)->adjList[i].firstedge;
                //将当前顶点的指针指向e
                (*GL)->adjList[i].firstedge=e;
                (*GL)->adjList[j].in++;
                
            }
        }
    }
}

/*3.拓扑排序. 若AOV网图无回路则输出拓扑排序的序列并且返回状态值1,若存在回路则返回状态值0*/
/*拓扑排序:解决的是一个工程能否顺序进行的问题!*/
Status TopologicalSort(GraphAdjList GL){
    
    EdgeNode *e;
    int i,k,gettop;
    //用于栈指针下标
    int top=0;
    //用于统计输出顶点的个数
    int count=0;
    
    //建栈将入度为0的顶点入栈(目的:为了避免每次查找时都要遍历顶点表查找有没有入度为0的顶点)
    int *stack=(int *)malloc(GL->numVertexes * sizeof(int) );
    
    //1.遍历邻接表-顶点表,将入度in为0的顶点入栈
    /*参考图1> 此时stack栈中应该成为0,1,3.即V0,V1,V3的顶点入度为0*/
    for(i = 0; i<GL->numVertexes; i++)
        //将入度为0的顶点入栈
        if(0 == GL->adjList[i].in)
            stack[++top]=i;
    printf("top = %d\n",top);
    
    //2.循环栈结构(当栈中有元素则循环继续)
    while(top!=0)
    {
        //出栈
        gettop=stack[top--];
        printf("%d -> ",GL->adjList[gettop].data);
        
        //输出顶点，并计数
        count++;
        
        //遍历与栈顶相连接的弧
        for(e = GL->adjList[gettop].firstedge; e; e = e->next)
        {
            //获取与gettop连接的顶点
            k=e->adjvex;
            
            //1.将与gettop连接的顶点入度减1;
            //2.判断如果当前减1后为0,则入栈
            if( !(--GL->adjList[k].in) )
                //将k入栈到stack中,并且top加1;
                stack[++top]=k;
        }
    }
    
    /*思考:3 -> 1 -> 2 -> 6 -> 0 -> 4 -> 5 -> 8 -> 7 -> 12 -> 9 -> 10 ->13 -> 11
     这并不是唯一的拓扑排序结果.
     分析算法:将入度为0的顶点入栈的时间复杂度为O(n), 而之后的while 循环,每个顶点进一次栈,并且出一次栈. 入度减1, 则共执行了e次. 那么整个算法的时间复杂度为O(n+e)*/
    
    printf("\n");
    
    //判断是否把所有的顶点都输出. 则表示找到了拓扑排序;
    if(count < GL->numVertexes)
        return ERROR;
    else
        return OK;
}
int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, 拓扑排序!\n");
    MGraph G;
    GraphAdjList GL;
    int result;
    CreateMGraph(&G);
    CreateALGraph(G,&GL);
    result=TopologicalSort(GL);
    printf("result:%d",result);
    return 0;
}