数据结构-实验3-图形结构及其应用

数据结构实验报告目的要求１．掌握图的存储思想及其存储实现..２．掌握图的深度、广度优先遍历算法思想及其程序实现..３．掌握图的常见应用算法的思想及其程序实现..实验内容１．键盘输入数据;建立一个有向图的邻接表..２．输出该邻接表..3．在有向图的邻接表的基础上计算各顶点的度;并输出..4．以有向图的邻接表为基础实现输出它的拓扑排序序列..5．采用邻接表存储实现无向图的深度优先递归遍历..6．采用邻接表存储实现无向图的广度优先遍历..7．在主函数中设计一个简单的菜单;分别调试上述算法..源程序：主程序的头文件：队列#include <stdio.h>#include <stdlib.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2typedef int QElemType;typedef struct QNode{ //队的操作QElemType data;struct QNode *next;}QNode;*QueuePtr;typedef struct {QueuePtr front;QueuePtr rear;}LinkQueue;void InitQueueLinkQueue &Q{ //初始化队列Q.front =Q.rear =QueuePtrmallocsizeofQNode;ifQ.front exitOVERFLOW; //存储分配失败Q.front ->next =NULL;}int EnQueueLinkQueue &Q;QElemType e //插入元素e为Q的新的队尾元素{QueuePtr p;p=QueuePtrmallocsizeofQNode;ifp exitOVERFLOW;p->data=e;p->next=NULL;Q.rear->next=p;Q.rear =p;return OK;}int DeQueueLinkQueue &Q;QElemType &e //删除Q的队头元素;用e返回其值{ ifQ.front ==Q.rear return ERROR;QueuePtr p;p=Q.front ->next;e=p->data;Q.front->next=p->next ;ifQ.rear==p Q.rear =Q.front ;freep;return OK;}主程序：#include <stdio.h>#include<stdlib.h>#include"duilie.h"#define TRUE 1#define FALSE 0#define Status int#define MAX_VERTEX_NUM 8 /*顶点最大个数*/#define VertexType char /*顶点元素类型*/enum BOOlean {False;True};BOOlean visitedMAX_VERTEX_NUM; //全局变量——访问标志数组typedef struct ArcNode{int adjvex;struct ArcNode *nextarc;int weight; /*边的权*/}ArcNode; /*表结点*/typedef struct VNode{ int degree;indegree;/*顶点的度;入度*/V ertexType data;ArcNode *firstarc;}VNode/*头结点*/;AdjListMAX_VERTEX_NUM;typedef struct{ AdjList vertices;int vexnum;arcnum;/*顶点的实际数;边的实际数*/}ALGraph;//建立图的邻接表void creat_linkALGraph *G{ int i;j;ArcNode *s;printf"请依次输入顶点数、边数：";scanf"%d%d";&G->vexnum;&G->arcnum;for i=0;i<G->vexnum;i++{ G->verticesi.data='A'+i;G->verticesi.firstarc=NULL;}for i=0;i<G->vexnum;{ printf"请输入顶点的数组坐标若退出;请输入-1：";scanf"%d";&i;ifi==-1 break;printf"请输入顶点所指向下一个顶点的数组坐标：";scanf"%d";&j;s=ArcNode *mallocsizeofArcNode;s->adjvex=j;s->nextarc=G->verticesi.firstarc;G->verticesi.firstarc=s;}}// 输出邻接表void visitALGraph G{ int i;ArcNode *p;printf"%4s%6s%18s\n";"NO";"data";"adjvexs of arcs";for i=0;i<G.vexnum;i++{printf"%4d%5c ";i;G.verticesi.data;forp=G.verticesi.firstarc;p;p=p->nextarcprintf"%3d";p->adjvex;printf"\n";}}// 计算各顶点的度及入度void cacuALGraph *G{ArcNode *p;int i;for i=0;i<G->vexnum;i++{G->verticesi.degree=0;G->verticesi.indegree=0;}//度与初度初始化为零for i=0;i<G->vexnum;i++forp=G->verticesi.firstarc;p;p=p->nextarc{G->verticesi.degree++;G->verticesp->adjvex.degree++;G->verticesp->adjvex.indegree++;}}void print_degreeALGraph G{int i;printf"\n Nom data degree indegree\n";for i=0;i<G.vexnum;i++printf"\n%4d%5c%7d%8d";i;G.verticesi.data;G.verticesi.degree;G.verticesi.indegree;printf"\n";}// 拓扑排序Status TopologiSortALGraph G{int i;count;top=0;stack50;ArcNode *p;cacu&G;print_degreeG;printf"\nTopologiSort is \n";fori=0;i<G.vexnum;i++ifG.verticesi.indegree stacktop++=i;count=0;whiletop=0{i=stack--top;if count==0 printf"%c";G.verticesi.data;else printf"-->%c";G.verticesi.data;count++;forp=G.verticesi.firstarc;p;p=p->nextarcif --G.verticesp->adjvex.indegreestacktop++=p->adjvex;}if count<G.vexnumreturnFALSE; else returnTRUE;}//在图G中寻找第v个顶点的第一个邻接顶点int FirstAdjVexALGraph G;int v{ifG.verticesv.firstarc return 0;else returnG.verticesv.firstarc->adjvex;}//在图G中寻找第v个顶点的相对于u的下一个邻接顶点int NextAdjVexALGraph G;int v;int u{ArcNode *p;p=G.verticesv.firstarc;whilep->adjvex=u p=p->nextarc; //在顶点v的弧链中找到顶点u ifp->nextarc==NULL return 0; //若已是最后一个顶点;返回0else returnp->nextarc->adjvex; //返回下一个邻接顶点的序号}//采用邻接表存储实现无向图的深度优先递归遍历void DFSALGraph G;int i{ int w;visitedi=True; //访问第i个顶点printf"%d->";i;forw=FirstAdjVexG;i;w;w=NextAdjVexG;i;wifvisitedw DFSG;w; //对尚未访问的邻接顶点w调用DFS}void DFSTraverseALGraph G{ int i;printf"DFSTraverse:";fori=0;i<G.vexnum;i++ visitedi=False; //访问标志数组初始化fori=0;i<G.vexnum;i++ifvisitedi DFSG;i; //对尚未访问的顶点调用DFS}//按广度优先非递归的遍历图G;使用辅助队列Q和访问标志数组visited void BFSTraverseALGraph G{int i;u;w;LinkQueue Q;printf"BFSTreverse:";fori=0;i<G.vexnum;i++ visitedi=False; //访问标志数组初始化InitQueueQ; //初始化队列fori=0;i<G.vexnum;i++ifvisitedi{visitedi=True; //访问顶点iprintf"%d->";i;EnQueueQ;i; //将序号i入队列whileQ.front ==Q.rear //若队列不空;继续{DeQueueQ;u; //将队头元素出队列并置为uforw=FirstAdjVexG;u;w;w=NextAdjV exG;u;wifvisitedw //对u的尚未访问的邻接顶点w进行访问并入队列{ visitedw=True;printf"%d->";w;EnQueueQ;w;}}}}void main{ALGraph G;int select;printf" 图的有关操作实验\n ";do{printf"\n1 创建一个有向图的邻接表 2 输出该邻接表\n";printf"3.输出该有向图的度和入度 4.输出该有向图拓扑排序序列\n";printf"5.创建一个无向图的邻接表 6.深度优先递归遍历该无向图\n";printf"7.广度优先遍历该无向图0.退出\n";printf"请输入选择：";scanf"%d";&select;switchselect{case 1:printf"\n创建一个有向图的邻接表：\n";creat_link&G;break;case 2:printf"\n输出该邻接表：\n";visitG;break;case 3:printf"\n输出该有向图的度和入度：\n";cacu&G;print_degreeG;break;case 4:printf"\n输出该有向图拓扑排序序列：\n";ifTopologiSortGprintf"Toposort is not success";break;case 5:printf"\n创建一个无向图的邻接表: \n";creat_link&G;break;case 6:printf"\n深度优先递归遍历该无向图: \n";DFSTraverseG;break;case 7:printf"\n广度优先遍历该无向图：\n";BFSTraverseG;break;case 0:break;default:printf"输入选项错误重新输入\n";}}whileselect;}运行结果截图：1.主菜单界面：2.创建一个有向图的领接表3.输出该邻接表4. 在有向图的邻接表的基础上计算各顶点的度;并输出..5. 输出它的拓扑排序序列6. 输出所建无向图的邻接表7. 深度优先递归遍历该无向图8. 广度优先遍历该无向图说明：本实验用的有向图是课本182页图7.28;无向图为课本168页图a实验总结这次的图的操作实验;与树的操作类似;但又比树复杂;包含更多的存储结构和遍历方法的操作;而且图的遍历需要沿着弧进行;以便输出弧上的信息..本实验中图的遍历采用邻接表的存储结构;在输入图的信息时;首先要画出图的邻接表信息..图有两种遍历的形式;一种为深度优先搜索;另一种为广度优先搜索..由于能力有限;没能实现图的深度非递归优先搜索;而是实现了图的深度递归优先搜索..本实验基本完成了图的操作;也学到了很多关于图的知识和算法..。

数据结构.图及应用数据结构是计算机科学中非常重要的一个概念，它是一种以特定方式组织和存储数据的方法。

图是数据结构中的一种类型，它由节点（或顶点）和连接这些节点的边组成。

图结构是一种非常灵活和强大的数据结构，它在计算机科学中有着广泛的应用。

在本文中，我将介绍图的数据结构及其应用，并探讨图在实际中的应用场景和作用。

首先，让我们来了解一下图的基本概念和特点。

图由节点和边组成，节点可以是任何类型的数据，比如数字、字符、对象等。

边则是节点之间的连接关系，它可以是有向的或者无向的。

图结构可以分为有向图和无向图两种类型，有向图的边有方向，而无向图的边没有方向。

图结构还可以是带权图，这种图的边上带有权重，表示了节点之间的关联程度或者距离。

图的数据结构可以使用多种方式来实现，比如邻接矩阵、邻接表、关联矩阵等。

邻接矩阵是使用二维数组来表示图的边关系，它的优点是可以快速地判断任意两个节点之间是否有边，但缺点是对于稀疏图来说会浪费大量的空间。

邻接表则是使用链表或数组来表示节点之间的连接关系，它的优点是节省空间，但查找任意两个节点之间是否有边需要遍历链表或数组。

图的数据结构在计算机科学中有着广泛的应用。

其中最直观的一个应用就是在地图导航系统中。

地图可以被表示成一个图结构，节点代表地点，边代表道路或路径。

利用图的数据结构，我们可以很容易地找到两个地点之间的最短路径，或者进行路线规划。

比如我们要从一个地方到另一个地方，我们可以利用图的搜索算法（比如深度优先搜索或者广度优先搜索）来找到最短路径或者规划出一条合适的路线。

另一个图的应用是在社交网络分析中。

社交网络可以被看做是一个图结构，其中节点代表用户，边代表用户之间的关系（比如好友关系）。

利用图的数据结构，我们可以进行社交网络的分析，比如查找两个用户之间的关系链，或者进行用户群体的聚类分析。

图的算法在社交网络中有着很广泛的应用，比如社区发现算法、影响力传播模型等。

此外，图的数据结构还可以用于解决一些复杂的优化问题。

数据结构图的应用实验原理1. 引言数据结构是计算机科学中的核心概念之一，它是用来组织和存储数据的一种方式。

在软件开发过程中，合理的数据结构设计可以极大地提高程序的性能和可维护性。

数据结构图是一种图形化的表示方式，它可以帮助我们分析和理解各种数据结构的关系和特性。

2. 实验目的本实验旨在通过实际应用的方式，深入理解数据结构图的原理和应用。

具体目的包括： - 掌握数据结构图的基本定义和特性 - 理解数据结构图在实际问题中的应用 - 学会使用数据结构图对复杂问题进行分析和解决3. 实验步骤1.选择适当的数据结构图工具：在进行数据结构图实验之前，我们需要选择一种合适的工具来绘制和表示数据结构图。

常见的数据结构图工具包括UML工具、流程图工具等，根据实验要求选择最合适的工具进行操作。

2.定义数据结构图：根据实际问题需求，确定所需的数据结构和相关关系，包括数据结构的类型、属性和操作等。

使用选定的工具，绘制数据结构图并对其进行命名。

3.分析数据结构图：对于给定的数据结构图，我们需要仔细分析其特性和关系。

可以通过观察图中的节点和边的连接方式，了解数据结构之间的层次关系和组织方式。

4.进行实验操作：根据实验要求，对数据结构图进行相关操作和计算。

可以使用图算法来解决具体问题，或者通过图的遍历来分析图中的各个节点和边的特性。

5.结果分析和总结：根据实验操作的结果，对实验过程和结果进行分析和总结。

比较实际结果与预期结果的差异，找出原因并提出改进建议。

4. 实验示例为了更好地理解数据结构图的应用实验原理，以下是一个简单的示例：假设有一家公司，需要管理公司内部的职员信息。

公司中的职员分为不同的部门，每个部门有若干个职位，每个职位对应一个或多个职员。

我们可以使用数据结构图来表示公司职员信息的组织结构。

1.定义数据结构图：根据公司内部的组织结构，我们可以定义如下的数据结构图：–节点1：公司（Company）•属性：公司名称–节点2：部门（Department）•属性：部门名称–节点3：职位（Position）•属性：职位名称–节点4：职员（Employee）•属性：职员姓名2.建立节点之间的关系：根据公司职员信息的实际关系，我们可以建立如下的节点之间的关系：–公司节点与部门节点之间的关系是一对多的关系–部门节点与职位节点之间的关系是一对多的关系–职位节点与职员节点之间的关系是一对多的关系3.实验操作：根据定义的数据结构图，我们可以进行各种实验操作，如：–查找某个职员所在的部门和职位–统计某个部门的职员数量–查找某个职员的上级领导4.结果分析和总结：通过实验操作，我们可以得到实际的结果，并进行分析和总结。

数据结构图的实验报告数据结构图的实验报告引言：数据结构图是计算机科学中重要的概念之一。

它是一种用图形表示数据元素之间关系的数据结构，广泛应用于算法设计、程序开发和系统优化等领域。

本实验报告旨在介绍数据结构图的基本原理、实验过程和结果分析。

一、实验目的本次实验的主要目的是掌握数据结构图的基本概念和操作方法，以及通过实验验证其在解决实际问题中的有效性。

具体而言，我们将通过构建一个社交网络关系图，实现对用户关系的管理和分析。

二、实验方法1. 确定数据结构在本次实验中，我们选择了无向图作为数据结构图的基础。

无向图由顶点集和边集组成，每条边连接两个顶点，且没有方向性。

2. 数据输入为了模拟真实的社交网络，我们首先需要输入一组用户的基本信息，如姓名、年龄、性别等。

然后，根据用户之间的关系建立边，表示用户之间的交流和联系。

3. 数据操作基于构建好的数据结构图，我们可以进行多种操作，如添加用户、删除用户、查询用户关系等。

这些操作将通过图的遍历、搜索和排序等算法实现。

三、实验过程1. 数据输入我们首先创建一个空的无向图，并通过用户输入的方式逐步添加用户和用户关系。

例如，我们可以输入用户A和用户B的姓名、年龄和性别，并建立一条边连接这两个用户。

2. 数据操作在构建好数据结构图后，我们可以进行多种操作。

例如，我们可以通过深度优先搜索算法遍历整个图，查找与某个用户具有特定关系的用户。

我们也可以通过广度优先搜索算法计算某个用户的社交网络影响力，即与该用户直接或间接相连的其他用户数量。

3. 结果分析通过实验，我们可以观察到数据结构图在管理和分析用户关系方面的优势。

它能够快速地找到用户之间的关系，帮助我们了解用户的社交网络结构和影响力。

同时，数据结构图也为我们提供了一种可视化的方式来展示用户之间的关系，使得分析更加直观和易于理解。

四、实验结果通过实验，我们成功构建了一个社交网络关系图，并实现了多种数据操作。

我们可以根据用户的姓名、年龄和性别等信息进行查询，也可以根据用户之间的关系进行遍历和排序。

数据结构实验报告--图
数据结构实验报告--图
1、实验目的
本实验主要旨在通过实践操作，深入理解图这种数据结构的基本概念、性质和基本操作，掌握图的存储结构与常见算法。

2、实验环境
本次实验使用编程语言C++，在Windows平台下进行开发和运行。

3、实验内容
3.1 图的定义与基本概念
在本章中，我们将介绍图的基本概念，包括有向图与无向图、顶点与边、度与入度出度、连通性等。

3.2 图的存储结构
在本章中，我们将介绍图的几种存储结构，包括邻接矩阵、邻接表和十字链表，以及它们的优缺点和适用场景。

3.3 图的遍历
在本章中，我们将介绍图的两种常用的遍历算法，即深度优先搜索（DFS）和广度优先搜索（BFS），并分别给出它们的实现代码和应用场景。

3.4 最短路径
在本章中，我们将介绍图的最短路径问题，包括单源最短路径和全源最短路径。

我们将使用Dijkstra算法和Floyd-Warshall算法来解决这些问题，并给出它们的实现代码和应用场景。

3.5 最小树
在本章中，我们将介绍图的最小树问题，即找到一棵树使得树上的边的权值之和最小。

我们将使用Prim算法和Kruskal算法来解决这个问题，并给出它们的实现代码和应用场景。

4、实验步骤和结果
在本章中，我们将详细介绍实验的具体步骤，并给出实验结果的详细分析和说明。

5、实验总结
在本章中，我们将对整个实验进行总结，总结实验中遇到的问题、解决方案和经验教训。

6、附件
本实验报告所涉及的附件包括实验代码和运行结果的截图。

7、法律名词及注释
本文所涉及的法律名词和注释详见附件中的相关文件。

实验题目：图的应用一、实验目的和任务1 掌握图的邻接表和邻接矩阵存储；2 掌握图的拓扑排序算法；二、实验内容及原理1以下两项内容选做一项。

2 请按照书中介绍的拓扑排序算法，完成P303页第5题。

3 给定某一个图，完成其深度优先搜索遍历和广度优先搜索遍历，每种遍历都必须在邻接矩阵和邻接表中完成。

四、实验数据及程序代码#include <iostream.h>#include <stdlib.h>#include <strstrea.h>#include <string.h>#include <stdio.h>const int MaxVertexNum=10;typedef int WeightType;struct edgenode{int adjvex;WeightType weight;edgenode*next;};typedef edgenode *adjlist[MaxVertexNum];void InitAdjoin(adjlist GL)//初始化{for(int i=0;i<MaxVertexNum;i++)GL[i]=NULL;}void CreatAdjoin(adjlist GL,int n,char*s,int k1,int k2)//生成邻接表{istrstream sin(s);char c1,c2,c3;WeightType w;edgenode*p;sin>>c1;if(k2==0){do{sin>>c1>>i>>c2>>j>>c3;p=new edgenode;p->adjvex=j;p->weight=1;p->next=GL[i];GL[i]=p;if(k1==0){p=new edgenode;p->adjvex=i;p->weight=1;p->next=GL[j];GL[j]=p;}sin>>c1;}while(c1==',');}else{do{sin>>c1>>i>>c2>>j>>c3>>w;p=new edgenode;p->adjvex=j;p->weight=w;p->next=GL[i];GL[i]=p;if(k1==0){p=new edgenode;p->adjvex=i;p->weight=w;p->next=GL[j];GL[j]=p;}sin>>c1;}while(c1==',');}}void PrintAdjion(adjlist GL, int n,int k1, int k2) {edgenode*p;cout<<"V={";for(i=0; i<n-1; i++) cout<<i<<',';cout<<n-1<<'}'<<endl;cout<<"E={";for(i=0;i<n;i++){if(k2==0){p=GL[i];while(p){j=p->adjvex;if(k1==0){if(i<j) cout<<'('<<i<<','<<j<<')'<<',';}elsecout<<'<'<<i<<","<<j<<'>'<<',';p=p->next;}}else{p=GL[i];while(p){j=p->adjvex;if(k1==0){if(i<j) cout<<'('<<i<<','<<j<<')'<<p->weight<<',';}elsecout<<'<'<<i<<','<<j<<'>'<<p->weight<<',';p=p->next;}}}cout<<'}'<<endl;}void Toposort(adjlist GL , int n){int i,j,k,top,m=0;edgenode*p;int*d=new int[n];for(i=0;i<n;i++) d[i]=0;for(i=0;i<n;i++){p=GL[i];while(p!=NULL){j=p->adjvex;d[i]++;p=p->next;//cout<<j;}}top=-1;for(i=0;i<n;i++)if(d[i]==0){d[i]=top; top=i;}while(top!=-1){j=top;top=d[top];cout<<j<<' ';m++;p=GL[j];while(p!=NULL){k=p->adjvex;d[k]--;if(d[k]==0){d[k]=top;top=k;}p=p->next;}}cout<<endl;cout<<top<<endl;cout<<m<<endl;cout<<n<<endl;if(m<n) cout<<"The network has a cycle!"<<endl;delete []d;}void main(){int n,k1,k2;cout<<"输入待处理图的顶点数:";cin>>n;cout<<"输入图的有无向和有无权选择（0为无，非0为有）:";cin>>k1>>k2;adjlist gl;InitAdjoin(gl);cout<<"输入图的边集:";FILE *p;p=fopen("d:\\1.txt","r+");char *a=new char[100];while (!feof(p)){fscanf(p,"%s ",a);cout<<a;}cout<<endl;//cin>>a;CreatAdjoin(gl,n,a,k1,k2);Toposort(gl,n);}五、实验数据分析及处理六、实验结论与感悟（或讨论）图的邻接矩阵，邻接表和边集数组表示各有利弊，具体运用时，要根据图的稠密和稀疏程度以及算法的要求进行选择。

数据结构图实验报告数据结构图实验报告引言：数据结构是计算机科学中非常重要的一个概念，它用于存储和组织数据，使得数据的操作更加高效和方便。

图是一种常见的数据结构，它由节点和边组成，用于表示各种实际问题中的关系和连接。

本实验旨在通过实际操作，深入理解图的基本概念和常见操作。

实验目的：1. 理解图的基本概念和特性；2. 掌握图的存储结构和基本操作；3. 实现图的遍历算法；4. 分析图的应用场景。

实验过程：1. 图的存储结构：在本次实验中，我们选择邻接矩阵来存储图。

邻接矩阵是一个二维数组，其中行和列分别表示图中的节点，数组元素表示节点之间的边的关系。

具体而言，如果节点i和节点j之间存在边，则邻接矩阵中的第i行第j列元素为1；否则为0。

2. 图的基本操作：在实验中，我们实现了以下几个图的基本操作：- 添加节点：通过向邻接矩阵中添加一行一列，并设置对应的边的关系，来添加一个节点；- 添加边：通过修改邻接矩阵中对应元素的值，来添加一条边；- 删除节点：通过删除邻接矩阵中对应行和列，并更新其他节点的索引，来删除一个节点；- 删除边：通过修改邻接矩阵中对应元素的值，来删除一条边；- 查找节点：通过遍历邻接矩阵，找到对应节点的索引；- 查找边：通过遍历邻接矩阵，找到对应边的关系。

3. 图的遍历算法：在实验中，我们实现了深度优先搜索（DFS）和广度优先搜索（BFS）两种图的遍历算法。

DFS通过递归的方式，先访问当前节点，再依次访问相邻节点，直到所有节点都被访问。

BFS则通过队列的方式，先访问当前节点，再依次访问当前节点的相邻节点，直到所有节点都被访问。

实验结果：通过实验，我们成功实现了图的存储结构和基本操作，并且正确实现了DFS和BFS两种遍历算法。

我们对不同规模的图进行了测试，并分析了算法的时间复杂度。

实验结果表明，邻接矩阵的存储结构在添加和删除节点时的时间复杂度较高，而在查找节点和边时的时间复杂度较低。

DFS和BFS的时间复杂度都为O(V+E)，其中V表示节点数，E表示边数。

图形数据结构实验1. 实验目的通过本实验，使学生掌握图这种数据结构的基本概念和基本算法，提高编程能力，为后续课程学习和实际应用打下基础。

2. 实验环境•编程语言：Java•开发工具：Eclipse/IntelliJ IDEA•硬件环境：计算机3. 实验内容3.1 实验原理图是一种复杂的数据结构，用于表示元素之间的相互关系。

图由顶点（节点）集合和边集合组成。

图的表示方法有邻接矩阵和邻接表两种。

3.2 实验任务1.实现图的邻接矩阵表示法；2.实现图的邻接表表示法；3.实现图的深度优先搜索（DFS）算法；4.实现图的广度优先搜索（BFS）算法；5.实现图的最短路径算法（如Dijkstra算法）。

4. 实验步骤4.1 创建图类首先，创建一个图类，包含顶点（节点）和边的基本操作。

```javaclass Graph {private int numVertices; // 顶点数量private int[][] adjMatrix; // 邻接矩阵public Graph(int numVertices) {this.numVertices = numVertices;adjMatrix = new int[numVertices][numVertices]; // 省略其他方法...4.2 邻接矩阵表示法实现邻接矩阵的初始化、添加边、删除边等操作。

```java// 初始化邻接矩阵public void initAdjMatrix() {for (int i = 0; i < numVertices; i++) {for (int j = 0; j < numVertices; j++) {if (i == j) {adjMatrix[i][j] = 0;} else {adjMatrix[i][j] = INFINITY;public void addEdge(int v1, int v2) {adjMatrix[v1][v2] = 1;adjMatrix[v2][v1] = 1;public void removeEdge(int v1, int v2) {adjMatrix[v1][v2] = INFINITY;adjMatrix[v2][v1] = INFINITY;// 省略其他方法…4.3 邻接表表示法实现邻接表的初始化、添加边、删除边等操作。

（前面可加目录页）一. 实验目的1.理解图的概念并熟悉有关术语。

2.熟练掌握邻接矩阵表示法和邻接表表示法。

3.掌握连通图遍历的基本思想和算法。

4.掌握最小生成树的有关概念和算法实现。

5.掌握最短路径有关概念和算法。

6.掌握拓扑排序的概念及实现。

二. 实验内容1.对给定的图，用邻接矩阵实现该图的深度优先搜索遍历。

2.对给定的图，用邻接矩阵实现该图的广度优先搜索遍历。

3.对给定的图，用邻接表实现该图的深度优先搜索遍历。

4.对给定的图，用邻接表实现该图的广度优先搜索遍历。

三. 文献综述数据结构（C语言版）习题解答及实训指导------------李根强、谢月娥四. 实验思路和技术路线（数据结构及算法）（1，2）算法设计：首先定义图的类型为结构型，包含图中的顶点信息和邻接矩阵两项信息，然后将输入边的信息建立邻接矩阵，再将深度搜索优先遍历和广度优先搜索遍历写成子函数的形式，在主函数中调用他们；（3，4）算法设计：首先定义图的邻接表数据类型，建立该图的邻接表，然后再用子函数写出深度优先搜索遍历和广度优先搜索遍历的算法，在主函数中调用它；五. 实验结果分析及心得（1）对给定的图，用邻接矩阵实现该图的深度优先和广度优先搜索遍历：<1 给定的图如下：< 2 广度优先和深度优先遍历程序如下：#include<stdio.h>#define n 8 //图中顶点数#define e 15 //图中边数#define elemtype intint visited[n+1]; //访问标志数组，为false表示未访问，为true表示已访问struct graph //定义图的数据类型{elemtype v[n+1]; //存放顶点信息 v1,v2,...,vn,不使用v[0]存储空间int arcs[n+1][n+1]; //邻接矩阵}g;void creatadj() //建立邻接矩阵{int i,j,k;printf("请输入%d个顶点信息\n",n);for(k=1;k<=n;k++)scanf("%d",&g.v[k]); //输入顶点信息for(i=1;i<=n;i++)for(j=1;j<=n;j++)g.arcs[i][j]=0;for(k=1;k<=e;k++){printf("请输入第%d条边，共%d条边",k,e);scanf("%d%d",&i,&j); //输入一条边（i,j)g.arcs[i][j]=1;g.arcs[j][i]=1;}}void dfs(int i) //从顶点i出发进行深度优先搜索遍历 {int j;printf("%d",g.v[i]); //输出访问顶点visited[i]=1; //全局数组访问标记置1表示已访问for(j=1;j<=n;j++)if((g.arcs[i][j]==1)&&(!visited[j]))dfs(j);}void bfs(int i) //从顶点i出发进行广度优先搜索遍历{int q[n+1]; //q为队列int f,r,j; //f,r分别为队列头指针、尾指针f=r=0; //设置空队列printf("%d",g.v[i]); //输出访问顶点visited[i]=1; //全局数组标记置1表示已访问r++;q[r]=i; //入队列while(f<r){f++;i=q[f]; //出队列for(j=1;j<=n;j++)if((g.arcs[i][j]==1)&&(!visited[j])){printf("%d",g.v[j]);visited[j]=1;r++;q[r]=j; //入队列}}}main(){int i,j;int yn=1;creatadj(); //建立邻接矩阵for(i=1;i<=n;i++) //输出邻接矩阵{for(j=1;j<=n;j++)printf("%d",g.arcs[i][j]);printf("\n");}while(yn==1){for(i=1;i<=n;i++)visited[i]=0;printf("请输入深度优先搜索开始访问的顶点");scanf("%d",&i);printf("\n");printf("从%d出发的深度优先搜素遍历序列为\n",i);dfs(i);printf("\n继续进行深度优先搜索吗（1/2）？");scanf("%d",&yn);}yn=1;while(yn==1){for(i=1;i<=n;i++)visited[i]=0;printf("请输入广度优先搜索开始访问的顶点");scanf("%d",&i);printf("\n");printf("从%d出发的广度优先搜索遍历序列为\n",i);bfs(i);printf("\n继续进行广度优先搜索吗 (1/2) ？");scanf("%d",&yn);}}运行结果：#define e 15 //图中边数#define elemtype intint visited[n+1];istruct link{elemtype data;struct link *next;};struct graph{struct link a[n+1];}g;void creatlink(){int i,j,k;struct link *s;for(i=1;i<=n;i++){g.a[i].data=i;g.a[i].next=NULL;}for(k=1;k<=e;k++){printf("请输入一条边");scanf("%d%d",&i,&j);s=(struct link *)malloc(sizeof(struct link));s->data=j;s->next=g.a[i].next;g.a[i].next=s;s=(struct link *)malloc(sizeof(struct link));s->data=i;s->next=g.a[j].next;g.a[j].next=s;}}void dfs1(int i){struct link *p;printf("%d",g.a[i].data);visited[i]=1;p=g.a[i].next;while(p!=NULL){if(!visited[p->data])dfs1(p->data);p=p->next;}}void bfs1(int i){int q[n+1];int f,r;struct link *p;f=r=0;printf("%d",g.a[i].data);visited[i]=1;r++;q[r]=i;while(f<r){f++;i=q[f];p=g.a[i].next;while(p!=NULL){if(!visited[p->data]){printf("%d",g.a[p->data].data);visited[p->data]=1;r++;q[r]=p->data;}p=p->next;}}}main(){struct link *p;int yn=1,i;creatlink();while(yn==1){for(i=1;i<=n;i++){p=g.a[i].next;printf("%d->",g.a[i].data);while(p->next!=NULL){printf("%d->",p->data);p=p->next;}printf("%d\n",p->data);}while(yn==1){for(i=1;i<=n;i++)visited[i]=0;printf("请输入深度优先搜索开始访问的顶点");scanf("%d",&i);printf("\n");printf("从%d出发的深度优先搜索遍历序列为\n",i);dfs1(i);printf("\n继续进行深度优先搜索吗（1/2）？");scanf("%d",&yn);}yn=1;while(yn==1){for(i=1;i<=n;i++)。

.数据结构实验报告图一、实验目的1、熟悉图的结构和相关算法。

二、实验内容及要求1、编写创建图的算法。

2、编写图的广度优先遍历、深度优先遍历、及求两点的简单路径和最短路径的算法。

三、算法描述1、图的邻接表存储表示：对图的每个顶点建立一个单链表，第i个单链表表示所有依附于第i个点的边（对于有向图表示以该顶点为尾的弧）；链表的每个节点存储两个信息，该弧指向的顶点在图中的位置（adjvex）和指向下一条弧的指针（nextarc）。

每个连表的头结点存储顶点的数据：顶点信息（data）和指向依附于它的弧的链表域。

存储表示如下：typedef struct ArcNode {int adjvex; // 该弧所指向的顶点的位置struct ArcNode *nextarc;// 指向下一条弧的指针// InfoType *info; // 该弧相关信息的指针} ArcNode;typedef struct VNode {char data; // 顶点信息int data2;int sngle;ArcNode *firstarc;// 指向第一条依附该顶点的弧} VNode, AdjList[MAX_NUM];typedef struct {AdjList vertices;int vexnum, arcnum;int kind; // 图的种类标志} ALGraph;2、深度优先搜索：假设初始态是图中所有定点未被访问，从图中的某个顶点v开始，访问此顶点，然后依次从v的未访问的邻接点出发深度优先遍历，直至途中所有和v有相同路径的点都被访问到；若图中仍有点未被访问，则从图中另选一个未被访问的点作为起点重复上述过程，直到图中所有点都被访问到。

为了便于区分途中定点是否被访问过，需要附设一个访问标致数组visited [0..n-1]，将其初值均设为false，一旦某个顶点被访问，将对应的访问标志赋值为true。

2、广度优先搜索：假设初始态是图中所有顶点未被访问，从图中的某个顶点v开始依次访问v的各个未被访问的邻接点，然后分别从这些邻接点出发以此访问他们的邻接点，并使“先被访问的邻接顶点”先于“后被访问的邻接顶点”被访问，直至图中所有已被访问过的顶点的邻接顶点都被访问。

数据结构实验三图的应用（代码&测试界面）//Traffic_Inquiry.h#include <stdio.h>#include <stdlib.h>#define FINITY 999 //用999代表无穷大#define M 20 //城市最大个数typedef struct { //邻接矩阵类型定义char name[8];}CityNode; //城市信息结点的结构体(顶点值类型)typedef int distype; //权值类型-距离typedef int costype; //权值类型-费用typedef struct {CityNode citys[M]; //顶点信息域distype dis[M][M]; //领接矩阵-距离costype cos[M][M]; //邻接矩阵-费用int n, e; //图中顶点总数与边数}Mgraph;//建立图的邻接矩阵存储结构void CreateGraph(Mgraph *g){int i, j, k;double d, c;printf("请输入城市数与路径数：");scanf("%d %d",&g->n, &g->e);for(i=0; i<g->n; i++) { //读入图的顶点数printf("请输入第%d个城市名称：",i);scanf("%s",g->citys[i].name);}for(i=0; i<g->n; i++) { //初始化邻接矩阵for(j=0; j<g->n; j++) {if(i==j) {g->dis[i][j]=0;g->cos[i][j]=0;}else {g->dis[i][j]=FINITY;g->cos[i][j]=FINITY;}}}printf("\n城市名称录入完毕，录入结果:\n\t");for(i=0; i<g->n; i++) {printf("%d->%s\t",i,g->citys[i].name);}printf("\n录入路径的权值信息，示例：0 1 34 40");printf("代表%s到%s的距离为34千米，费用为40元\n",g->citys[0].name,g->citys[1].name);for(k=0; k<g->e; k++) { //读入网络中的边scanf("%d %d %lf %lf",&i, &j, &d, &c);g->dis[i][j]=g->dis[j][i]=d;g->cos[i][j]=g->cos[j][i]=c;}}//Dijkstra算法求解单源最短路径typedef enum{FALSE,TRUE} boolean; //FALSE为0，TRUE为1void dijkstra(Mgraph g, int v0,const int q) //函数参数：图的领接矩阵g；源点v0；{int d[M];//权值（距离或费用）向量类型int p[M];//路径类型boolean final[M]; //表示当前元素是否已经求出最短路径int i,k,v,min;//第一步，初始化集合s与距离向量dfor (v=0; v<g.n; v++){final[v]=FALSE;if(q) d[v]=g.dis[v0][v];else d[v]=g.cos[v0][v];if (d[v]<FINITY && d[v]!=0)p[v]=v0; else p[v]=-1; //v无前驱}final[v0]=TRUE; d[v0]=0; //初始时s中只有v0一个结点//第二步，依次找出n-1个结点加入s中for(i=1; i<g.n; i++){min=FINITY;for(k=0;k<g.n;++k) //找最小边入结点if(!final[k]&&d[k]<min) //！final[k]表示k还在V-S中{v=k;min=d[k];}if(min<FINITY){if(q) printf("[ %s ]到[ %s ]的最短距离为:%d千米\n",g.citys[v0].name,g.citys[v].name,min);else printf("[ %s ]到[ %s ]的最小费用为:%d元\n",g.citys[v0].name,g.citys[v].name,min);}else if(min==FINITY) return;final[v]=TRUE; //v加入S//第三步，修改V-S中各节点的距离for(k=0;k<g.n;++k)if(!final[k]&&(min+g.dis[v][k]<d[k])){d[k]=min+g.dis[v][k];p[k]=v;}}}void floyd(Mgraph g,int q) //Floyd方法求所有顶点对间的最短路径(q用于判断参与算法的是距离还是费用){int e[M][M]; //权值（距离或费用）向量类型int p[M][M]; //路径类型int i, j, k;if(q) memcpy(e,g.dis,M*M*sizeof(int));else memcpy(e,g.cos,M*M*sizeof(int));for(i=0;i<g.n;i++) //初始化for(j=0;j<g.n;j++){if(i!=j && e[i][j]<FINITY) p[i][j]=i;else p[i][j]=-1;}for(k=0;k<g.n;k++) //递推求解每一对顶点间的最短距离{for(i=0;i<g.n;i++)for(j=0;j<g.n;j++){if(e[i][j]>(e[i][k]+e[k][j])){e[i][j]=e[i][k]+e[k][j];p[i][j]=k;}}}printf("┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄\n");for(i=0;i<g.n;i++){for(j=0;j<g.n;j++){if(i!=j&&e[i][j]!=0&&e[i][j]<FINITY)if(q) printf("[ %s ]到[ %s ]的最短距离为:%dkm。

数据结构实验三图的应用（代码&测试界面）//Traffic_Inquiry.h#include <stdio.h>#include <stdlib.h>#define FINITY 999 //用999代表无穷大#define M 20 //城市最大个数typedef struct { //邻接矩阵类型定义char name[8];}CityNode; //城市信息结点的结构体(顶点值类型)typedef int distype; //权值类型-距离typedef int costype; //权值类型-费用typedef struct {CityNode citys[M]; //顶点信息域distype dis[M][M]; //领接矩阵-距离costype cos[M][M]; //邻接矩阵-费用int n, e; //图中顶点总数与边数}Mgraph;//建立图的邻接矩阵存储结构void CreateGraph(Mgraph *g){int i, j, k;double d, c;printf("请输入城市数与路径数：");scanf("%d %d",&g->n, &g->e);for(i=0; i<g->n; i++) { //读入图的顶点数printf("请输入第%d个城市名称：",i);scanf("%s",g->citys[i].name);}for(i=0; i<g->n; i++) { //初始化邻接矩阵for(j=0; j<g->n; j++) {if(i==j) {g->dis[i][j]=0;g->cos[i][j]=0;}else {g->dis[i][j]=FINITY;g->cos[i][j]=FINITY;}}}printf("\n城市名称录入完毕，录入结果:\n\t");for(i=0; i<g->n; i++) {printf("%d->%s\t",i,g->citys[i].name);}printf("\n录入路径的权值信息，示例：0 1 34 40");printf("代表%s到%s的距离为34千米，费用为40元\n",g->citys[0].name,g->citys[1].name);for(k=0; k<g->e; k++) { //读入网络中的边scanf("%d %d %lf %lf",&i, &j, &d, &c);g->dis[i][j]=g->dis[j][i]=d;g->cos[i][j]=g->cos[j][i]=c;}}//Dijkstra算法求解单源最短路径typedef enum{FALSE,TRUE} boolean; //FALSE为0，TRUE为1void dijkstra(Mgraph g, int v0,const int q) //函数参数：图的领接矩阵g；源点v0；{int d[M];//权值（距离或费用）向量类型int p[M];//路径类型boolean final[M]; //表示当前元素是否已经求出最短路径int i,k,v,min;//第一步，初始化集合s与距离向量dfor (v=0; v<g.n; v++){final[v]=FALSE;if(q) d[v]=g.dis[v0][v];else d[v]=g.cos[v0][v];if (d[v]<FINITY && d[v]!=0)p[v]=v0; else p[v]=-1; //v无前驱}final[v0]=TRUE; d[v0]=0; //初始时s中只有v0一个结点//第二步，依次找出n-1个结点加入s中for(i=1; i<g.n; i++){min=FINITY;for(k=0;k<g.n;++k) //找最小边入结点if(!final[k]&&d[k]<min) //！final[k]表示k还在V-S中{v=k;min=d[k];}if(min<FINITY){if(q) printf("[ %s ]到[ %s ]的最短距离为:%d千米\n",g.citys[v0].name,g.citys[v].name,min);else printf("[ %s ]到[ %s ]的最小费用为:%d元\n",g.citys[v0].name,g.citys[v].name,min);}else if(min==FINITY) return;final[v]=TRUE; //v加入S//第三步，修改V-S中各节点的距离for(k=0;k<g.n;++k)if(!final[k]&&(min+g.dis[v][k]<d[k])){d[k]=min+g.dis[v][k];p[k]=v;}}}void floyd(Mgraph g,int q) //Floyd方法求所有顶点对间的最短路径(q用于判断参与算法的是距离还是费用){int e[M][M]; //权值（距离或费用）向量类型int p[M][M]; //路径类型int i, j, k;if(q) memcpy(e,g.dis,M*M*sizeof(int));else memcpy(e,g.cos,M*M*sizeof(int));for(i=0;i<g.n;i++) //初始化for(j=0;j<g.n;j++){if(i!=j && e[i][j]<FINITY) p[i][j]=i;else p[i][j]=-1;}for(k=0;k<g.n;k++) //递推求解每一对顶点间的最短距离{for(i=0;i<g.n;i++)for(j=0;j<g.n;j++){if(e[i][j]>(e[i][k]+e[k][j])){e[i][j]=e[i][k]+e[k][j];p[i][j]=k;}}}printf("┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄\n");for(i=0;i<g.n;i++){for(j=0;j<g.n;j++){if(i!=j&&e[i][j]!=0&&e[i][j]<FINITY)if(q) printf("[ %s ]到[ %s ]的最短距离为:%dkm。

淮海工学院计算机工程学院实验报告书课程名：《数据结构》题目：图形数据结构实验班级：学号：姓名：实验3图形数据结构实验实验目的和要求1．熟悉图的两种常用的存储结构，邻接矩阵和邻接表。

2．在这两种存储结构上的两种遍历图的方法，即深度优先遍历和广度优先遍历。

3．熟练掌握拓扑排序算法；理解求有向无环图的关键路径算法。

4．进一步掌握递归算法的设计方法。

实验环境Turbo C 或VC++实验学时4学时，必做实验实验内容和步骤一、要求画图并对所画的图进行DFS和BFS遍历。

如：实验步骤实验步骤： 1.输入图的顶点数目和边数.2.建立图的邻接表.3.按深度优先和广度优先遍历图.4.给出遍历序列.源程序#define N 10#define INFINITY 32768#define True 1#define False 0#define Error -1#define Ok 1#include "stdlib.h"#include "stdio.h"typedef enum{DG,DN,UDG,UDN}GraphKind;typedef char VertexData;typedef struct ArcNode2{int adjvex;struct ArcNode2 *nextarc;} ArcNode2;typedef struct VertexNode{VertexData data;ArcNode2 *firstarc;}VertexNode;typedef struct{VertexNode vertex[N];int vexnum2,arcnum2;GraphKind kind2;}AdjList;/*.............................*/typedef struct Node{int data;struct Node *next;}LinkQueueNode;typedef struct{LinkQueueNode *front;LinkQueueNode *rear;}LinkQueue;int InitQueue(LinkQueue *Q){Q->front=(LinkQueueNode*)malloc(sizeof(LinkQueueNode)); if(Q->front!=NULL){Q->rear=Q->front;Q->front->next=NULL;return(True);}elsereturn(False);}int EnterQueue(LinkQueue *Q,int x){LinkQueueNode *NewNode;NewNode=(LinkQueueNode*)malloc(sizeof(LinkQueueNode)); if(NewNode!=NULL){NewNode->data=x;NewNode->next=NULL;Q->rear->next=NewNode;Q->rear=NewNode;return(True);}elsereturn(False);}int DeleteQueue(LinkQueue *Q,int *x){LinkQueueNode *p;if(Q->front==Q->rear)return(False);p=Q->front->next;Q->front->next=p->next;if(Q->rear==p)Q->rear=Q->front;*x=p->data;free(p);return(True);}int IsEmpty(LinkQueue *Q){if(Q->front==Q->rear)return(True);elsereturn(False);}typedef struct node1{char data;struct node1 *next;}Node1, *LinkList1;typedef struct node2char data1;char data2;struct node2 *next;}Node2, *LinkList2;int a[2];int visited[N];int LocateVertex2(AdjList *G2,VertexData v){int k,j=Error;for(k=0;k<G2->vexnum2;k++)if(G2->vertex[k].data==v){j=k;break;}return(j);}int CreateUDG2(AdjList *G2){int i,j,k;ArcNode2 *p,*r;VertexData v1,v2;printf("\ninput G->vexnum,G->arcnum\n"); fflush(stdin);scanf("%d,%d",&(G2->vexnum2),&(G2->arcnum2)); getchar();printf("input G->vexs\n");for(i=0;i<G2->vexnum2;i++){fflush(stdin);scanf("%c",&(G2->vertex[i].data));G2->vertex[i].firstarc=NULL;}getchar();printf("input G v1,v2\n");fflush(stdin);for(k=0;k<G2->arcnum2;k++){fflush(stdin);scanf("%c,%c",&v1,&v2);getchar( );i=LocateVertex2(G2,v1);j=LocateVertex2(G2,v2);if(G2->vertex[i].firstarc==NULL){p=(ArcNode2*)malloc(sizeof(ArcNode2));if(p==NULL)return(False);G2->vertex[i].firstarc=p;p->adjvex=j;p->nextarc=NULL;}else{r=G2->vertex[i].firstarc;while(r->nextarc!=NULL)r=r->nextarc;p=(ArcNode2*)malloc(sizeof(ArcNode2));if(p==NULL)return(False);r->nextarc=p;p->adjvex=j;p->nextarc=NULL;}if(G2->vertex[j].firstarc==NULL){p=(ArcNode2*)malloc(sizeof(ArcNode2));if(p==NULL)return(False);G2->vertex[j].firstarc=p;p->adjvex=i;p->nextarc=NULL;}else{r=G2->vertex[j].firstarc;while(r->nextarc!=NULL)r=r->nextarc;p=(ArcNode2*)malloc(sizeof(ArcNode2));if(p==NULL)return(False);r->nextarc=p;p->adjvex=i;p->nextarc=NULL;}}return(Ok);}void Breadth2(AdjList g2,int vo){ArcNode2 *p;int vi;LinkQueue Q;InitQueue(&Q);visited[vo]=True;EnterQueue(&Q,vo);while(!IsEmpty(&Q)){DeleteQueue(&Q,&vi);printf("%c",g2.vertex[vi].data);p=g2.vertex[vi].firstarc;while(p!=NULL){if(!visited[p->adjvex]){visited[p->adjvex]=True;EnterQueue(&Q,p->adjvex);}p=p->nextarc;}}}void Depth2(AdjList g2,int vo){ArcNode2 *p;printf("%c",g2.vertex[vo].data);visited[vo]=True;p=g2.vertex[vo].firstarc;while(p!=NULL){if(!visited[p->adjvex])Depth2(g2,p->adjvex);p=p->nextarc;}}void Traverse2(AdjList g2){int vi;for(vi=0;vi<g2.vexnum2;vi++)visited[vi]=False;printf("\nThe order of G2 Depth\n");for(vi=0;vi<g2.vexnum2;vi++){if(!visited[vi]){Depth2(g2,vi);printf("\n");}}for(vi=0;vi<g2.vexnum2;vi++)visited[vi]=False;printf("\nThe order of G2 Breadth\n");for(vi=0;vi<g2.vexnum2;vi++){if(!visited[vi]){Breadth2(g2,vi);printf("\n");}}}int main( ){AdjList g2;CreateUDG2(&g2);Traverse2(g2);return 0;}测试数据与实验结果（可以抓图粘贴）实验体会1.对于运用图表和遍历还存在很大的毛病。

数据结构DATA STRUCTURE, DS授课教师：郭艳:191124授课班级: 191124中国地质大学计算机学院2014年春上堂课要点回顾图的应用一：最小生成树问题定义Prim算法及其实现Kruskal算法图的应用二：最短路径问题 定义单源最短路径问题——Dijkstra算法(O(n2))第十五次课阅读：朱战立，第235-242页习题：作业14数据结构课程内容图结构的应用3——拓扑排序图结构的应用4——关键路径9.7 拓扑排序（topological sort）先决条件问题学生选修课程问题：学生应按怎样的顺序数学模型：有向无环图顶点——活动（课程）拓扑排序将一个有向学习下列课程，才能无矛盾、顺利地完成有向弧<i,j>——活动i是活动j的先决条件无环图中所有顶点在不学业？课程代号课程名称先修课C2C4C5违反先决条件关系的前C1程序设计基础无C2离散数学C1C3数据结构C1,C2C4汇编语言C1语言的设计和分析C3C4C1C3C7提下排成线性序列的过C5C3,C4C6计算机原理C11C7编译原理C3.C5C8操作系统C3,C6C8C9C10C12程称为拓扑排序C9高等数学无C10线性代数C9C11普通物理C9C1C9C10C6C11Activity OnVertex network C12数值分析C1,C9,C10序列1：C1->C2->C3->C4->C5->C7->C9->C10->C11->C6->C12->C8序列2：C9->C10->C11->C6->C1->C12->C4->C2->C3->C5->C7->C8Vertex network9.7 拓扑排序（续）拓扑序列(topological order)对于有向无环图G=(V, E), 所有顶点组成的线性序列如果满足若在有向无环图G中从顶点V i到V j有一条路径，则在序列中顶点V必在顶点V之前i j则该线性序列可称作一个拓扑序列。

淮海工学院计算机工程学院实验报告书课程名：《数据结构》题目：图状数据结构实验班级：学号：姓名：实验报告要求1目的与要求:1）掌握图的邻接矩阵存储结构表示和与图创建算法的c语言实现；2）掌握普里姆（Prim）最小生成树算法的C语言实现及应用；3）掌握AOE网的邻接表存储结构表示及创建算法的c语言实现；4）理解AOE网的拓扑排序算法的实现原理及应用；5）掌握AOE网关键路径的计算算法及C语言实现与应用；6）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）；7）认真书写实验报告,并按时提交。

2 实验内容或题目题目1：图形数据结构实验——最小生成树的算法实现及其应用内容：按照图的“邻接巨阵”存储结构实现最小生成树的Prim算法，并以下图1所示的无向网的为例进行验证。

题目2：图的应用实验——计算AOE网的关键路径内容：按照图的“邻接表”存储结构表示AOE网，实现求其关键路径的算法，并验证如下图2所示AOE网的关键路径。

图2 AOE网3 实验步骤与源程序1)#include<stdio.h>#include<stdio.h>#include<stdlib.h>#include<string.h>#define MAX_NAME 6#define MAX_VERTEX_NUM 20typedef char Vertex[MAX_NAME];typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; struct MGraph{Vertex vexs[MAX_VERTEX_NUM];AdjMatrix arcs;int vexnum,arcnum;};typedef struct{Vertex adjvex;int lowcost;}minside[MAX_VERTEX_NUM];int LocateVex(MGraph G,Vertex u){int i;for(i=0;i<G.vexnum;++i)if(strcmp(u,G.vexs[i])==0)return i;return -1;}void CreateGraph(MGraph &G){int i,j,k,w;Vertex va,vb;printf("请输入无向网G的顶点数和边数(以空格为分隔)\n");scanf("%d %d",&G.vexnum,&G.arcnum);printf("请输入%d个顶点的值(<%d个字符):\n",G.vexnum,MAX_NAME);for(i=0;i<G.vexnum;++i)scanf("%s",G.vexs[i]);for(i=0;i<G.vexnum;++i)for(j=0;j<G.vexnum;++j)G.arcs[i][j]=0x7fffffff;printf("请输入%d条边的顶点 1 顶点 2 权值(以空格作为间隔): \n",G.arcnum);for(k=0;k<G.arcnum;++k){scanf("%s%s%d%*c",va,vb,&w);i=LocateVex(G,va);j=LocateVex(G,vb);G.arcs[i][j]=G.arcs[j][i]=w;}}int minimum(minside SZ,MGraph G){int i=0,j,k,min;while(!SZ[i].lowcost)i++;min=SZ[i].lowcost;k=i;for(j=i+1;j<G.vexnum;j++)if(SZ[j].lowcost>0&&min>SZ[j].lowcost){min=SZ[j].lowcost;k=j;}return k;}void MiniSpanTree_PRIM(MGraph G,Vertex u){int i,j,k;minside closedge;k=LocateVex(G,u);for(j=0;j<G.vexnum;++j){strcpy(closedge[j].adjvex,u);closedge[j].lowcost=G.arcs[k][j];}closedge[k].lowcost=0;printf("最小代价生成树的各条边为:\n");for(i=1;i<G.vexnum;++i){k=minimum(closedge,G);printf("(%s-%s)\n",closedge[k].adjvex,G.vexs[k]);closedge[k].lowcost=0;for(j=0;j<G.vexnum;++j)if(G.arcs[k][j]<closedge[j].lowcost){strcpy(closedge[j].adjvex,G.vexs[k]);closedge[j].lowcost=G.arcs[k][j];}}}int main(){MGraph g;CreateGraph(g);MiniSpanTree_PRIM(g,g.vexs[0]);system("PAUSE");return 0;}2)#include<stdio.h>#include<iostream>using namespace std;#define n 9#define ed 11#define maxsize 20typedef char vextype;typedef struct node1{int adjvex;int dut;struct node1 *next;}edgenode1;typedef struct{vextype vertex;int id;edgenode1 *link;}vexnode1;void creatgraph(vexnode1 dig[]);void criticalpath(vexnode1 dig[]);void main(){printf(" ——AOE网的关键路径——\n");vexnode1 dig[n];creatgraph(dig);printf("【输出AOE网的邻接表】\n");int i;edgenode1 *s;for(i=0;i<n;i++){printf("|%c %d |",dig[i].vertex,dig[i].id);s=dig[i].link;while(s){printf("——> %d %d",s->adjvex+1,s->dut);s=s->next;}printf("\n");}printf("【输出关键活动】\n");printf("每行分别为开始事件、结束事件、最早开始时间、最迟开始时间和完成活动的时间余量\n");criticalpath(dig);}void creatgraph(vexnode1 dig[]){printf("【输入AOE网的顶点（顶点信息和入度，用空格隔开）】\n");int i;for(i=0;i<n;i++){printf("第%d个顶点的信息和入度：",i+1);cin>>dig[i].vertex>>dig[i].id;dig[i].link=NULL;}printf("【输入AOE网的边（始点、终点和权，用空格隔开）】\n");edgenode1 *s;int a,b;for(i=0;i<ed;i++){s=(edgenode1 *)malloc(sizeof(edgenode1));printf("第%d条边的始点、终点和权：",i+1);cin>>a>>b>>s->dut;s->adjvex=b-1;s->next=dig[a-1].link;dig[a-1].link=s;}}void criticalpath(vexnode1 dig[]) {int i,j,k,m;int front=-1,rear=-1;int tport[n],vl[n],ve[n];int l[maxsize],e[maxsize]; edgenode1 *p;for(i=0;i<n;i++)ve[i]=0;for(i=0;i<n;i++)if(dig[i].id==0)tport[++rear]=i;m=0;while(front!=rear){front++;j=tport[front];m++;p=dig[j].link;while(p){k=p->adjvex;dig[k].id--;if(ve[j]+p->dut>ve[k])ve[k]=ve[j]+p->dut;if(dig[k].id==0)tport[++rear]=k;p=p->next;}}if(m<n){printf("AOE网有回路\n");return;}for(i=0;i<n;i++)vl[i]=ve[n-1];for(i=n-2;i>=0;i--){j=tport[i];p=dig[j].link;while(p){k=p->adjvex;if((vl[k]-p->dut)<vl[j])vl[j]=vl[k]-p->dut;p=p->next;}}i=0;for(j=0;j<n;j++){p=dig[j].link;while(p){]k=p->adjvex;e[++i]=ve[j];l[i]=vl[k]-p->dut;printf("%c\t%c\t%d\t%d\t%d\t",dig[j].vertex,dig[k].vertex,e[i],l[i],l[i]-e[i]);if(l[i]==e[i])printf("关键活动");printf("\n");p=p->next;}}}4 测试数据与实验结果（可以抓图粘贴）(1)(2)5 结果分析与实验体会做完了这一份报告，我对图的邻接矩阵存储结构表示和与图创建算法的c语言实现有了一定的认识，体会到了普里姆（Prim）最小生成树算法的C语言实现及应用，完成的过程中了解了AOE网的拓扑排序算法用C语言的实现以及对其关键路径的计算算法的应用与实现。

数据结构实验报告--图【数据结构实验报告--图】【一、实验目的】本实验旨在掌握图的基本概念、存储结构以及相关操作，并通过实验加深对图的理解。

【二、实验环境】操作系统：Windows 10编程语言：C++开发工具：Dev-C++ 5.11【三、实验内容】1.图的定义与基本概念1.1 图的定义：有向图、无向图1.2 图的基本概念：顶点、边、路径、路径长度2.图的存储结构2.1 邻接矩阵表示法2.2 邻接表表示法3.图的操作3.1 图的创建①手动输入图的顶点和边②从文件中读取图的顶点和边3.2 图的遍历①深度优先遍历（DFS）②广度优先遍历（BFS）3.3 图的最小树① Prim算法② Kruskal算法3.4 图的最短路径① Dijkstra算法② Floyd算法4.实验结果分析4.1 图的创建结果4.2 图的遍历结果4.3 图的最小树结果4.4 图的最短路径结果【四、实验步骤】1.定义图的数据结构和相关操作的函数原型。

2.实现图的存储结构和相关操作的函数实现。

3.开发主程序，包括菜单、用户输入、调用图操作函数等。

4.运行程序，测试各个功能是否正常进行。

5.根据运行结果分析，进行必要的调试和优化。

【五、实验结果】1.图的创建结果：●手动输入图的顶点和边：●顶点数.10●边数.15●从文件中读取图的顶点和边：●顶点数.8●边数.122.图的遍历结果：●深度优先遍历：●遍历路径.1 -> 2 -> 4 -> 5 -> 3●广度优先遍历：●遍历路径.1 -> 2 -> 3 -> 4 -> 53.图的最小树结果：●Prim算法：●最小树顶点集合：{1, 2, 4, 5}●最小树边集合：{(1, 2), (2, 4), (2, 5)}●Kruskal算法：●最小树边集合：{(1, 2), (2, 4), (2, 5)}4.图的最短路径结果：●Dijkstra算法：●从顶点1到其他顶点的最短路径长度：●1 -> 2、2●1 -> 3、5●1 -> 4、4●1 -> 5、6●Floyd算法：●图的最短路径邻接矩阵：●0 2 5 4 6●2 0 3 1 3●5 3 0 5 4●4 1 5 0 2●6 3 4 2 0【附件】无【法律名词及注释】1.顶点：图中的一个节点，可以表示实体或事件。