拓扑排序

拓扑排序 - 简介

设G= (V, E) 是一个具有n个顶点的有向图，V中的顶点序列V1, V2,…Vn.满足从顶点Vi到顶点Vj有一条路径，则在定点序列Vi必须在Vj之前，则我们成这样的顶点需列成为拓扑序列
所谓拓扑排序，其实就是对一个有向图构造序列的过程
构造过程拓扑序列会产生2个结果

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

AOV网
存储用邻接表

算法分析：
算法思路
从AOV网中选择一个入度为0的顶点输出，然后从删去次顶点，并删除依此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或AOV网中不存在入度为0的顶点未知。

在这个算法实现过程，我们需要接祖一个数据结构栈，来帮助我们解决避免每次查找时，都要去遍历AOV图中的顶点表查找有没有入度为0的顶点。

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

 同样的方式进行执行，知道执行结束

代码实现

#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));//邻接序号为je->adjvex=j;// 将当前顶点上的指向的结点指针赋值给ee->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;elsereturn 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;
}

Hello, 拓扑排序!
top = 3
3 -> 1 -> 2 -> 6 -> 0 -> 4 -> 5 -> 8 -> 7 -> 12 -> 9 -> 10 -> 13 -> 11 ->