广州大学数据结构实验报告实验三图的操作与实现_实现图的邻接矩阵和邻接表存储实验报告 - CSDN文库

图的操作与实现

5星 · 超过95%的资源需积分: 43 97 浏览量更新于2023-03-03 评论 3 收藏 209KB DOC 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

广州大学学生实验报告

开课实验室：计算机科学与工程实验（电子楼 517）

学院

计算机科学

与网络工程

学院

年级、

专业、

班

姓名学号

实验课程数据结构实验成绩

实验项目实验三图的操作与实现

指导

老师

一、实验目的：

1、图的邻接表和邻接矩阵存储

2、图的各种遍历算法实现

3、最小生成树的算法实现

4、最短路径的算法实现

二、使用仪器、器材

微机一台

操作系统：WIN10

编程软件：C++

三、实验内容及原理

利用图的邻接表或邻接矩阵存储结构设计并实现各种操作算法（任选一种存储结构来实

现算法）。

1、图的邻接表和邻接矩阵存储

建立下图的邻接表或邻接矩阵，并输出之；

是否还有其他没有被访问过的邻接顶点：如果有，则访问此顶点，之后再从此顶点

出发，进行与前述类似的访问；如果没有，就再退回上一步进行搜索。重复上述过

程，直至连通图中所有顶点都被访问过为止；

2 需要建立一个辅助数组，判断顶点是否被访问过。

广度优先遍历算法：

1 从图的某一结点出发，首先依次访问该结点的所有邻接结点，再按照这些顶点被访问

的先后次序依次访问与它们相邻接的所有未被访问的结点。重复此过程，直至所有顶

点均被访问为止。

2 需要建立一个辅助队列和辅助数组，由于广度优先类似与层次遍历，如果顶点未访问

过，则实行入队；如果顶点访问过，则实行出队，其未被访问过的邻接点入队，通过

队列实现①中的部分功能，出队的元素顺序即为广度优先遍历的结果。

3、最小生成树的算法实现

利用普里姆（Prim）算法或克鲁斯卡尔(Kruskal)算法求上图的最小生成树，算法

实现代码必须有注释。

无论是普里姆（Prim）算法还是克鲁斯卡尔(Kruskal)算法，都利用了 MST 性质

构成最小生成树。MST 性质：设 N=（V,E）是一个连通网，U 是顶点集 V 的一个非空

子集。若边（u,v）是一条具有最小权值的边，其中 u∈U，v∈V-U，则必存在一棵包

含边（u,v）的最小生成树。在生成树的构造过程中，图中 n 个顶点分属两个集合：①

已落在生成树上的顶点集：U；②尚未落在生成树上的顶点集：V-U。接下来则应在所

有连通 U 中顶点和 V-U 中顶点的边中选取权值最小的边。

普里姆（Prim）算法：

设 N=（V,E）是连通网，TE 是 N 上最小生成树中边的集合。初始令 U=｛u0｝，

（u0∈V）， TE=｛｝，在所有 u∈U，v 属于 V-U 的边（u,v）∈E 中，找一条代价最

小的边（u0,v0），将（ u0,v0）并入集合 TE，同时 v0 并入 U。重复上述操作直至

U=V 位置，则 T=（V,TE）为 N 的最小生成树；

克鲁斯卡尔(Kruskal)算法：

设连通网 N=（V,E），令最小生成树初始状态为只有 n 个顶点而无边的非连通图

T=（V，｛｝），每个顶点自成一个连通分量。在 E 中选取代价最小的边，若该边依

剩余11页未读，继续阅读

评论5

士多霹雳酱

2023-07-27

报告内容简洁明晰，让人一目了然地掌握了图相关的基本概念和操作方法。

李阿伯

粉丝: 9
资源: 5

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈