一、定义

在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为AOV(Activity On Vertex Network)。
注意：AOV网中不存在回路
设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列V₁， V₂，...， V_n满足若从顶点V_i到V_j有一条路径，则在顶点序列中，顶点V_i必须在顶点V_j之前，我们称这样的顶点序列为拓扑序列。
拓扑排序其实就是对一个有向图构造拓扑序列的过程。

二、算法思路

从AOV网中选择一个入度为0的顶点V0入输出。
删除V0结果，并删除以此顶点为尾的弧。
继续重复1、2步骤，直至输出全部顶点或者AOV网中不存在入度为0的顶点为止。
如果此网的顶点全部被输出，则说明它是不存在环路的AOV网，如果输出顶点数少了，哪怕是少了一个，也说明这个网存在环路，不是AOV网。

三、算法实现

#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){
    (*GL) = (GraphAdjList)malloc(sizeof(graphAdjList));
    (*GL)->numVertexes = G.numVertexes;
    (*GL)->numEdges = G.numEdges;
    
    for(int i = 0; i<G.numVertexes; i++){
        (*GL)->adjList[i].in = 0;
        (*GL)->adjList[i].data = G.vexs[i];
        (*GL)->adjList[i].firstedge = NULL;
    }
    
    for(int i = 0; i<G.numVertexes; i++){
        for(int j = 0; j<G.numVertexes; j++){
            if(G.arc[i][j] == 1){
                EdgeNode* e = (EdgeNode*)malloc(sizeof(EdgeNode));
                e->adjvex = j;
                e->next = (*GL)->adjList[i].firstedge;
                (*GL)->adjList[i].firstedge = e;
                (*GL)->adjList[j].in++;
            }
        }
    }
}

/*3.拓扑排序. 若AOV网图无回路则输出拓扑排序的序列并且返回状态值1,若存在回路则返回状态值0*/
/*拓扑排序:解决的是一个工程能否顺序进行的问题!*/
Status TopologicalSort(GraphAdjList GL){
    //栈用于存储入度为0的顶点
    int* stack = (int *)malloc(GL->numVertexes * sizeof(int));
    int stackTop = 0;
    int count = 0;
    
    for(int i = 0; i<GL->numVertexes; i++){
        if(GL->adjList[i].in == 0){
            stack[++stackTop] = i;
        }
    }
    while(stackTop != 0){
        int i = stack[stackTop--];
        printf("%d ", i);
        count++;
        for(EdgeNode* p=GL->adjList[i].firstedge; p; p=p->next){
            GL->adjList[p->adjvex].in-- ;
            if(GL->adjList[p->adjvex].in == 0){
                stack[++stackTop] = p->adjvex;
            }
        }
    }
    printf("\n");
    if(count != GL->numVertexes)
        return ERROR;
    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;
}

四、算法复杂度
分析整个算法，对于一个具有n个顶点e条弧的AOV网来说，扫描顶点表，将入度为0的顶点入栈的时间复杂度为O(n)，而之后的while循环中，每个顶点进一次栈出一次栈，入度减1的操作共执行了e次，因此整个时间复杂度为O(n+e)。

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

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

一、定义

二、算法思路

三、算法实现