内容发布更新时间 : 2025/1/22 8:27:54星期一 下面是文章的全部内容请认真阅读。

数据结构实验报告 实验六 图的应用及其实现 姓名: 李 大 宝 学院：计算机学院 班级：软件114班 学号：201100834416 软件114班李大宝 201100834416

实验六 图的应用及其实现

（相关知识点：拓扑排序、关键路径、最小生成树和最短路径）

一、实验目的

1．进一步功固图常用的存储结构。

2．熟练掌握在图的邻接表实现图的基本操作。

3．理解掌握AOV网、AOE网在邻接表上的实现以及解决简单的应用问题。

二、实验内容

一>.基础题目：(本类题目属于验证性的，要求学生独立完成)

[题目一]：从键盘上输入AOV网的顶点和有向边的信息,建立其邻接表存储结构,然后对该图拓扑排序,并输出拓扑序列. 试设计程序实现上述AOV网的类型定义和基本操作,完成上述功能。 测试数据：教材图7.28

1、图的定义（用邻接表存储图）

#define MAX_VERTEX_NUM 20 //最大顶点数 bool visited[MAX_VERTEX_NUM]; //标记数组 intindegree[MAX_VERTEX_NUM]={0}; typedefint* INT; stack m;

typedefstructArcNode

{intadjvex; //该弧所指向的顶点位置 structArcNode *nextarc; //指向下一个弧的指针 }ArcNode;

typedefstructvNode

{char data; //顶点信息

ArcNode *firstarc; //指向第一条依附该顶点的弧的指针 }vNode,AdjList[MAX_VERTEX_NUM]; typedefstruct

{AdjList vertices;

intvexnum,arcnum; //图的顶点数和弧数 }ALGraph;

2、相关函数声明：

1、/*在图中查找顶点a的位置*/ intlocatevex(ALGraphG,char a)

2、/* 输入图的顶点和边的信息,建立图*/ voidcreatgraph(ALGraph&G) 3、/*查找每个顶点的入度*/ voidfinddegree(ALGraph G) 4、/*拓扑排序*/

inttopologicalsort(ALGraph G)

3、相关函数(主要函数)的具体说明： 1、/* 输入图的顶点和边的信息,建立图*/

1

软件114班李大宝 201100834416

voidcreatgraph(ALGraph&G)

{int i,v1,v2;char a,b;ArcNode* p=NULL;

cout<<\输入结点个数，边数\\n\ cout<<\输入顶点的数据：\\n\

for(i=0;i>G.vertices[i].data;G.vertices[i].firstarc=NULL;} cout<<\输入相关联的边：\\n\ for(i=0;i>a>>b;

v1=locatevex(G,a);v2=locatevex(G,b);//输入关联的边

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

p->adjvex=v2;

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

G.vertices[v1].firstarc=p;//插入节点时每次都是插入到头结点后面 } }

2、/*查找每个顶点的入度*/ voidfinddegree(ALGraph G)

{ for(inti=0;i

while(p)//通过while循环找到每个节点的入度 {indegree[p->adjvex]++;p=p->nextarc;} } }

3、/*拓扑排序*/

inttopologicalsort(ALGraph G) {inti,k,t;ArcNode* p;

finddegree(G);//对所有的顶点求入度 for(i=0;i

if(!indegree[i])m.push(i);//入度为0的全部进栈 int count=0; //对输出顶点计数 while (!m.empty()) {t=m.top();m.pop();

cout<nextarc) {

k=p->adjvex;indegree[k]-=1;//对i号顶点的每个邻接点入度减1

if(!indegree[k])m.push(k);//若入度为0则入栈 } }

if(count

4、函数的调用关系图

2

软件114班李大宝 201100834416

5、调试分析及实验总结： 程序运行如下图：

题目一主要是运用邻接表进行的图的操作然后求出每个顶点的入度，根据每个顶点的入度进行拓扑排序。拓扑排序是当一个顶点的入度为0 时将其入栈，然后每次从栈中获得一个栈顶元素将其输出最后将对该顶点的每个邻接点的入度减一。这道题目主要考察我们对图的掌握情况。通过这道题目我们又复习了有关栈的知识。 6、程序清单：

略。

[题目二]：从键盘上输入AOE网的顶点和有向边的信息,建立其邻接表存储结构,输出其关键路径和关键路径长度。 试设计程序实现上述AOE网类型定义和基本操作,完成上述功能。 测试数据：教材图7.29

1、图的定义（用邻接表存储图）

#define MAX_VERTEX_NUM 20 //最大顶点数 bool visited[MAX_VERTEX_NUM]; //标记数组 intindegree[MAX_VERTEX_NUM]={0}; //入度数组 intve[MAX_VERTEX_NUM]={0}; //最早发生时间 intvl[MAX_VERTEX_NUM]; //最迟发生时间

3

软件114班李大宝 201100834416

typedefint* INT; stack m;

typedefstructArcNode {intadjvex;

structArcNode *nextarc; int info; }ArcNode;

typedefstructvNode {char data;

ArcNode *firstarc;

}vNode,AdjList[MAX_VERTEX_NUM]; typedefstruct

{AdjList vertices; intvexnum,arcnum; }ALGraph;

2、相关函数声明：

1、/*在图中查找顶点a的位置*/ intlocatevex(ALGraphG,char a)

2、/* 输入图的顶点和边的信息,建立图*/ voidcreatgraph(ALGraph&G) 3、/*查找每个顶点的入度*/ voidfinddegree(ALGraph G) 4、/*拓扑排序*/

inttopologicalsort(ALGraph G) 5、/*求关键路径*/

voidcriticalpath(ALGraphG,stack T) 3、相关函数(主要函数)的具体说明：（与题目一相同的省略） /*求关键路径*/

voidcriticalpath(ALGraphG,stack T) {inti,dut,k,ee,el,j;char tag;ArcNode* p;

if(!topologicalsort(G,T))return; //存在环则退出该程序 cout<

for(i=0;i

while(!T.empty()) //按拓扑排序求各顶点的vl值 {j=T.top();T.pop();

for (p=G.vertices[j].firstarc;p;p=p->nextarc) {k=p->adjvex;dut=(p->info);

if(vl[k]-dut

cout<<\起点 终点 路径长度 最早发生时间 最迟发生时间 关键路径\

for (j=0;j

4