【数据结构算法】实验9 图的拓扑排序问题(附源代码)

浙江大学城市学院实验报告

课程名称 数据结构与算法 实验项目名称 实验九 图的拓扑排序问题 实验成绩 指导老师（签名 ） 日期

一. 实验目的和要求

1. 掌握拓扑排序概念。

2. 理解并能实现拓扑排序算法（采用邻接表表示图）。

二. 实验内容

1、 编写用邻接表表示有向无权图时图的基本操作的实现函数，具体包括： ① 初始化用邻接表表示的有向无权图 void InitAdjoin(adjlist G);

② 建立用邻接表表示的有向无权图 void CreateAdjoin (adjlist G, int n) （即通过输入图的每条边建立图的邻接表）;

③ 输出用邻接表表示的有向无权图void PrintAdjoin (adjlist G, int n) （即输出图的每条边）。

把邻接表的结构定义及这些基本操作实现函数存放在头文件Graph3.h中。 2、 编写拓扑排序算法 void Toposort( adjlist G, int n) （输入为图的邻接表，输出为相应的拓扑序列）。

3、 编写测试程序（即主函数），首先建立并输出有向无权图，然后进行拓扑排序。 要求： 把拓扑排序函数Toposort以及主函数存放在主文件test9_3.cpp中。 测试数据如下：

4、 填写实验报告，实验报告文件取名为report9.doc。

5、 上传实验报告文件report9.doc与源程序文件test9_3.cpp及Graph3.h到Ftp服务器上自己的文件夹下。

三. 函数的功能说明及算法思路

包括每个函数的功能说明，及一些重要函数的算法实现思路

【结构说明】

const int MaxVertexNum =10; //图的最大顶点数 const int MaxEdgeNum =100; //边数的最大值 struct EdgeNode{ //链表边结点，表示弧

int adjvex; //存放与头结点顶点有关的另一个顶点在邻接表(数组)中的下标。

EdgeNode *next; //指向链表下一个结点 };

typedef struct VNode{ //邻接表，表示顶点 int data; // 顶点数据，顶点名称

EdgeNode *firstarc; // 指向边结点链表第一个结点 } adjlist[MaxVertexNum];

【函数说明】

① void InitAdjoin(adjlist G)

功能：初始化用邻接表表示的有向无权图

思路：将邻接表的所有顶点置为-1，边结点链表指针置为NULL

② void CreateAdjoin (adjlist &G, int n) 功能：建立用邻接表表示的有向无权图（即通过输入图的每条边建立图的邻接表）思路：按照输入的顶点信息，新建边结点链入邻接表中对应位置

③ void PrintAdjoin (adjlist G, int n)

功能：输出用邻接表表示的有向无权图（即输出图的每条边） 思路：按照一定的格式输出邻接表

④ void Toposort( adjlist G, int n)

功能：输入图的邻接表，输出相应的拓扑序列 思路：初始化数组 d[ ]，利用数组的空间建立入度为零的顶点栈并设置栈顶指针。当入度为零的顶点栈不空时，重复执行以下步骤：从顶点栈中退出一个顶点, 并输出之；将该顶点的出边邻接点入度减一，如果出边邻接点入度减至0， 则该顶点入栈，更新栈顶指针。完成整个循环后，判断输出的顶点个数是否少于邻接表的顶点个数，如果少于则说明存在回路，打印输出信息。

四. 实验结果与分析

包括运行结果截图等

【测试数据】

顶点数：6

输入弧的信息：

正确的邻接表应为：

（程序给出的结果与拓扑排序结果一并显示在本部分末尾）

下面给出了拓扑排序函数实现过程中d[]数组的一系列状态。状态记录点共有三种：循环开始前、top指针改变时、一次循环结束后：

【1】循环开始前 -1 0 top 【2】top 改变 -1 0 2 2 0 top 【3】一次循环结束 -1 0 1 1 0 top 【4】一次循环结束 -1 top 【5】top 改变 -1 0 2 top 2 1 3 0 1 1 0 2 3 3 2 2 1 3

【6】一次循环结束 -1 0 -1 top 1 0 2

【7】top 改变 -1 0 -1 -1 top 【8】一次循环结束 -1 -14

0

-1

-1

0

0

-1

top

拓扑排序输出的顶点顺序应为：1 4 0 2 3 5

五. 心得体会

记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。

【附录----源程序】 [Test9_3.cpp] #include<stdio.h> #include<stdlib.h> #include<iostream.h> #include<string.h>

#include"Graph3.h"

void main(){ adjlist G; int n; void Toposort( adjlist G, int n); InitAdjoin(G); printf("输入要构造的图顶点数\n"); scanf("%d",&n); CreateAdjoin(G,n); PrintAdjoin(G,n); Toposort(G,n); }

//输入为图的邻接表，输出为相应的拓扑序列 void Toposort( adjlist G, int n) { int *d; int i,count,top,t; EdgeNode *p; d = new int[n]; for(i=0;i<n;i++) d[i] = 0; top = -1; //初始化数组d[] for(i=0;i<n;i++){ p=G[i].firstarc; while(p){ d[p->adjvex]++; p=p->next; } } //建立入度为零的顶点栈 for(i=0;i<n;i++){

if(d[i] == 0){ d[i] = top; top = i; } } printf("\n----------------------------------------------------\n"); printf("Toposort Result: "); count = 0; while(top != -1){ //top指示的顶点即为本次删除的顶点 printf("%d ",top); count++; p = G[top].firstarc; t = top; while(p){ //删除以该顶点出发的边（实际只减少到达顶点入度） //同时判断是否为0，是则入栈 if (--d[p->adjvex] == 0){ d[p->adjvex] = d[top]; top = p->adjvex; } p = p->next; } if (t …… 此处隐藏：2301字，全部文档内容请下载后查看。喜欢就下载吧 ……