广州大学数据结构实验报告实验三图的操作与实现

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

1、图的邻接表和邻接矩阵存储 2、图的各种遍历算法实现 3、最小生成树的算法实现 4、最短路径的算法实现

广州大学学生实验报告

开课实验室：计算机科学与工程实验（电子楼 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页未读，继续阅读

李阿伯

粉丝: 10
资源: 5

广州大学 数据结构实验报告 实验三 图的操作与实现

数据结构实验报告（链表，栈，串，数组，邻接表，邻接矩阵，查找，归并排序和快速排序的实验代码）

《数据结构》C语言版 实验报告 （基础共7个实验含代码和结果）

广州大学数据结构实验报告+源码.rar

广州大学 数据结构实验报告 实验二 二叉树的操作与实现

广州大学 数据结构实验报告 实验四 查找和排序算法实现

广州大学数据结构实验报告及源码解析

广州大学数据结构实验1-6.zip

广州大学计算机系统结构与操作系统实验报告

广州大学计网实验报告五 模拟网桥与校验和【python实现】

广州大学 动态几何实验报告.zip

最新资源

广州大学数据结构实验报告实验三图的操作与实现

《数据结构》C语言版实验报告（基础共7个实验含代码和结果）

广州大学数据结构实验报告实验二二叉树的操作与实现

广州大学数据结构实验报告实验四查找和排序算法实现

广州大学计网实验报告五模拟网桥与校验和【python实现】

广州大学动态几何实验报告.zip