数据结构实验报告
1．实验要求（1）实验目的通过选择下面5个题目之一进行实现，掌握如下内容：掌握图基本操作的实现方法了解最小生成树的思想和相关概念了解最短路径的思想和相关概念学习使用图解决实际问题的能力2实验内容根据图的抽象数据类型的定义，使用邻接矩阵或邻接表实现一个图。
图的基本功能：1、图的建立2、图的销毁3、深度优先遍历图4、广度优先遍历图5、使用普里姆算法生成最小生成树6、使用克鲁斯卡尔算法生成最小生成树7、求指定顶点到其他各顶点的最短路径8、其他：比如连通性判断等自定义操作
编写测试mai
函数测试图的正确性
2程序分析
21存储结构图：1带权值的无向图
9
V1
2带权值的有向图V0
V06
2
V2
f39
64
V1
2
V2
22关键算法分析
（1）深度优先遍历
i
tvisitedMAXSIZEfalsetemplateclassTvoidMGraphTDFSi
tv
coutvertexvvisitedvtruefori
tj0jvNumj
ifarcvj1visitedjDFSj

时间复杂度：O

（2）广度优先遍历i
tqueueMAXSIZE
i
tf0r0coutvertexvvisitvtruequeuervwhilefr
vqueueffori
tj0jvNumj
ifarcvj1visitjcoutvertexjvisitjtruequeuerj
时间复杂度：O（
）（3）普利姆算法i
tadjvexMAXSIZEi
tlowcostMAXSIZEi
tMAX10000templateclassT
fi
tmi
i
umMGraphTGi
ta
i
tmi
MAXi
tk0fori
ti0iGvNumi
ifai0aimi
寻找UVU中边权值最小的顶点
mi
aikiretur
k
templateclassTvoidMGraphTPrimMGraphG
fori
ti0iGvNumi
adjvexi0lowcostiGarcs0ilowcost00初始化Uvofori
ti1iGvNumii
tkmi
i
umGlowcost求下一个边权值最小的邻接点coutVadjvexk