文档介绍：河南工程学院《数据结构与算法》课程设计
成果报告
拓扑排序算法实现
2014 年 12 月 29 日
题 目
拓扑排序算法实现
考核项目
考核内容
得分素邻接的顶点的入度减一，若减一后，入度为零，则继续入栈重复上述步骤。
3
：
（1）全部顶点被输出，网中没有回路。
（2）未输出全部顶点，剩余顶点均有前驱，网中有回路。
：
（1）图的邻接表存储形式;
typedef char VertexType[20];//顶点信息（名称）
typedef struct ArcNode//链表结点
{ int vexpos;//该弧所指向的顶点在数组中的位置
struct ArcNode *next;//指向当前起点的下一条弧的指针
} ArcNode;
typedef struct VNode//头结点
{ VertexType name;//顶点信息（名称）
int indegree;//顶点入度
ArcNode *firstarc;//指向当前顶点的第一条弧的指针
} VNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{ AdjList vexhead;//邻接表头结点数组
int vexnum,arcnum;//图的顶点数和弧数
} ALGraph;
（2）链式队列的存储类型为：
typedef int ElemType;
typedef struct QNode
{ ElemType data;
struct QNode *next;
} QNode,*QueuePtr;
typedef struct
{ QueuePtr front;
QueuePtr rear;
} LinkQueue;
4
算法描述
1、采用邻接表存储结构实现有向图；有向图需通过顶点数、弧数、顶点以及弧等信息建立。
2、拓扑排序算法void TopologicalSort(ALGraph G) 中，先输出入度为零的顶点，而后输出新的入度为零的顶点，此操作可利用栈或队列实现。考虑到教学计划安排的实际情况，一般先学基础课（入度为零），再学专业课（入度不为零），与队列先进先出的特点相符，故采用队列实现。
3、拓扑排序算法void TopologicalSort(ALGraph G)，大体思想为：
1)遍历有向图各顶点的入度，将所有入度为零的顶点入队列；
2)队列非空时，输出一个顶点，并对输出的顶点数计数；
3)该顶点的所有邻接点入度减一，若减一后入度为零则入队列；
4)重复2)、3)，直到队列为空，若输出的顶点数与图的顶点数相等则该图可拓扑排序，否则图中有环。
4、要对教学计划安排进行检验，因此编写了检测用户输入的课程序列是否是拓扑序列的算法void TopSortCheck(ALGraph G)，大体思想为：
1)用户输入待检测的课程序列，将其存入数组；
2)检查课程序列下一个元素是否是图中的顶点（课程），是则执行3)，否则输出“课程XX不存在”并跳出；
3)判断该顶点的入度是否为零，是则执行4)，否则输出“入度不为零”并跳出；
4)该顶点的所有邻接点入度减一；
5)重复2)、3)、4)直到课程序列中所有元素均被遍历，则该序列是拓扑序列，否则不是拓扑序列。
程序流程图
当拓扑排序开始时，输入顶点的及弧信息，输入的条件符合时，将会建立新的邻接表，而当入度为零时，将其入栈，弹出栈顶，将与栈顶元素邻接的顶点的入度减一，当栈不为空是继续循环，为空时则输出拓扑排序。
5
流程图如下：
-1流程图
6
3 程序清单
#include<>
#include<>
#define true 1
#define false 0
#define MAX_VEXTEX_NUM 20
#define M 20
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
/*-----------------------图的邻接表存储结构------------------------*/
typedef struct ArcNode /*弧结点结构类型*/
{
int adjvex;