图结构试验实验报告..doc

附件（四） 深 圳 大 学 实 验 报 告 课程名称： 数据结构实验与课程设计 实验项目名称： 图结构实验 学院： 计算机与软件学院 专业： 指导教师： 报告人： 学号： 班级： 实验时间： 实验报告提交时间： 教务处制 一、实验目的与完成说明： 1. 简单介绍本实验的主要目的 2. 说明你自己在本次实验中完成了第几项要求（必填） Contest1620 - DS实验08--图遍历【11.12】 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--最短路径【11.19】 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--图遍历【11.12】 Problem A: DS图遍历--深度优先有哪些信誉好的足球投注网站 0 0 4 3 2 1 0 0 3 1 2 从0开始连续获取邻接结点，然后逐个遍历并设Visit为true避免重复遍历 04 0 4 3 2 1 0 0 3 1 2 首先将该顶点的邻接顶点全部入队，然后挨个读取，在读取的过程中继续将邻接矩阵入队，并把已经读取过的顶点全被设为true。 Contest1638 - DS实验09--最短路径【11.19】 12 1 2 0 3 4 1 5 2 7 5 15 ① 输入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 ⑤初