离散数学实验指导书(2011-5-16)(7)

实验十三 最小生成树的Kruskal算法

1、实验类型：设计性 2、实验目的

通过算法设计并编程实现求出给定无向连通加权图的一棵最小生成树，加深学生对求最小生成树的Kruskal算法的理解。 3、实验内容

给定无向连通加权图，编程设计求出其一棵最小生成树。 4、实验原理

设所给定无向连通加权图具有n个结点，m条边，首先，将各条边的权按从小到大的顺序排序。然后依次将这些边按所给图的结构放到生成树中去。如果在放置某一条边时，使得生成树形成回路，则删除这条边。这样，直至生成树具有n-1条边时，我们所得到的就是一棵最小生成树。 5、实验仪器设备或软件环境及工具

运行Windows 或Linux操作系统的PC机，具有gcc(Linux)、Turboc、Vc(Windows)等C语言的编译环境。 6、实验要求

复习树及最小生成树的定义，实验由一人一组完成。所设计程序能够通过编译，并能够求出给定无向连通加权图的一棵最小生成树。 7、实验步骤及注意事项

（1） 边依小到大顺序得l1，l2，?，lm。 （2） 置初值：??S，0?i，1?j。 （3） 若i=n-1，则转（6）。

（4） 若生成树边集S并入一条新的边lj之后产生的回路，则j+1?j，并转（4）。 （5） 否则，i+1?i；lj?S（i）；j+1?j，转（3）。 （6） 输出最小生成树S。 （7） 结束。 8、实验报告要求

（1）写出实验过程中遇到的问题及其解决过程。

（2）写出类c的算法，并写一个程序求出给定无向连通加权图的一棵最小生成树。 （3）写出实验结束时的程序清单及运行结果及实验总结。

20

实验十四 判别图的连通性

1、实验类型：设计性 2、实验目的

通过算法设计并编程实现，使学生掌握利用计算机语言判别图的连通性的基本方法。 3、实验内容

给定n个结点的有向图的邻接矩阵，可判断该图是否为强连通的，单向连通的，或弱连通的。 4、实验原理

对于给定的邻接矩阵A，我们可以用前面给出的可达矩阵Warshall算法求出A所表示的图的可达矩阵P。对于可达矩阵P来说，如果P的所有元素均为1，则所给的有向图是强连通的；对于P的所有元素（除主对角线元素外）Pij来说，均有：Pij+Pji>0，则所给有向图是单向连通的。当所给有向图既不是强连通的，又不是单向连通的时候，我们改造邻接矩阵为：对于矩阵A中所有的元素（除主对角线的元素外）aij，若aij=1或aji=1，则1?aij且1?aji。对于这样改造之后所得到的新的矩阵A’（A’相当于原有向图忽略方向之后所得到的无向图的邻接矩阵），再用前面所述的方法进行判断，当P’的所有元素（除主对角线的元素外）均为1时，原有向图是弱连通图；否则，原有向图是不连通的。

5、实验仪器设备或软件环境及工具

运行Windows 或Linux操作系统的PC机，具有gcc(Linux)、Turboc、Vc(Windows)等C语言的编译环境。 6、实验要求

复习图的强连通、单向连通和弱连通的定义，实验由几人一组完成。所编程序能够通过编译，并能够对给定n个结点的有向图的邻接矩阵，判断该图是否为强连通的，单向连通的，或弱连通的。 7、实验步骤及注意事项 （1）输入邻接矩阵A（n，n）。 （2）A（n，n）?P（n，n）。

（3）调用求可达矩阵子程序求出可达矩阵P。 （4）调用强连通或单向连通子程序。

（5）若为强连通或单向连通的，则输出其标志，转结束；否则转（6）。 （6）改造A阵为 A’，且A’ ?P（n,n）。

21

（7）调用求可达矩阵子程序。

（8）调用判断连通或单向连通子程序。

（9）若为强连通的，则输出原有向图是弱连通的；否则输出原有向图是非连通的。 （10）结束。 8、实验报告要求

（1）写出实验过程中遇到的问题及其解决过程。

（2）写出类c的算法，并编写一个程序求出给定n个结点的有向图的邻接矩阵，据此判断该图是否为强连通的，单向连通的，或弱连通的。 （3）写出实验结束时的程序清单及运行结果及实验总结。

22

实验十五 求无向图中顶点的度数

1、实验类型：设计性 2、实验目的

通过算法设计并编程实现求出给定无向图顶点的度数，加深学生对关联及度的定义的理解。 3、实验内容

给定无向图的各边所关联的顶点对，编程设计求出每个顶点的度数。 4、实验原理

设无向图G=, ek=(vi,vj)?E, 称vi , vj为ek 的端点, ek与vi (vj)关联。若vi= vj，则称ek 为环loop. 无边关联的顶点称作孤立点. 若vi ? vj, 则称ek 与vi (vj)的关联次数为1; 若vi = vj, 则称ek 与vi 的关联次数为2; 若vi不是边e的端点, 则称e与vi 的关联次数为0。设G=为无向图, v?V,v的度数(度) d(v)是v作为边的端点次数之和。

5、实验仪器设备或软件环境及工具

运行Windows 或Linux操作系统的PC机，具有gcc(Linux)、Turboc、Vc(Windows)等C语言的编译环境。 6、实验要求

复习无向图中关联和度的定义，实验由一人一组完成。所设计程序能够通过编译；并能够根据给定无向图的各边所关联的顶点对，编程设计求出每个顶点的度数。 8、实验报告要求

（1）写出实验过程中遇到的问题及其解决过程。

（2）写出类c的算法，并写一个程序求出给定无向图的各边所关联的顶点对的每个顶点的度数。

（3）写出实验结束时的程序清单及运行结果及实验总结。

23

实验十六 求有向图中顶点的度数

1、实验类型：设计性 2、实验目的

通过算法设计并编程实现求出给定有向图顶点的度数，加深学生对关联及出度和入度的定义的理解。 3、实验内容

给定有向图的各边所关联的有序顶点对，编程设计求出每个顶点的入度和出度。 4、实验原理

设有向图D=, 其中V??称为顶点集, 其元素称为顶点或结点; E是V?V的多重子集, 称为边集, 其元素称为有向边，简称边。对有向图. 设ek =? vi, vj ?是有向图的一条边, 又称vi是ek的始点, vj是ek的终点, vi邻接到vj, vj邻接于vi。

v的入度d?(v)是v作为边的终点次数之和；v的出度d+(v)是v作为边的始点次数之和；v的度数(度) d(v)是v作为边的端点次数之和。其中d(v)= d+(v)+ d?(v) 5、实验仪器设备或软件环境及工具

运行Windows 或Linux操作系统的PC机，具有gcc(Linux)、Turboc、Vc(Windows)等C语言的编译环境。 6、实验要求

复习有向图中关联、邻接和入度及出度的定义，实验由一人一组完成。所设计程序能够通过编译；并能够根据给定无向图的各边所关联的有序顶点对，编程设计求出每个顶点的入度和出度。 8、实验报告要求

（1）写出实验过程中遇到的问题及其解决过程。

（2）写出类c的算法，并写一个程序求出给定有向图的各边所关联的顶点对的每个顶点的入度和出度。

（3）写出实验结束时的程序清单及运行结果及实验总结。

24