设G = (V,E)是一个具有n个顶点的有向图,V中的顶点序列V1,V2,...Vn.若满足顶点Vi到Vj有一条路径,则在顶点序列Vi必须在Vj之前,则我们称这样的顶点序列为拓扑序列.
所谓拓扑排序,其实就是对一个有向图构造拓扑排序的过程
构造过程会产生2个结果：
- 如果在此王忠的全部顶点被输出,则说明它不存在环(回路)的AOV网
- 如果输出的顶点书少了,说明这个网存在环(回路),不是AOV网
基本思路
从AOV网中选择一个入度为0的顶点输出,然后删除此顶点,并删除以此顶点为尾的弧,继续重复此步骤,知道输出全部顶点或AOV网中不存在入度为0的顶点为止.
代码部分
邻接矩阵结构
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;
构成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;
}
将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++;
}
}
}
}
拓扑排序
/*拓扑排序:解决的是一个工程能否顺序进行的问题!
若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;
}
网友评论