数据结构 实验一 图[推荐]_数据结构图实验

数据结构 实验一 图[推荐]由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构图实验”。

北京邮电大学信息与通信工程学院

数据结构实验报告

实验名称： 实验二——图 学生姓名： 佘晨阳 班

级： 2014211117 班内序号： 20 学

号： 2014210491 日

期： 2015年12月05日

1．实验要求

根据图的抽象数据类型的定义，使用邻接矩阵或邻接表实现一个图。图的基本功能：

1、图的建立

2、图的销毁

3、深度优先遍历图

4、广度优先遍历图

5、使用普里姆算法生成最小生成树

6、使用克鲁斯卡尔算法生成最小生成树

7、求指定顶点到其他各顶点的最短路径

8、其他：比如连通性判断等自定义操作

编写测试main()函数测试图的正确性

2.程序分析

本实验要求掌握图基本操作的实现方法，了解最小生成树的思想和相关概念，了解最短路径的思想和相关概念，学习使用图解决实际问题的能力。

2.1 存储结构

存储结构：1.不带权值的无向图邻接矩阵

2.带权值的无向图邻接矩阵

3.带权值的有向图邻接矩阵

1．不带权值的无向图邻接矩阵

第1页 北京邮电大学信息与通信工程学院

2带权值的无向图邻接矩阵.3.带权值的有向图邻接矩阵

[备注]：

1.在使用打印元素、BFS、DFS 采用无权值的无向图邻接矩阵存储方式 2.在使用PRIM、KRUSKAL、3.在使用最短路径的算法时采用具有权值的有向图邻接矩阵存储方式

2.2 关键算法分析

第2页 北京邮电大学信息与通信工程学院

一．图的邻接矩阵构造函数：

1.关键算法： template Graph::Graph(f a[], int n, int e)

//带权值的图的构造函数 { int i, j, k, height;f s1, s2;vnum = n;arcnum = e;for(k = 0;k

//初始化顶点

for(k = 0;k

for(i = 0;i

{

arc[k][i] =-1;

if(i == k)arc[k][i] = 0;

//初始化权值的大小

}

visited[k] = 0;} cout

//初始化边

{

cout

cin >> s1 >> s2 >> height;

arc[convert(s1)][convert(s2)] = height;

arc[convert(s2)][convert(s1)] = arc[convert(s1)][convert(s2)];//采用无向图带权值的邻接矩阵

} cout

for(k = 0;k

for(i = 0;i

{

if(arc[k][i] ==-1)

cout

else cout

//打印邻接矩阵的格式

}

cout

} cout

第3页 北京邮电大学信息与通信工程学院

有构造可知，初始化时其时间复杂度：O(n2)

二．深度优先便利DFS:

1.关键算法

①从某顶点v出发并访问

②访问v的第一个未访问的邻接点w，访问w的第一个未访问的邻接点u，……

③若当前顶点的所有邻接点都被访问过，则回溯，从上一级顶点的下一个未访问过的顶点开始深度优先遍历

④直到所有和v路径相通的顶点都被访问到； 2.代码图解：

深度优先遍历示意图 3.代码详解：

template void Graph::DFS(int v){ cout

for(int j = 0;j

//连通图

if((visited[j] == 0)&&(arc[v][j] >= 1))DFS(j);//当存在回路时，则连通深一层遍历

} 4.时间复杂度

时间复杂度：O(n2)

空间复杂度：栈的深度O(n)

辅助空间O(n)

第4页 北京邮电大学信息与通信工程学院

三．广度遍历BFS 1.关键算法 ①访问顶点v ②依次访问v的所有未被访问的邻接点v1,v2,v3…

③分别从v1,v2,v3…出发依次访问它们未被访问的邻接点 ④反复①②③，直到所有和v路径相通的顶点都被访问到；

2.代码图解

3.代码详解

1.初始化队列Q

2.访问顶点v，visited[v]=1

3.while(队列非空)

3.1 v=队头元素出队

3.2 访问队头元素的所有未访问的邻接点 4.时间复杂度

时间复杂度：O(n2)

空间复杂度：辅助空间O(n)

四.最小生成树——普里姆算法

1,关键思路

一般情况下，假设n个顶点分成两个集合：U(包含已落在生成树上的结点)和V-U(尚未落在生成树上的顶点)，则在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。主数据结构：

邻接矩阵 辅助数据结构：

int

adjvex[MAXSIZE];// U集中的顶点序号

第5页 北京邮电大学信息与通信工程学院

int

lowcost[MAXSIZE];

// U(V-U)的最小权值边

2.代码图解

第6页 北京邮电大学信息与通信工程学院

第7页 北京邮电大学信息与通信工程学院

3;代码详解

template void Graph::Prim(){ for(int i = 0;i

//辅助数组存储所有到的V0边

{

adjvex[i] = 0;lowcost[i] = arc[0][i];

} lowcost[0] = 0;for(int j = 1;j

//循环n-1次

{

int k = Mininum(lowcost);

//求下一个顶点

cout “

lowcost[k] = 0;

//U=U+{Vk}

for(int j = 0;j

//设置辅助数组

{

if((lowcost[j]!= 0 && arc[k][j]

{

lowcost[j] = arc[k][j];

adjvex[j] = k;

}

}

第8页 北京邮电大学信息与通信工程学院

} } 4,时间复杂度：

时间复杂度O(n2)，适合稠密图

五.最小生成树----克鲁斯卡尔算法

1,关键思路

先构造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加上这条边，如此重复，直至加上n-1条边为止。2.代码图解：

3.代码详解

template void Graph::Kruskal()

//最小生成树—kruskal算法

{ cout

int k = 0, j = 0;

while(k

int m = vedgelist[j].fromv, n = vedgelist[j].endv;

int sn1 = vset[m];

int sn2 = vset[n];

//两个顶点分属

第9页 北京邮电大学信息与通信工程学院

不同的集合 if(sn1!= sn2)

{

cout ”

k++;

for(int i = 0;i

{

if(vset[i] == sn2)

vset[i] = sn1;

//集合sn2全部改成sn1

}

}

j++;} } 4.时间复杂度

时间复杂度O(nlogn)，适合稀疏图

六．最短路径——Dijkstra算法 1.关键代码

• 按路径长度递增的次序产生源点到其余各顶点的最短路径。• 1)设置集合s存储已求得的最短路径的顶点，• 2)初始状态：s=源点v • 3)叠代算法：

• 直接与v相连的最近顶点vi,加入s • 从v经过vi可以到达的顶点中最短的，加入s

……

2.代码图解

第10页 北京邮电大学信息与通信工程学院

3.代码详解

emplate void Graph::ShotPath(f x)

//关于最短路径的初始化 { int v=convert(x);

for(int i = 0;i

//初始化路径和点

{

s[i]=0;

disk[i] = arc[v][i];

if(disk[i]!= maxs)path[i] = v;

else path[i] =-1;} s[v] = 1;disk[v] = 0;path[v]=-1;for(int i = 0;i

//反复经过从该点到其他点的路径

{

if((v = FindMin())==-1)continue;

s[v] = 1;

for(int j = 0;j

if(!s[j] &&(disk[j]>arc[v][j] + disk[v]))

{

第11页 北京邮电大学信息与通信工程学院

disk[j] = arc[v][j] + disk[v];

path[j] = v;

} } Print();

//打印路径长度和遍历

} 4.时间复杂度

时间复杂度为：n^2

七．判断连通图算法

template bool Graph::judgegraph(){ DFS(convert(vertex[0]));if(count==vnum)

{

cout

return false;

} else {

cout

return true;

} }

时间复杂度：n^2

3.程序运行结果

1.测试主函数流程：

第12页 北京邮电大学信息与通信工程学院

函数流程图：

1.输入图的连接边并打印

构造下面所示图的邻接矩阵：

第13页 北京邮电大学信息与通信工程学院

2.判断图连通是否成功

3.BFS DFS PRIM算法的实现

第14页 北京邮电大学信息与通信工程学院

4.克鲁斯卡尔算法实现过程

4.有向图邻接矩阵的构建

第15页 北京邮电大学信息与通信工程学院

插入V0位置后打印距离并开始回溯

总结

1.调试时出现的问题及解决的方法

问题一：prim算法中

解决方法：调整循环条件，修正函数体注意有无Next的区别

第16页 北京邮电大学信息与通信工程学院

问题二：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)判断图为非连通图后，提示输入错误，重新输入图元素

第17页

数据结构上机实验图

数据结构上机实验六实验内容:图的基本操作实验要求:1) 图的遍历与基本操作要作为函数被调用.2) 把自己使用的图结构明确的表达出来.3) 基本上实现每个实验题目的要求.分组要......

北化航天工业学院~数据结构~实验5图

实验五：图的应用班级学号姓名一、实验预备知识1 复习C++中的全局变量的概念。2 复习图的邻接矩阵和邻接表两种存储方式。3 复习图的两种遍历方法和求图的最小生成树的方法。......

数据结构实验指导书

目 录 实验一线性表、栈和队列的基本操作............................................................1 实验二二叉树的基本操作............................................

数据结构实验指导书

目 录 实验规则················································2 实验环境····················......

《数据结构》实验指导书

《数据结构》实验(训)指导书电气与信息工程学院实验中心 前 言《数据结构》是计算机相关专业的一门核心基础课程，也是很多高校研究生入学考试专业课必考课程之一。它主要介绍......