文档介绍：附件(四)
深圳大学实验报告
课程名称: 数据结构实验与课程设计
实验项目名称: 图结构实验
学院: 计算机与软件学院
专业:
指导教师:
报告人: 学号: 班级:
实验时间:
实验报告提交时间:
教务处制
一、实验目的与完成说明:
1. 简单介绍本实验的主要目的
2. 说明你自己在本次实验中完成了第几项要求(必填)
Contest1620 - DS实验08--图遍历【】
Problem A: DS图遍历--深度优先搜索
Description
主要目的:
给出一个图的邻接矩阵,对图进行深度优先搜索,从顶点0开始(完成)
注意:图n个顶点编号从0到n-1
Input
第一行输入t,表示有t个测试实例(完成)
第二行输入n,表示第1个图有n个结点(完成)
第三行起,每行输入邻接矩阵的一行,以此类推输入n行(完成)
第i个结点与其他结点如果相连则为1,无连接则为0,数据之间用空格隔开(完成)
以此类推输入下一个示例(完成)
Output
每行输出一个图的深度优先搜索结果,结点编号之间用空格隔开(完成)
Problem B: DS图遍历--广度优先搜索
Description
给出一个图的邻接矩阵,对图进行深度优先搜索,从顶点0开始(完成)
注意:图n个顶点编号从0到n-1
Input
第一行输入t,表示有t个测试实例(完成)
第二行输入n,表示第1个图有n个结点(完成)
第三行起,每行输入邻接矩阵的一行,以此类推输入n行(完成)
第i个结点与其他结点如果相连则为1,无连接则为0,数据之间用空格隔开(完成)
以此类推输入下一个示例
Output
每行输出一个图的广度优先搜索结果,结点编号之间用空格隔开(完成)
Contest1638 - DS实验09--最短路径【】
Problem A: DS图应用--最短路径
Description
给出一个图的邻接矩阵,再给出指定顶点v0,求顶点v0到其他顶点的最短路径(完成)
Input
第一行输入t,表示有t个测试实例(完成)
第二行输入n,表示第1个图有n个结点(完成)
第三行起,每行输入邻接矩阵的一行,以此类推输入n行(完成)
第i个结点与其他结点如果相连则为1,无连接则为0,数据之间用空格隔开
第四行输入v0,表示求v0到其他顶点的最短路径距离(完成)
以此类推输入下一个示例
Output
每行输出v0到某个顶点的最短距离和最短路径(完成)
每行格式:v0编号-其他顶点编号----[最短路径],具体请参考示范数据(完成)
二、主要思路与方法:
1. 对于本次实验,说明你认为最重要的函数、算法或知识点,并谈谈你对它们的理解
Contest1620 - DS实验08--图遍历【】
Problem A: DS图遍历--深度优先搜索
0
4
3
2
1
0
3
1
2
从0开始连续获取邻接结点,然后逐个遍历并设Visit为true避免重复遍历
0
4
3
2
1
Problem B: DS图遍历--广度优先搜索
0
3
1
2
首先将该顶点的邻接顶点全部入队,然后挨个读取,在读取的过程中继续将邻接矩阵入队,并把已经读取过的顶点全被设为true。
Contest1638 - DS实验09--最短路径【】
1
2
0
3
4
1
5
2
7
5
15
Problem A: DS图应用--最短路径
①输入mx矩阵
Mx
0
1
2
3
4
0
0
5
0
7
15
1
0
0
5
0
0
2
0
0
0
0
1
3
0
0
2
0
0
4
0
0
0
0
0
②初始化并赋值Matrix的矩阵
Matrix
0
1
2
3
4
0
∞
5
∞
7
15
1
∞
∞
5
∞
∞
2
∞
∞
∞
∞
1
3
∞
∞
2
∞
∞
4
∞
∞
∞
∞
∞
③初始化并赋值path的矩阵
Path
0
1
2
3
4
0
-1
-1
-1
-1
-1
1
0
1
-1
-1
-1
2
-1
-1
-1
-1
-1
3
0
-1
-1
3
-1
4
0
-1
-1
-1
4
④初始化并赋值dist数组
Dist
0
1
2
3
4
∞
5
∞
7
15
⑤初始并赋值len数组
Len
0
1
2