数据结构实验报告_8.docVIP

沈 阳 工 程 学 院 学 生 实 验 报 告 实验室名称：信息工程系软件实验室 实验课程名称：数据结构 实验项目名称：图的结构及多种应用 班 级：计专本121 姓 名：郑永凯 学 号：2012461127 实验日期： 2013 年 5 月 17 日 实验台编号：17 指导教师：代钦 批阅教师（签字）： 成绩： 实验目的 1.掌握图的存储思想及其存储实现。 2.掌握图的深度，广度优先遍历算法思想及其程序实现。 3.掌握图的常见应用算法的思想及其程序实现。 实验内容 1.键盘输入数据，建立一个有向图的邻接表或邻接矩阵。 2.输出该邻接表或邻接矩阵。 3.以有向图的邻接表或邻接矩阵为基础实现输出它的拓扑排序序列。 4.采用邻接表或邻接矩阵存储实现图的深度优先遍历。 5.采用邻接表或邻接矩阵存储实现图的广度优先遍历。 6.采用邻接矩阵存储实现无向图的最小生成树的 PRIM 算法。 7.在主函数中设计一个简单的菜单，分别调试上述算法。 8.3和6是选做题 实验前的准备 理解图的存储思想。 理解图的深度，广度优先遍历算法思想。 理解图的常见应用算法的思想。 实验要求及实验软硬件环境 【基本要求】 掌握图的存储思想。 掌握图的深度，广度优先遍历算法思想。 掌握图的常见应用算法的思想。 完成此项实验，完成实验报告 【实验组织方式】 个人实验 【实验条件】 Windows操作系统 实验过程及程序清单 了解图的结构 图是一种数据结构，由二个集合V和E组成，记做G=(V,E)，其中V是数据元素的非空有限集合，E是V中二元关系（边）的集合。即V是顶点的集合，E是顶点的偶对，即边的集合。 根据E的性质，图可分为两类： ① 有向图：图的每条边都是有序顶点对（即边是有方向的） ② 无向图：图的每条边都是无序顶点对（即边是无方向的） 建立有向图的邻接矩阵 代码： typedef struct { int vexnum,arcnum;/* 当前图的顶点数和边或弧数*/ VexType vexs[N]; /* 图中N个顶点的信息*/ AdjType arcs[N][N]; /* 图邻接矩阵信息。对无权图，用0或1表示相邻否；对带权图，则为权值类型*/ }graph; void CreatGraph(graph *ga) /* 建立一个有向图ga*/ { int i,j,w; /*w表示是否邻接*/ char v; ga-vexnum=0;ga-arcnum=0; i=0; cout读入顶点信息endl; while((v=getchar())!=#) { ga-vexs[i]=v; /*读入顶点信息*/ i++; } ga-vexnum=i; /*顶点数目*/ for(i=0;iga-vexnum;i++) /*邻接矩阵初始化*/ for(j=0;jga-vexnum;j++) ga- arcs [i][j]=0; cout读入边信息endl; scanf (%d,%d,%d ,i,j,w); /*读入边(i,j)上的w*/ while(i!=-1) { ga- arcs [i][j]=w; scanf (%d,%d,%d ,i,j,w); } 其具体实现如下图1所示： 图1 创建有向图邻接矩阵 3、显示邻接矩阵 代码： cout显示邻接矩阵endl; for(i=0;iga-vexnum;i++) { for(j=0;jga-vexnum;j++) coutga- arcs [i][j]\t; coutendl; } 其具体实现如图2所示： 图2 显示邻接矩阵 4、选择算法 ①深度优先算法 代码： void dfs(int i,graph *g){ /*深度优先有哪些信誉好的足球投注网站递归算法*/ int j; printf(node:%c\n,g-vexs[i]); visited[i]=TRUE; for(j=0;jg-vexnum;j++) if((g-arcs[i][j]==1)(!visited[j])) dfs(j,g); } void tdfs(graph *g) { ///*深度优先有哪些信誉好的足球投注网站遍历整图算法*/ int i; for(i=0;ig-vexnum;i++) if(visited[i]!=TRUE)