课程名称实验项目名称实验成绩
浙江大学城市学院实验报告
pytho
高级程序设计
实验六图的基本操作与应用
指导老师（签名）
日期
一实验目的和要求1、掌握图的存储结构：邻接矩阵、邻接表。2、掌握图的深度优先与广度优先两个搜素算法。3、学会对图的存储结构进行基本操作。4、加强综合程序的分析、设计能力。
二实验内容1、现有14个人（分别用字母A、B、N表示），他们相互之间的朋友关系如图所示（有线相连表示是朋友关系），请分别用邻接矩阵与邻接表表示该关系图，并完成以下功能。
①以邻接矩阵表示，在此结构上完成：创建此图；输出此图的邻接矩阵；输出从A出发的深度优先搜索序列；输出从A出发的广度优先搜索序列；输入两个人p1、p2，判断此两人是否为朋友关系，若不是，给出一种从p1能找到p2的路径；（如输入p1‘A’、p2‘N’，则A与N不是直接朋友关系，但可以（不唯一）通过ABFKN方式联系到N。）
②以邻接表表示，在此结构上完成：创建此图；输出此图的邻接表；
f输出从A出发的深度优先搜索序列；输出从A出发的广度优先搜索序列；输入两个人p1、p2，判断此两人是否为朋友关系，若不是，给出一种从p1能找到p2的路径；（如输入p1‘A’、p2‘N’，则A与N不是直接朋友关系，但可以（不唯一）通过ABFKN方式联系到N。）
③编写程序，分别实现上述两种存储结构，实现相同的功能。④自行增加合适的功能，可作为额外的实验成绩进行加分（例如考虑添加或删除一对朋友关系；找出朋友最多的那个人；上面找到A到N的联系路径，若要求找到一条最短的路线怎么找等等）。
2、以小组为单位认真填写实验报告，实验报告必须包括各类数据类型的结构定义说明，各类数据的组织方式，系统的功能结构，各个操作的定义以及实现方法，运行结果与分析，难点如何解决，存在问题以及可改进之处等。同时，在实验报告中需写明小组每位同学的分工，得分（小组总分不超过12分）等。实验报告文件取名为report6doc。每组还必须制作一个答辩PPT以备答辩。3、由组长上传实验报告文件、源程序文件到BB平台上。
三实验结果与分析（一）小组分工
徐慧：创建此图；输出此图的邻接矩阵；郑博思：输出从A出发的深度优先搜索序列；输出从A出发的广度优先搜索序列；郑超：输入两个人p1、p2，判断此两人是否为朋友关系，若不是，给出一种从p1能找到p2的路径；（如输入p1‘A’、p2‘N’，则A与N不是直接朋友关系，但可r