离散数学实验指导
别妄想泡我
855次浏览
2021年01月30日 01:02
最佳经验
本文由作者推荐
温馨提示语-学习英文
实验
1
关系的闭包运算
1
、实验类型：
设计性
2
、实验目的
通过算法设计并编程实现求给定关系的各种闭包运算，
加深学生对闭包运算
的概念的理解。
3
、实验内容
给定关系
R
，求
R
的自反闭包、对称闭包及
R
的传递闭包。
4
、实验原理
若关系
R
的关系矩阵为
M
，而自反闭包为
A
（即< br>r
（
R
）
=A
）
，对称闭包为
B
（ 即
S
（
R
）
=B
）
，则
A=M
∨
I B=M
∨
M
T
其中，
I
为恒等矩 阵，
M
T
为
M
的转置矩
阵。
5
、实验仪器设备或软件环境及工具
运行
Windows
或
Linux
操作系统的
PC
机，具有
gcc(Linux)、
Turboc
、
Vc(Windows)
等
C
语言的 编译环境。
6
、实验要求
复习关系闭包的定义，
实验由 一人一组完成。
所编程序能够通过编译，
并能
够实现求出给定关系的闭包的运算。
7
、实验报告要求
（
1
）写出实验过程中遇到的问题及其解决过程。
（
2< br>）写出类
c
的算法并编写一个程序求出给定关系的闭包。
（
3
）写出实验结束时的程序清单及运行结果及实验总结。
实验
2
最小生成树的
Kruskal
算法
1
、实验类型：
设计性
2
、实验目的
通过算法设计并编程实现求出给定无向连通加权图的一棵最小生成树，
加深
学生对求最小生成树 的
Kruskal
算法的理解。
3
、实验内容
给定无向连通加权图，编程设计求出其一棵最小生成树。
4
、实验原理
设所给定无向连通加权图具有
n
个结点，< br>m
条边，首先，将各条边的权按从
小到大的顺序排序。
然后依次将这些边按所给 图的结构放到生成树中去。
如果在
放置某一条边时，使得生成树形成回路，则删除这条边。这样 ，直至生成树具有
n-1
条边时，我们所得到的就是一棵最小生成树。
5
、实验仪器设备或软件环境及工具
运行
Windows
或
Linux
操作系统的
PC
机，具有
gcc(Linux)、
Turboc
、
Vc
、
CFree(Windows)
等
C
语言的编译环境。
6
、实验要求
复习树 及最小生成树的定义，
实验由一人一组完成。
所设计程序能够通过编
译，并能够求出给 定无向连通加权图的一棵最小生成树。
7
、实验步骤及注意事项
（
1
）
边依小到大顺序得
l
1
，
l
2
，…，
l
m
。
（
2
）
置初值：
S
，0
i
，
1
j
。
（
3
）
若
i=n-1
，则转（
6
）
。
（
4
）
若生成树边集
S
并入一条新的边
l
j
之后产生的回路，则
j+1
j
，并
转（4
）
。
（
5
）
否则，
i +1
i
；
l
j
S
（
i
）
；
j+1
j
，转（
3
）
。
（
6
）
输出最小生成树
S
。
（
7
）
结束。
8
、实验报告要求
（
1
）写出实验过程中遇到的问题及其解决过程。
（
2< br>）写出类
c
的算法，并写一个程序求出给定无向连通加权图的一棵最小生成
树。
（
3
）写出实验结束时的程序清单及运行结果及实验总结。
参考例子：
1
闭包：
#include
int main()
{
int i,j,k,n;
static int str[122],zifan[122],chuandi[122],duich[122];
printf(
scanf(
printf(
for(i=0;i
{
scanf(
}
printf(
for(j=0;j
{
printf(
if((j+1)%n==0)
printf(
}
for(j=0;j
{
zifan[j]=str[j];
chuandi[j]=str[j];
duich[j]=str[j];
}
printf(
for(i=0;i
{
if(i%(n+1)==0)
zifan[i]=zifan[i]||1;
printf(
if((i+1)%n==0)
printf(
}
printf(
for(i=0,j=0;i
{
if(i>j*(n+1)&&i<(j+1)*n)
{
duich[i]=duich[(i-j*(n+1))*(n-1)+i]||duich[i];
duich[(i-j* (n+1))*(n-1)+i]=duich[(i-j*(n+1))*(n-1)+i]||duich[ i];
}
else if(i>=(j+1)*n)
j++;
}
for(i=0;i
{
printf(
if((i+1)%n==0)
printf(
}
printf(
for(i=0;i
for(j=0;j
if(chuandi[j*n+i])
{for(k=0;k
chuandi[j*n+k]=chuandi[j*n+k]||chuandi[i*n+k];
}
for(i=0;i
{
printf(
if((i+1)%n==0)
printf(
}
return 0;
}
2
、
warshall
算法：
#include
#include
#include
#define N 3
#define TRUE 0
int get_matrix(int a[N][N])
{
int i = 0,j = 0;
for (i = 0;i < N;i++) {
for (j = 0;j < N;j++) {
scanf(
if (a[i][j] != 0 && a[i][j] != 1) {
printf(
exit(2);
}
}
}
return TRUE;
}
int output_matrix(int a[N][N])
{
int i = 0,j = 0;
for (i = 0;i < N;i++) {
for (j = 0;j < N;j++) {
printf(
}
putchar('n');
}
return TRUE;
}
int warshall(int a[N][N])
{
int col = 0;
int line = 0;
int temp = 0;
for (col = 0;col < N;col++) {
for (line = 0;line < N;line++) {
if (a[line][col] != 0) {
for (temp = 0;temp < N;temp++) {
a[line][temp] = a[line][temp] | a[col][temp];
}
}
}
}
return TRUE;
}
int main(void)
{
int a[N][N] = {0};
printf(
if (get_matrix(a)) {
printf(
exit(1);
}
warshall(a);
output_matrix(a);
return 0;
}
3
、
Kruskal
算法
1:
#define MAXE 11
#define MAXV 10
#include
typedef struct
{
int vex1;
//
边的起始顶点
int vex2;
//
边的终止顶点
int weight;
//
边的权值
} Edge;
void kruskal(Edge E[],int n,int e)
{
int i,j,m1,m2,sn1,sn2,k;
int vset[MAXV];
for (i=1; i<=n; i++)
//
初始化辅助数组
vset[i]=i;
k=1;
//
表示当前构造最小生成树的第
k
条边，初值为
1
j=0;
//E
中边的下标，初值为
0
while (k < e)
//
生成的边数小于
e
时继续循环
{
m1=E[j].vex1;
m2=E[j].vex2;//
取一条边的两个邻接点
sn1=vset[m1];
sn2=vset[m2];
//
分别得到两个顶点所属的集合编号
if (sn1!=sn2)
//
两顶点分属于不同的集合，该边是最小生成树的一条边
{