数据结构图_

来源:火狐app 时间:2022-09-17 05:36:48 阅读:9

  【试验意图】 1、把握图的邻接矩阵和邻接表表明。 2、把握图的深度优先和广度优先查找办法。 3、把握图的最小生成树 Prim 算法。 4、把握图的拓扑排序算法。 5、把握图的单源最短途径 dijkstra 算法。

  【试验预习】 答复以下问题: 1、写出图 7-1 无向图的邻接矩阵表明。 G A F C B

  3、写出图 7-1 的深度优先查找序列和广度优先查找序列。 深度优先查找序列:A,C,B,D,E,F,G,H 广度优先查找序列:A,B,C,D,E,F,G,H, 常熟理工学院计算机科学与工程学院 2

  4、写出图 7-2 的拓扑序列,阐明该有向图是否有环? 拓扑序列:EABCD 该有向图没有环

  【试验内容和要求】 1、编写程序 exp7_1.c,完成图的邻接矩阵存储及图的深度优先查找和广度优先查找。

  以图 7-1 的无向图为例,弥补完好程序,调试运转并写出运转成果。 运转成果:(包含输入数据) 常熟理工学院计算机科学与工程学院 3

  2、编写程序 exp7_2.c,完成图的邻接表存储和拓扑排序算法。 以图 7-2 的有向图为例,弥补完好程序,调试运转并写出运转成果。 运转成果:(包含输入数据)

  3、编写程序 exp7_3.c,完成带权图的存储、图的最小生成树及单源最短途径算法。 以图 7-3(求该图最小生成树)和图 7-4(求该图的单源最短途径)为例,弥补完好程 序,调试运转并写出运转成果。 运转成果:(包含输入数据)

  Kruskal 算法完成的根本过程: ( 1)需求对图中一切的边进行排序,因而需求凭借一个辅佐数组 edge 来存储按权值由 小到大排序的边。包含边的权值、边的起点和结尾。 ( 2)每参加一条边,需求判别该边的两个极点是否处在同一连通重量上,能够使用数 组 parents 来表明各极点的情况,parents[i]=i;初始值设置为各自的极点值,表明各顶 点自成一连通重量。当参加该边,需求对该边的边头极点和边尾极点的 parents 值持平。

  5、编写算法,完成图的最短途径 Floyd 算法。 提示: 弗洛伊德算法的根本过程:对有向图选用带权邻接矩阵存储,一起界说一个二维数组 A[N][N]寄存极点 i 到 j 的最短途径。 ( 1)初始化 A[i][j]=arcs[i][j]; ( 2)考虑 vi 和 vj 之间的途径,是否存在途经 vk 的途径(vi,vk,vj),若存在,比较 A[i][k]A[K][j]和 A[i][j]的间隔,较小送 A[i][j];

  重复上步,取 vk 为图中一切极点,直到比较结束。 一起还必须界说一个矩阵记载最短途径经过的极点。 voidFloyd() {

  } 6、编写算法,完成图的要害途径算法。 提示: 依据邻接矩阵的要害途径的求解过程: (1)对 AOE 网进行拓扑排序,一起按拓扑序列的次第求出各极点事情的最早产生时间 ve, 若网中存在回路,则算法停止,不然履行过程(2); (2)按拓扑序列的逆序求出各极点事情的最迟产生时间 vl; (3)依据各极点事情的 ve 和 vl 值,求出各极点活动 ai 的最早产生时间 e(i)和最迟产生时 间 l(i)。若 e(i)= l(i),则 ai 为要害活动。

  经过试验七——图,我学会了的邻接矩阵和邻接表表明,学会了图的深度优先和广度优 先查找办法以及图的最小生成树 Prim 算法、图的拓扑排序算法。

地址:北京市海淀区丰秀中路3号院12号楼 / 邮编:100094 / 电话:010-82695000 010-82883933 / 传真:010-82883858

版权所有: 京ICP备05008170号 京公网安备11010802029694号
© All rights reserved by 火狐app

扫一扫,关注