拓扑排序数据结构课程设计报告图形演示

拓扑排序问题描述：若用有向网表示教学计划，其中顶点表示某门课程，有向边表示课程之间的先修关系（如果A课程是B课程的先修课程，那么A到B之间有一条有向边从A 指向B）。

试设计一个教学计划编制程序，获取一个不冲突的线性的课程教学流程。

（课程线性排列，每门课上课时其先修课程已经被安排）。

基本要求：（1）输入参数：课程总数，每门课的课程号（固定占3位的字母数字串）和直接先修课的课程号。

（2）若根据输入条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。

需求分析：（测试数据加强版）1、输入形式：第一行是是个整数t，表示有t组测试数据；每一组测试数据的第一行是一个整数n,表示结点数目接下来的n行是n个顶点的信息接下来的一行是一个整数m，表示有向边的数目接下来是m行数据每一行是一条有向边的起止结点信息2、输出形式：如果可以实现拓扑排序，输出其得到的合法线性序列否则，输出“Input Error!”；3、功能描述：帮助判断当前的课程是否可以安排得当；如果得当，输出一个合法的修读顺序；4、样例输入输出：输入：25MathEnglishPhysicsChineseMusic5Math EnglishMath PhysicsEnglish ChinesePhysic ChineseChinese Music5MathEnglishPhysicsChineseMusic4Math EnglishMath PhysicsEnglish ChinesePhysic Chinese输出：Input Error！Math English Physics Chinese Music抽象数据结构类型描述（ADT）：采用邻接表的方式来存储数据：抽象数据类型描述：Typedef struct Arc * link;struct Arc{Int adjvex;//邻接点编号Char info[15];//存储结点信息Link nextarc;//指向下一个邻接点};Struct Vex{Char info; //顶点信息Int indgree;//顶点的入度Link firstarc; //指向下一个邻接点};概要设计：算法主题思想：<1>、在有向图中选择一个没有前驱的顶点，输出之；<2>、从有向图中删除该顶点和所有以该顶点为尾的边；<3>、重复上述步骤，直到全部顶点都已经输出了或者图中剩下的顶点都不满足上述的两个条件位置。

indegree first adjvex next
10
4
3
22 ^
p
31
5
2^
41
5^
52 ^
60
5
4^
2^
4
3
2
1
top
0
输出序列：6 1
indegree First adjvex next
10
4
3
22 ^
p
31
5
2^
40
5^
52 ^
60
5
4^
2^
4
3
2
1
top
40
输出序列：6 1
indegree first adjvex next
10
4
3
20 ^
30
5
2^
40
5^
p
51 ^
60
5
4^
2^
4
3
top
2
21
40
输出序列：6 1 3
indegree first adjvex next
10
4
3
20 ^
30
5
2^
40
5^
51 ^
60
5
4^
2^ p=NULL
4
3
top
2
21
40
输出序列：6 1 3
indegree first adjvex next
10
4
3
21 ^
30 40
5
2^
5
p ^
52 ^
60
5
4^
2^

实验题目：图的应用实验目的：（1）熟练掌握图的基本存储方法；（2）熟练掌握图的深度优先和广度优先搜索方法；（3）掌握AOV网和拓扑排序算法；（4）掌握AOE网和关键路径。

实验内容：拓扑排序。

任意给定一个有向图，设计一个算法，对它进行拓扑排序。

拓扑排序算法思想：a.在有向图中任选一个没有前趋的顶点输出；b.从图中删除该顶点和所有以它为尾的弧；c.重复上述a、b，直到全部顶点都已输出，此时，顶点输出序列即为一个拓朴有序序列；或者直到图中没有无前趋的顶点为止，此情形表明有向图中存在环。

设计分析：为实现对无权值有向图进行拓扑排序，输出拓扑序列，先考虑如何存储这个有向图。

拓扑排序的过程中要求找到入度为0的顶点，所以要采用邻接表来存储有向图，而要得到邻接表，则先要定义有向图的邻接矩阵结构，再把邻接矩阵转化成邻接表。

在具体实现拓扑排序的函数中，根据规则，当某个顶点的入度为0（没有前驱顶点）时，就将此顶点输出，同时将该顶点的所有后继顶点的入度减1，为了避免重复检测入度为0的顶点，设立一个栈St，以存放入度为0的顶点。

源程序代码：#include<stdio.h>#include<stdlib.h>#define MAXV 10 // 最大顶点个数typedef struct{int edges[MAXV][MAXV]; // 邻接矩阵的边数组int n; // 顶点数}MGraph;typedef struct ANode{int adjvex; // 该弧的终点位置struct ANode * nextarc; // 指向下一条弧的指针}ArcNode;typedef struct{int no; // 顶点信息int count; // 顶点入度ArcNode * firstarc; // 指向第一条弧}VNode, AdjList[MAXV];typedef struct{AdjList adjlist; // 邻接表int n; // 图的顶点数}ALGraph;void MatTolist(MGraph g, ALGraph * &G){int i, j, n=g.n;ArcNode * p;G = (ALGraph *)malloc(sizeof(ALGraph));for (i=0; i<n; i++)G->adjlist[i].firstarc = NULL;for (i=0; i<n; i++)for (j=n-1; j>=0; j--)if (g.edges[i][j]!=0){p=(ArcNode *)malloc(sizeof(ArcNode));p->adjvex = j;p->nextarc = G->adjlist[i].firstarc;G->adjlist[i].firstarc = p;}G->n=n;}void TopSort(ALGraph * G){int i,j,flag=0,a[MAXV];int St[MAXV], top = -1; // 栈St的指针为topArcNode * p;for (i=0; i<G->n; i++) // 入度置初值为0 G->adjlist[i].count = 0;for (i=0; i<G->n; i++) // 求所有顶点的入度{p=G->adjlist[i].firstarc;while (p!=NULL){G->adjlist[p->adjvex].count++;p=p->nextarc;}}for (i=0; i<G->n; i++)if (G->adjlist[i].count==0) // 入度为0的顶点进栈{top++; St[top] = i;}while (top>-1) // 栈不为空时循环{i = St[top]; top--; // 出栈a[flag++]=i; // 输出顶点p=G->adjlist[i].firstarc; // 找第一个相邻顶点while (p!=NULL){j = p->adjvex;G->adjlist[j].count--;if (G->adjlist[j].count==0){top++; St[top] = j; // 入度为0的相邻顶点进栈}p = p->nextarc; // 找下一个相邻顶点}}if (flag<G->n)printf("该图存在回路，不存在拓扑序列!\n");else{printf("该图的一个拓扑序列为:");for(i=0; i<flag; i++)printf("%d", a[i]);printf("\n");}}void main(){int i, j;MGraph g;ALGraph * G;G=(ALGraph *)malloc(sizeof(ALGraph));printf("请输入图的顶点数:");scanf("%d", &g.n);printf("请输入图的邻接矩阵:\n");for(i=0; i<g.n; i++)for(j=0; j<g.n; j++)scanf("%d", &g.edges[i][j]);MatTolist(g, G);TopSort(G);} 测试用例：对图7-1所示的有向图进行拓扑排序的测试结果如下：图7-1图7-2程序执行界面，提示输入图的顶点数，输入之后又提示输入其邻接矩阵，对图7-1所示的有向图的邻接矩阵输入如图7-2所示。

数据结构课设——有向图的深度、⼴度优先遍历及拓扑排序任务：给定⼀个有向图，实现图的深度优先, ⼴度优先遍历算法，拓扑有序序列，并输出相关结果。

功能要求：输⼊图的基本信息，并建⽴图存储结构（有相应提⽰），输出遍历序列，然后进⾏拓扑排序，并测试该图是否为有向⽆环图，并输出拓扑序列。

按照惯例，先上代码，注释超详细：#include<stdio.h>#include<stdlib.h>#include<malloc.h>#pragma warning(disable:4996)#define Max 20//定义数组元素最⼤个数（顶点最⼤个数）typedef struct node//边表结点{int adjvex;//该边所指向结点对应的下标struct node* next;//该边所指向下⼀个结点的指针}eNode;typedef struct headnode//顶点表结点{int in;//顶点⼊度char vertex;//顶点数据eNode* firstedge;//指向第⼀条边的指针，边表头指针}hNode;typedef struct//邻接表（图）{hNode adjlist[Max];//以数组的形式存储int n, e;//顶点数，边数}linkG;//以邻接表的存储结构创建图linkG* creat(linkG* g){int i, k;eNode* s;//边表结点int n1, e1;char ch;g = (linkG*)malloc(sizeof(linkG));//申请结点空间printf("请输⼊顶点数和边数：");scanf("%d%d", &n1, &e1);g->n = n1;g->e = e1;printf("顶点数：%d 边数：%d\n", g->n, g->e);printf("请输⼊顶点信息（字母）：");getchar();//因为接下来要输⼊字符串，所以getchar⽤于承接上⼀条命令的结束符for (i = 0; i < n1; i++){scanf("%c", &ch);g->adjlist[i].vertex = ch;//获得该顶点数据g->adjlist[i].firstedge = NULL;//第⼀条边设为空}printf("\n打印顶点下标及顶点数据：\n");for (i = 0; i < g->n; i++)//循环打印顶点下标及顶点数据{printf("顶点下标：%d 顶点数据：%c\n", i, g->adjlist[i].vertex);}getchar();int i1, j1;//相连接的两个顶点序号for (k = 0; k < e1; k++)//建⽴边表{printf("请输⼊对<i,j>（空格分隔）：");scanf("%d%d", &i1, &j1);s = (eNode*)malloc(sizeof(eNode));//申请边结点空间s->adjvex = j1;//边所指向结点的位置，下标为j1s->next = g->adjlist[i1].firstedge;//将当前s的指针指向当前顶点上指向的结点g->adjlist[i1].firstedge = s;//将当前顶点的指针指向s}return g;//返回指针g}int visited[Max];//标记是否访问void DFS(linkG* g, int i)//深度优先遍历{eNode* p;printf("%c ", g->adjlist[i].vertex);visited[i] = 1;//将已访问过的顶点visited值改为1p = g->adjlist[i].firstedge;//p指向顶点i的第⼀条边while (p)//p不为NULL时（边存在）{if (visited[p->adjvex] != 1)//如果没有被访问DFS(g, p->adjvex);//递归}p = p->next;//p指向下⼀个结点}}void DFSTravel(linkG* g)//遍历⾮连通图{int i;printf("深度优先遍历;\n");//printf("%d\n",g->n);for (i = 0; i < g->n; i++)//初始化为0{visited[i] = 0;}for (i = 0; i < g->n; i++)//对每个顶点做循环{if (!visited[i])//如果没有被访问{DFS(g, i);//调⽤DFS函数}}}void BFS(linkG* g, int i)//⼴度优先遍历{int j;eNode* p;int q[Max], front = 0, rear = 0;//建⽴顺序队列⽤来存储，并初始化printf("%c ", g->adjlist[i].vertex);visited[i] = 1;//将已经访问过的改成1rear = (rear + 1) % Max;//普通顺序队列的话，这⾥是rear++q[rear] = i;//当前顶点（下标）队尾进队while (front != rear)//队列⾮空{front = (front + 1) % Max;//循环队列，顶点出队j = q[front];p = g->adjlist[j].firstedge;//p指向出队顶点j的第⼀条边while (p != NULL){if (visited[p->adjvex] == 0)//如果未被访问{printf("%c ", g->adjlist[p->adjvex].vertex);visited[p->adjvex] = 1;//将该顶点标记数组值改为1rear = (rear + 1) % Max;//循环队列q[rear] = p->adjvex;//该顶点进队}p = p->next;//指向下⼀个结点}}}void BFSTravel(linkG* g)//遍历⾮连通图{int i;printf("⼴度优先遍历：\n");for (i = 0; i < g->n; i++)//初始化为0{visited[i] = 0;}for (i = 0; i < g->n; i++)//对每个顶点做循环{if (!visited[i])//如果没有被访问过{BFS(g, i);//调⽤BFS函数}}}//因为拓扑排序要求⼊度为0，所以需要先求出每个顶点的⼊度void inDegree(linkG* g)//求图顶点⼊度{eNode* p;int i;for (i = 0; i < g->n; i++)//循环将顶点⼊度初始化为0{g->adjlist[i].in = 0;}for (i = 0; i < g->n; i++)//循环每个顶点{p = g->adjlist[i].firstedge;//获取第i个链表第1个边结点指针while (p != NULL)///当p不为空（边存在）{g->adjlist[p->adjvex].in++;//该边终点结点⼊度+1p = p->next;//p指向下⼀个边结点}printf("顶点%c的⼊度为：%d\n", g->adjlist[i].vertex, g->adjlist[i].in);}void topo_sort(linkG *g)//拓扑排序{eNode* p;int i, k, gettop;int top = 0;//⽤于栈指针的下标索引int count = 0;//⽤于统计输出顶点的个数int* stack=(int *)malloc(g->n*sizeof(int));//⽤于存储⼊度为0的顶点for (i=0;i<g->n;i++)//第⼀次搜索⼊度为0的顶点{if (g->adjlist[i].in==0){stack[++top] = i;//将⼊度为0的顶点进栈}}while (top!=0)//当栈不为空时{gettop = stack[top--];//出栈,并保存栈顶元素（下标）printf("%c ",g->adjlist[gettop].vertex);count++;//统计顶点//接下来是将邻接点的⼊度减⼀，并判断该点⼊度是否为0p = g->adjlist[gettop].firstedge;//p指向该顶点的第⼀条边的指针while (p)//当p不为空时{k = p->adjvex;//相连接的顶点（下标）g->adjlist[k].in--;//该顶点⼊度减⼀if (g->adjlist[k].in==0){stack[++top] = k;//如果⼊度为0，则进栈}p = p->next;//指向下⼀条边}}if (count<g->n)//如果输出的顶点数少于总顶点数，则表⽰有环{printf("\n有回路！\n");}free(stack);//释放空间}void menu()//菜单{system("cls");//清屏函数printf("************************************************\n");printf("* 1.建⽴图 *\n");printf("* 2.深度优先遍历 *\n");printf("* 3.⼴度优先遍历 *\n");printf("* 4.求出顶点⼊度 *\n");printf("* 5.拓扑排序 *\n");printf("* 6.退出 *\n");printf("************************************************\n");}int main(){linkG* g = NULL;int c;while (1){menu();printf("请选择：");scanf("%d", &c);switch (c){case1:g = creat(g); system("pause");break;case2:DFSTravel(g); system("pause");break;case3:BFSTravel(g); system("pause");break;case4:inDegree(g); system("pause");break;case5:topo_sort(g); system("pause");break;case6:exit(0);break;}}return0;}实验⽤图:运⾏结果：关于深度优先遍历 a.从图中某个顶点v 出发，访问v 。