数据结构 实验一 图

实验名称： 实验二——图

**** ***

班    级： 2014211117

班内序号： 20

学    号： **********

日    期： 2015年12月05日

1．实验要求

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

图的基本功能：

1、图的建立

2、图的销毁

3、深度优先遍历图

4、广度优先遍历图

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

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

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

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

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

2. 程序分析

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

2.1 存储结构    

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

 带权值的无向图邻接矩阵

 带权值的有向图邻接矩阵

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

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

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

[备注]：

1.在使用打印元素、BFS、DFS 采用无权值的无向图邻接矩阵存储方式

2.在使用PRIM、KRUSKAL、

3.在使用最短路径的算法时采用具有权值的有向图邻接矩阵存储方式

2.2 关键算法分析

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

1.关键算法：

template

G带权值的图的构造函数

{

  //初始化顶点

   初始化权值的大小

 初始化边

  请输入线性链接节点:";

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

 所得邻接矩阵为：" << endl; 

    ∞" << " ";

    打印邻接矩阵的格式

2.算法的时间复杂度

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

二．深度优先便利DFS:

1.关键算法

①从某顶点v出发并访问

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

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

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

④直到所有和v路径相通的顶点都被访问到；

2.代码图解：

深度优先遍历示意图

3.代码详解：

template

void Graph::DFS(int v)

{

 连通图 

 当存在回路时，则连通深一层遍历 

}

4.时间复杂度 

时间复杂度：O(n2)

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

辅助空间O(n)

三．广度遍历BFS

1.关键算法

①访问顶点v

②依次访问v的所有未被访问的邻接点v1,v2,v3…

③分别从v1,v2,v3…出发依次访问它们未被访问的邻接点

④反复①②③ ，直到所有和v路径相通的顶点都被访问到；

2.代码图解

3.代码详解

1.初始化队列Q

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

  3. while(队列非空)

 队头元素出队

 访问队头元素的所有未访问的邻接点

4.时间复杂度

  时间复杂度：O(n2)

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

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

1,关键思路

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

主数据结构：  邻接矩阵

辅助数据结构：

   i集中的顶点序号

  int    lowcost[MAXSIZE];    // U(V-U)的最小权值边

2.代码图解

3;代码详解

template

void Graph::Prim()

{

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

 循环n-1次

  求下一个顶点

  设置辅助数组

}

4,时间复杂度：

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

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

1,关键思路

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

2.代码图解：

3.代码详解

template

v最小生成树—kruskal算法 

{

 算法结果为："< 

  两个顶点分属不同的集合

     集合sn2全部改成sn1

}

4.时间复杂度

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

六．最短路径——Dijkstra算法

1.关键代码

•按路径长度递增的次序产生源点到其余各顶点的最短路径。

•1)设置集合s存储已求得的最短路径的顶点，

•2)初始状态：s=源点v

•3)叠代算法：

•直接与v相连的最近顶点vi,加入s

•从v经过vi可以到达的顶点中最短的，加入s

2.代码图解

3.代码详解

emplate

v关于最短路径的初始化

{

 初始化路径和点

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

 打印路径长度和遍历 

}

4.时间复杂度

时间复杂度为：n^2

七．判断连通图算法

template

bool Graph::judgegraph()

{

 该图为连通图！*******输入成功！"< 该图不为连通图！*******请重新输入"< }

时间复杂度：n^2

3.  程序运行结果

 1. 测试主函数流程：

函数流程图：

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

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

2.判断图连通是否成功

3.BFS DFS PRIM算法的实现

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