北京邮电大学数据结构实验第二次实验图

数据结构实验报告

实验名称： 实验2——图 学生姓名： 班 级： 班内序号： 学 号： 日 期： 1.要求

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

1、图的建立 2、图的销毁 3、深度优先遍历图 4、广度优先遍历图

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

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

2.程序分析

3.算法分析

3.1深度优先遍历

（1）设置一个数组记录节电状态： bool visited[MAXSIZE]={false}; （2）从节点v开始访问，设置该节点的visited[v]=true; （3）寻找节点v的第一个未访问的邻接点:

for （int j=0;j

if （arc[v][j]）==1&&!visited[j]) 3.2广度优先遍历

（1）初始化队列Q

bool visited[MAXSIZE]={false};

（2）访问顶点v，visited[v]=true （3）While(队列非空) V=队头元素出队；

访问队头元素的所有未访问节点。 for （int j=0;j

if （arc[v][j]）==1&&!visited[j]) 3.3普里姆算法

（1）初始化辅助数据结构

（2）选择辅助数组lowcost中最小值，即U->V-U的最小权值边集合中的最小权值边。 （3）迭代的更新adjvex和lowcost。即U->V-U的边集更新一次。寻找每一个邻接点到U集合的最小值。重复（2）（3），直到U为空。即最小生成树。 3.4克鲁斯卡尔算法

（1）获取EdgeList，并对其排序。

（2）构建辅助数据结构，判断新加入的边是否构成回路。

（3）选择一条最小边，该边两个顶点若分属不同的集合i和j，则在vest中寻找所有编号为j的顶点，将其更新为i，否则选择下一条边。 （4）复杂度为o（n2） 3.5Dijkstra

(1)源点直接到达顶点的所有路径，选出最短一条

(2)以此路径为出发路径，找出到达其他顶点的路径，并选出最短一条路径。 重复执行（2）。直到所有顶点。 4.

本文来源：https://www.bwwdw.com/article/yp5d.html