数据结构实验一图剖析Word下载.docx
《数据结构实验一图剖析Word下载.docx》由会员分享，可在线阅读，更多相关《数据结构实验一图剖析Word下载.docx（20页珍藏版）》请在冰点文库上搜索。
存储结构：
1.不带权值的无向图邻接矩阵
2.带权值的无向图邻接矩阵
3.带权值的有向图邻接矩阵
1．不带权值的无向图邻接矩阵
2带权值的无向图邻接矩阵.
3.带权值的有向图邻接矩阵
[备注]：
1.在使用打印元素、BFS、DFS采用无权值的无向图邻接矩阵存储方式
2.在使用PRIM、KRUSKAL、
3.在使用最短路径的算法时采用具有权值的有向图邻接矩阵存储方式
2.2关键算法分析
一．图的邻接矩阵构造函数：
1.关键算法：
template<
classf>
Graph<
f>
:
Graph（fa[],intn,inte）//带权值的图的构造函数
{
inti,j,k,height;
fs1,s2;
vnum=n;
arcnum=e;
for（k=0;
k<
n;
k++）{vertex[k]=a[k];
}//初始化顶点
k<
n;
k++）
{
for（i=0;
i<
i++）
{
arc[k][i]=-1;
if（i==k）arc[k][i]=0;
//初始化权值的大小
}
visited[k]=0;
}
cout<
<
endl;
e;
k++）//初始化边
cout<
"
请输入线性链接节点:
"
;
cin>
>
s1>
s2>
height;
arc[convert（s1）][convert（s2）]=height;
arc[convert（s2）][convert（s1）]=arc[convert（s1）][convert（s2）];
//采用无向图带权值的邻接矩阵
所得邻接矩阵为：
<
if（arc[k][i]==-1）
cout<
∞"
elsecout<
arc[k][i]<
//打印邻接矩阵的格式
endl
2.算法的时间复杂度
有构造可知，初始化时其时间复杂度：
O（n2）
二．深度优先便利DFS:
1.关键算法
①从某顶点v出发并访问
②访问v的第一个未访问的邻接点w，
访问w的第一个未访问的邻接点u，
……
③若当前顶点的所有邻接点都被访问过，则回溯，从上一级顶点的下一个未访问过的顶点开始深度优先遍历
④直到所有和v路径相通的顶点都被访问到；
2.代码图解：
深度优先遍历示意图
3.代码详解：
voidGraph<
DFS（intv）
vertex[v];
visited[v]=1;
for（intj=0;
j<
vnum;
j++）//连通图
if（（visited[j]==0）&
&
（arc[v][j]>
=1））DFS（j）;
//当存在回路时，则连通深一层遍历
}
4.时间复杂度
时间复杂度：
空间复杂度：
栈的深度O（n）
辅助空间O（n）
三．广度遍历BFS
①访问顶点v
②依次访问v的所有未被访问的邻接点v1,v2,v3…
③分别从v1,v2,v3…出发依次访问它们未被访问的邻接点
④反复①②③，直到所有和v路径相通的顶点都被访问到；
2.代码图解
3.代码详解
1.初始化队列Q
2.访问顶点v，visited[v]=1
3.while（队列非空）
3.1v=队头元素出队
3.2访问队头元素的所有未访问的邻接点
4.时间复杂度
时间复杂度：
空间复杂度：
四.最小生成树——普里姆算法
1,关键思路
一般情况下，假设n个顶点分成两个集合：
U（包含已落在生成树上的结点）和V-U（尚未落在生成树上的顶点），则在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。
主数据结构：
邻接矩阵
辅助数据结构：
intadjvex[MAXSIZE];
//U集中的顶点序号
intlowcost[MAXSIZE];
//Uà
（V-U）的最小权值边
3;
代码详解
Prim（）
for（inti=0;
i++）//辅助数组存储所有到的V0边
adjvex[i]=0;
lowcost[i]=arc[0][i];
lowcost[0]=0;
for（intj=1;
j++）//循环n-1次
intk=Mininum（lowcost）;
//求下一个顶点
vertex[adjvex[k]]<
->
vertex[k]<
lowcost[k]=0;
//U=U+{Vk}
for（intj=0;
j++）//设置辅助数组
{
if（（lowcost[j]!
=0&
arc[k][j]<
lowcost[j]））
{
lowcost[j]=arc[k][j];
adjvex[j]=k;
}
4,时间复杂度：
时间复杂度O（n2），适合稠密图
五.最小生成树----克鲁斯卡尔算法
先构造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加上这条边，如此重复，直至加上n-1条边为止。
Kruskal（）//最小生成树—kruskal算法
cout<
Krusal算法结果为：
endl;
intvset[MAXSIZE];
i++）vset[i]=i;
intk=0,j=0;
while（k<
vnum-1）
intm=vedgelist[j].fromv,n=vedgelist[j].endv;
intsn1=vset[m];
intsn2=vset[n];
//两个顶点分属不同的集合
if（sn1!
=sn2）
cout<
vertex[m]<
vertex[n]<
k++;
for（inti=0;
if（vset[i]==sn2）
vset[i]=sn1;
//集合sn2全部改成sn1
j++;
时间复杂度O（nlogn），适合稀疏图
六．最短路径——Dijkstra算法
1.关键代码
•按路径长度递增的次序产生源点到其余各顶点的最短路径。
•1）设置集合s存储已求得的最短路径的顶点，
•2）初始状态：
s=源点v
•3）叠代算法：
•直接与v相连的最近顶点vi,加入s
•从v经过vi可以到达的顶点中最短的，加入s
emplate<
ShotPath（fx）//关于最短路径的初始化
intv=convert（x）;
i++）//初始化路径和点
s[i]=0;
disk[i]=arc[v][i];
if（disk[i]!
=maxs）path[i]=v;
elsepath[i]=-1;
s[v]=1;
disk[v]=0;
path[v]=-1;
i++）//反复经过从该点到其他点的路径
if（（v=FindMin（））==-1）continue;
s[v]=1;
j++）
if（!
s[j]&
（disk[j]>
arc[v][j]+disk[v]））
disk[j]=arc[v][j]+disk[v];
path[j]=v;
Print（）;
//打印路径长度和遍历
时间复杂度为：
n^2
七．判断连通图算法
boolGraph<
judgegraph（）
DFS（convert（vertex[0]））;
if（count==vnum）
{
该图为连通图！
*******输入成功！
returnfalse;
else
该图不为连通图！
*******请重新输入"
returntrue;
3.程序运行结果
1.测试主函数流程：
函数流程图：
1.输入图的连接边并打印
构造下面所示图的邻接矩阵：
2.判断图连通是否成功
3.BFSDFSPRIM算法的实现
4.克鲁斯卡尔算法实现过程
4.有向图邻接矩阵的构建
插入V0位置后打印距离并开始回溯
总结
1.调试时出现的问题及解决的方法
问题一：
prim算法中
解决方法：
调整循环条件，修正函数体注意有无Next的区别
问题二：
BFS和DFS同时在一个类里作用时会输出错误
解决方案：
每次BFS/DFS使用时都把visited数组初始化一遍
问题三：
在最短路径，经常出现了停止输入的情况
改return为continue，并修改打印算法
2.心得体会
通过本次实验，基本熟练掌握了c++基本语句，尤其对图的结构及应用有了较深了解；
调试代码时尽量做到完成一个代码段调试一次，可以最快检测出错误所在；
类的封装和调用，类的共有成员和私有成员的设置。
3.下一步的改进
第一，设置增加图节点和边的函数
第二，实现图形化输出图的路径的功能
第三，主函数设计简单，不要过于累赘
4.程序中出现的亮点
1）利用dfs算法衍生生成判断是否为连通图的连通算法
2）采用graph类实现所有图的所有算法，所需的数据类型均在私有成员内，封装
3）利用convert函数采取象意输入，采用ABCD的节点输入方式而并非转化成01234再输入。
4）BFS中采用c++标准库的。
5）打印邻接矩阵时，打印出非链接的∞符号和与自身路径的0距离
6）判断图为非连通图后，提示输入错误，重新输入图元素
升级会员 