实验三:图的度(出度)统计和最小生成树 一、实验目的 1. 熟练掌握图的两种存储方式：邻接矩阵和邻接表。 2. 通过领接表统计图中顶点度为n的顶点数量。 3. 通过邻接矩阵实现最小生成树的prime算法。 二、实验内容 1.问题描述 图1 图2 （1）对图进行定义，采用邻接表的存储方式对图进行存储。统计出图度数或出度（有向图）为n的顶点个数。 （2）对图进行定义，采用邻接矩阵的存储方式对图进行存储。用prim算法求出图的最小生成树。

三、实验步骤

1. 定义图1和图2，采用邻接表的方式存储图。

2. 统计图中度数或出度为n的顶点个数，具体步骤如下：

（1）根据邻接表的存储方式，遍历每个顶点的邻接链表。

（2）统计每个顶点的度数或出度，若为n，则计数器加1。

（3）输出计数器的值，即为度数或出度为n的顶点个数。

3. 定义图1和图2，采用邻接矩阵的方式存储图。

4. 使用prim算法求出图的最小生成树，具体步骤如下：

（1）初始化一个空的生成树T，将一个任意顶点v加入T中。

（2）找出与T中顶点相邻的所有顶点中权值最小的边，将该边连接的顶点加入T中。

（3）重复上述步骤，直到T包含所有顶点。

（4）输出T中所有边的权值和，即为图的最小生成树的权值和。

四、实验结果

1. 图1的邻接表：

顶点 邻接顶点

A B->C

B A->C->D

C A->B->D

D B->C

图1的度数为2的顶点个数为2。

2. 图2的邻接表：

顶点 邻接顶点

A B->D

B A->C->D

C B->D

D A->B->C

图2的度数为2的顶点个数为0。

3. 图1的邻接矩阵：

0 1 1 0

1 0 1 1

1 1 0 1

0 1 1 0

图1的最小生成树的权值和为3。

4. 图2的邻接矩阵：

0 1 0 1

1 0 1 1

0 1 0 1

1 1 1 0

图2的最小生成树的权值和为3。

五、实验总结

本次实验通过对图的邻接矩阵和邻接表两种存储方式的使用，学习了如何统计图中度数或出度为n的顶点个数以及如何使用prim算法求解最小生成树。实践中需要注意细节，如顶点的编号、边的权值等。