AOV网的拓扑序列生成-数据结构与算法课程设计报告

数据结构与算法课程设计 实验报告 完整版 带概要分析 详细分析 源代码 测试 参考文献等

题目：AOV网的拓扑序列生成

一、问题分析和任务定义

本次课程设计要求对于给定的AOV网求出它所有拓扑序列。AOV网（Activity on Vertex Network）是一个有向无环图（Directed Acycline Graph，DAG图）。AOV网中，如果顶点Vi表示的活动在和顶点Vj表示的活动之前进行，则称Vi是Vj的前驱顶点，Vj是Vi后继顶点。拓扑排序就是将有向无环图中的各个顶点排成一个序列，使得所有的前去后继关系都得到满足。对于相互之间没有次序关系的顶点，在拓扑排序的序列中可以处在任意的位置。因此，拓扑排序的结果往往是不唯一的。本次课程设计的主要任务就是将给定的一个AOV网输出所有的该种序列。下面以图一为例：

对于该图其所有的拓扑序列如下：

（1）、V0 V1 V2 V3 V4

（2）、V0 V1 V2 V4 V3

（3）、V1 V0 V2 V3 V4

（4）、V1 V0 V2 V4 V3

二、数据结构的选择和概要设计

对于给出的AOV网首先要确定它的存储方式，这里选择邻接表，它的具体数据结构如下图二所示：

typedef struct node{ //邻接表中的结点类型

int number; //结点编号

struct node *next; //指向下一个结点

int info; //与表头结点边的信息

}ListNode;

typedef struct{ //定义表头结点数组

int number; //顶点信息

ListNode *firstarc; //指向第一个邻接点

}AdjList; //表头结点类型

typedef struct{ //邻接表类型

AdjList head[max_vertex_num]; //邻接表的组

int vexnum ,edgnum; //顶点个数、边的个数

}ALGraph;

数据结构与算法课程设计 实验报告 完整版 带概要分析 详细分析 源代码 测试 参考文献等

一种拓扑序列的生成一般有一下步骤：

（1）、从有向无环图中选择一个没有前驱结点的顶点并加入到结点的序列中；

（2）、从有向无环图中删除该顶点以及该顶点为尾的所有的弧；

（3）、重复（1）（2）的步骤。

在整个拓扑排序的过程中需要频繁的检查顶点的前驱以及作删除顶点和弧的操作，在这里我们用两个全局变量rudu[max_vertex_num]和visited[max_vertex_num]来分别实现这两个操作，如果rudu[i]为零则表示无前驱结点，如果visited[i]为零则表示没有被访问过。如果每删除一个结点就检查，那样的话时间复杂度将很大（等于遍历所有的顶点一遍），因此设计一个堆栈，把检测到的入度为零的结点入栈。每次删除顶点只要从栈中取出一个结点即可。这里堆栈也有一个数据结构，具体实现如图三所示：

数据结构与算法课程设计 实验报告 完整版 带概要分析 详细分析 源代码 测试 参考文献等

typedef struct{

int data[max_vertex_num];//堆栈数组

int top;//栈顶标志

}Stack; //顺序表类型

但是如果需要实现一个AOV网所有拓扑序列的生成则不止如此。在每找到一个符合要求的结点后入栈，从而实现一种拓扑排序。在一趟拓扑排序结束后，应该进行恢复删除的结点和删除的弧，并标记已经有过的序列，在恢复某几个个结点后进行下一次的拓扑排序。这里用到递归的思想。具体实现见下面的详细设计。

三、详细设计和编码

本次课程设计的重点在于输出AOV网的所有拓扑序列，因此图的创建即输出之类的问题不做为重点，在此设计过程略过。

对于拓扑排序算法流程图如图四所示：

数据结构与算法课程设计 实验报告 完整版 带概要分析 详细分析 源代码 测试 参考文献等

实现该算法的具体编码如下：

void topusort(Stack *L,ALGraph *G,int i){//拓扑排序

ListNode *P;

int j,k;Soutput(L);

Sinsert(L,i); //把顶点Vi加入到栈中

P=G->head[i].firstarc;

visited[i]=1; //把排序过的点标记

while(P) {

j=P->number;

rudu[j]--; //把以Vi为头的终止结点入度减1

P=P->next;

}

if(L->top+1==G->vexnum){//判断栈中一种拓扑排序完成

Soutput(L);

printf("\n");

flag++;

}

for(k=0;k<G->vexnum;k++)//调用部分

if((visited[k]==0)&&(rudu[k]==0))// 如果Vk在此轮中未被访问过且入度为0 topusort(L,G,k);

visited[i]=0; //使Vi恢复为未访问

P=G->head[i].firstarc;

while(P)

{

j=P->number;

rudu[j]++; //使Vj的入度恢复 ，加1

P=P->next;

}

Sdelete(L);

}

首先建立空栈，并从第一个顶点开始进行拓扑排序。将该结点初始化为被访问过，并将图类的结点指针指向该编号的结点的表头数组firstarc域，把该顶点入栈后，将所有的以它为起点的弧都删掉，即将弧的终点的入度都减一。接着判断栈里面的数据个数是否和图顶点的个数一样，如果一样，则说明已经有一次拓扑排序完成，若不一样，则往下进行递归，再将符合条件的顶点入栈，直到一次拓扑排序完成的条件成立。最后将顶点出栈，恢复所有结点的入度，并准备下一趟拓扑排序。注意，在这里，可能再某一次拓扑排序完成后，所有的结点还没有来得及全部出栈，则发现了又可以入栈的情况如图一中的第二、四种排序就属于这种例子。

四、上机调试

这里我按照做课程设计的过程，将在其中遇到的问题和解决的办法都写在这里。

1、课程设计开始，确定使用什么样的数据结构来存储图的时候，在邻接表和邻接矩阵

之间进行徘徊。课本上使用的事邻接表，我当时想自己重新想，不按照课本上已设计好的来，但是在随后的操作中，发现在对于每个结点进行查找，删除等操作的时候才发现，用邻接矩阵很不方便，也正是在此才明白用邻接表的优越性。

数据结构与算法课程设计 实验报告 完整版 带概要分析 详细分析 源代码 测试 参考文献等

2、接下来就是创建图及输出图的一些函数的编写。这部分比较简单，除了一些语法错

误外没有很严重的错误。这归功于以前在每次做实验的时候，这些基本的算法实现都有，直接按照这里的数据结构复制过来就行了。

3、下面是本次课程设计的核心部分。

（1）、在拓扑排序里面有必须设计一个数据结构来接受从图里面扫描出来没有入度

且没有被访问过的结点。开始的时候对于该数据结构的选择很是犯难，这让

开始一天，程序毫无进展，想过用队列用栈用顺序表，但是思想都很混乱，

在将以前写过的这些基础函数都用到这里还是不能解决问题。结果我想，这

个数据结构到底有什么样的特点，要什么样的功能。基于该数据结构必须实

现要将开始所有的符合条件的顶点保存起来，在判断保存的数据个数是否等

于图的顶点个数后，才将所有的数据的输出，作为一次拓扑排序结束。在此

判断符合栈的先进先出的特点，最终确定使用栈的数据结构。其实在这里对

于栈到底是使用顺序栈还是链栈也是一 …… 此处隐藏：8060字，全部文档内容请下载后查看。喜欢就下载吧 ……