拓扑排序课程设计报告

须满足活动之间先后关系，需要将各活动排一个先后次序即为拓扑排序。编

写算法建立有向无环图，主要功能如下：

1.

能够求解该有向无环图的拓扑排序并输出出来；

2.

拓扑排序应该能处理出现环的情况；

3.

顶点信息要有几种情况可以选择。

1.2

课程设计要求

1.

输出拓扑排序数据外，还要输出邻接表数据；

2.

参考相应的资料，独立完成课程设计任务；

3.

交规范课程设计报告和软件代码。

1

沈阳航空航天大学课程设计报告

2

课程设计原理

2.1

课设题目粗略分析

本课设题目要求编 写算法能够建立有向无环图，有向无环图，顾名思义，即一个

无环的有向图，是一类较有 向图更一般的特殊有向图。

其功能要求及个人在写程序时对该功能的实现作如下分析：

1.

将图以合适的方式存储起来。图有多种存储方式，其中最 常用的存储方式有图

的邻接矩阵和邻接表。本人在构思时使用邻接表来建立有向无环图， 将其存储起

来；

2.

求解该有向无环图的拓扑排序，并将其输出出来。若通过构造，建立了一个有

向无环图，那么一定可以求出其拓扑排序，其原理比较简单。即统计每个节点的

入度，将 入度为

0

的结点提取出来，然后再统计剩下的结点的入度，再次 将入度

为零的结点提取出来，以此类推，这样就形成了一个序列，这样的序列就是该图< /p>

的拓扑排序序列；

3.

拓扑排序算法应能够处理出现环的情况。个人在写程序时，考虑到构造图时，

会有构造成有向有环图的情况，应该在运行程序时，试着统计依次按照入读为零

的节点输 出的节点数是否为整个节点的总数，如果是，那么拓扑排序成功，输出

拓扑排序的结果， 否者输出“有环出现”

；

4.

输出除拓扑排序外，还要求输出邻接表数据。由于图是用邻接表存储的，所以

将邻接表按照顺序依次打印输出。

2.2

原理图介绍

2.2.1

功能模块图

2

沈阳航空航天大学课程设计报告

拓扑排序算法

图的建立

打印邻接表

图

2.1

功能模块图

拓扑排序

邻

接

矩

阵

邻

接< /p>

表

行

有

向

无

环

图

可

入

读

为

零

的

依

次

输

出

2.2.2

流程图分析

1.

如图

2 .2

所示，

根据题目要求建立一个有向无环图，

按照提示，

依次输入

节点数和变数，然后输入两个联通 的节点

，前者指向后者，当输入边数为所

。

开始

N

Y

图

2.2

建立有向无环图

3

建立有向无环图

输入节点数

i

，边数

n

，

j=0

j

j=j+1

输入确定弧的两点

结束

沈阳航空航天大学课程设计报告

2.

如图

2.3

所示，

判断有向图是否为有向无 环图。

按照输入的有向图建立一

个邻接表，将图储存在邻接表中 ，并将邻接表打印，然后对该邻接表进行拓扑排

序，依次取入度为零的节点，入栈，并删 除该节点和该节点有关的所边，若入栈

节点个数与节点数相同，则全部入栈，该图为无环 图，可以进行拓扑排序，若该

图节点数大于入栈节点数，则该图为有环图。

N

入栈节点数等

于节点总数

Y

图

2.3

判断是否为无环图

开始

建立邻接表并打印

取入度为零的节点 入

栈，删除该节点，继

续遍历其他节点

该图为无环图

该图为有环图

结束

4

沈阳航空航天大学课程设计报告

3.

此时 该图为有向无环图，可进行拓扑排序，在上一过程中，所有节点已

经入栈，

将栈顶弹出进入另一个空栈，

，然后依次输出栈顶，

拓扑排序成功。如图

2.4

所示。

开始

输出栈顶元素

将弹出的栈顶进入

新的空栈

将栈顶依次输出

拓扑排序成功

结束

图

2.4

输出拓扑排序结果

5

沈阳航空航天大学课程设计报告

4.

具体内容

开始

输入节点及弧的信息

-

符合条件？

根据输入信息建立邻接表

建栈

寻找入度为零的节点入栈

弹出栈顶， 打印，将与栈顶元

素邻接的节点入度减一

栈是否为空

结束

-

图

2.5

拓扑排序

6

沈阳航空航天大学课程设计报告

3

数据结构分析

3.1

存储结构

一个无环的有向图叫 做有向无环图，简称

DAG

图。本算法首先要建立一个

有向无环图，即通过输入各边的数据，搭建图的结构。对于图的存储，用到邻接

< br>表，是一种链式存储结构。

弧结点结构类型：

typedef struct ArcNode

{

int adjvex;

/*

该弧 指向的顶点的位置

*/

struct ArcNode *nextarc;

/*

指向下一条弧的指针

}ArcNode;

邻接表头结点类型：

typedef struct VNode

{

int data;

/*< /p>

顶点信息

*/

ArcNode *firstarc;

/*< /p>

指向第一条依附于该点的弧的指针

*/

}VNode,AdjList[MAX_VEXTEX_NUM];

< br>

3.2

算法描述

1.

邻接表的构建

创建一个邻接表，首先 要输入节点数和边数，然后输入确定一条边的两个节

点，通过输入顺序来确定边的方向， 构成有向图，具体方法如下：

初始化头结点

for (i=1; i<=G->vexnum;i++)

{

G->vertices[i].data=i;

/*

编写 顶点的位置序号

*/

G->vertices[i].firstarc=NULL;

}

先将头结点清零，编写顶点位置序号。

输入确定弧的两点，

如果输入数字大于节点数或者小于零，

则 输出错误信息，

7

沈阳航空航天大学课程设计报告

并重新输入一组节点，申请新的节点来储存新的节点信息，该 弧指向位置编号为

m

的节点，下一条弧指向的是依附于

n

的第一条弧，最后打印生成的邻接表。

for (i=1;i<=G->arcnum;i++)

{

pri ntf(

输入确定弧的两个顶点

u

，< /p>

v:

scanf(

while (n<0||n>G->vexnum||m<0||m>G->vexnum)

{

printf(

输入的顶点序号不正确

请重新输入

:

scanf(

}

p=(ArcNode*)malloc(sizeof(ArcNode));

/*

开辟新的弧结点

*/

< br>

if(p==NULL)

{

printf(

exit(1);

}

p->adjvex=m;

/*< /p>

该弧指向位置编号为

m

的结点

p->nextarc=G->vertices[n].firstarc;

G->vertices[n].firstarc=p;

}

pri ntf(

建立的邻接表为

:n

/*

打印生成的邻接表（以一定的格式）

*/

for(i=1;i<=G->vexnum;i++)

{

printf(

for(p=G->vertic es[i].firstarc;p;p=p->nextarc)

printf(

printf(

8

沈阳航空航天大学课程设计报告

邻接表构建完成。

2.

入栈操作

在本算法中栈主要用来构造 拓扑排序序列。由于栈具有先入后出的特点，所

以，将每次选择入度为零的结点入栈，这 样当结点都入栈的时候，再依次出栈，

进入另一个新栈，这样，排序序列显而易见。它将 图这样的非线性结构转化为栈

这样的线性结构。

建立空栈

typedef struct

{

int *base;

/*

栈底指针

*/

int *top;

< br>/*

栈顶指针

*/

int stacksize;

}SqStack;

初始化栈

void InitStack(SqStack *S)

{

S->base=(int *)malloc(STACK_INIT_SIZE*sizeof(int));

if(!S->base)

/*< /p>

存储分配失败

*/

{

printf(

exit(1);

}

S->top=S->base;

S->stacksize=STACK_INIT_SIZE;

}

入栈操作，压入新的元素为栈顶，

e

为新的栈顶元素。

void Push(SqStack *S,int e)

/*

压入新的元素为栈顶

*/

{

9

沈阳航空航天大学课程设计报告

if(S->top-S->base>=S->stacksize)

{

S->base=(int

*)r ealloc(S->base,(S->stacksize+STACKINCREMENT)*sizeo f(int));

if(!S->base)

{

printf(

exit(1);

}

S->top=S->base+S->stacksize;

S->stacksize+=STACKINCREMENT;

}

*S->top++=e;

}

3.

拓扑排序

本程序的拓扑排序，

必须在图的邻接表已知的情况下。

它还有另外一个功能：

判断一个图是不是无环图。确切的说，不能单纯的叫拓扑排序，但考虑它主要的

作用，在不引起误解的情况下就叫拓扑排序算法。

判断一个 图是否为有向无环图并进行拓扑排序，对于本题目来说，由于本题

要求是对有向无环图进 行拓扑排序，其主要方法是将入度为零的结点依次输出出

来，知道图的所有定点全部输出 为止。那么若图为有环图，在环上的结点在其他

结点都选择出来后，入度都不为零，即无 法被输出出来。那么就可以认为按照拓

扑排序的方法输出结点后，若不是将节点全部输出 出来的，则此图为有环图。输

出有向图有环，拓扑排序失败。若无环，则进行拓扑排序。 通过入栈出栈的操作

来完成拓扑排序。主要算法如下：

void TopoSort(ALGraph G)

{

int indegree[M];

int i, k, n;

10