数据结构上机实验图_数据结构上机实验答案

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

数据结构上机实验六

实验内容:图的基本操作

实验要求:

1)图的遍历与基本操作要作为函数被调用.2)把自己使用的图结构明确的表达出来.3)基本上实现每个实验题目的要求.分组要求：可单独完成，也可两人一组。

实验目的:

1)熟悉C/C++基本编程,培养动手能力.2)通过实验,加深对图的理解.评分标准：

1)只完成第一和第二题，根据情况得4，5分；

2）完成前3题，根据情况得5至7分；

3）在2）基础上，选做四）中题目，根据情况得8至10分。

题目:

一)建立一个无向图+遍历+插入

(1)以数组表示法作为存储结构，从键盘依次输入顶点数、弧数与各弧信息建立一个无向图；

(2)对（1）中生成的无向图进行广度优先遍历并打印结果；

(3)向（1）中生成的无向图插入一条新弧并打印结果；

二)建立一个有向图+遍历+插入+删除

(1)以邻接表作为图的存储结构，从键盘输入图的顶点与弧的信息建立一个有向图；

(2)对（1）中生成的有向图进行深度优先遍历并打印结果；

(3)在（1）中生成的有向图中，分别插入与删除一条弧并打印其结果；

(4)在（1）中生成的有向图中，分别插入与删除一个顶点并打印结果；

(5)在（1）中生成的有向图中,各顶点的入度与出度并打印结果；

三）基本应用题

（1）编写算法，判断图中指定的两个顶点是否连通。

（2）编写算法，判断图的连通性。如果不连通，求连通分量的个数

（3）编写算法，判断图中任意两个顶点的连通性

（4）编写算法，判断图中是否存在回路。

（5）实现图的广度优先搜索算法。

四）高级应用题

（1）实现Prim算法

（2）实现Kruskal算法

（3）实现迪杰斯特拉算法

（4）实现拓扑排序算法

（5）实现关键路径算法