《离散数学》实验报告HEBUT-Toy模板网

这篇具有很好参考价值的文章主要介绍了《离散数学》实验报告HEBUT。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

《离散数学》实验指导书

一、实验目的

《离散数学》是现代数学的一个重要分支，是计算机科学与技术专业的基础理论课，也是该专业的核心课程和主干课程。“离散数学”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。该课程一方面为后继课程如数据结构、编绎原理、操作系统、数据库原理、人工智能和形式语言与自动机等提供必要的理论基础；同时，更为重要的是培养学生的抽象思维能力和逻辑推理能力，为今后的学习和工作打好基础。无论从计算机学科发展的过去、现在和未来看，《离散数学》都是计算机科学与技术专业不可缺少的重要组成部分。这门课程有着其它课程不可替代的地位和作用，是一门承前启后的课程。

根据《离散数学》课程本身的理论性较强的特性，为了帮助学生更好地学习本课程，理解和掌握所学基本概念和方法，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，设置实践环节十分重要。通过实验实践内容的训练，突出逻辑性思维训练的特征, 目的是学习离散数学中的基本算法和方法，掌握数理逻辑、关系和图论中的基本算法，提高学生学习的兴趣及实际动手的能力。通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所学知识，培养分析、解决实际问题的能力。

二、实验要求

掌握真值表技术，熟悉联结词合取、析取、条件和双条件的概念。熟悉Warshall算法，掌握求关系的自反闭包、对称闭包和传递闭包的方法。熟悉邻接矩阵和两结点间长度为m的路的数目的关系。熟悉最优树的构造算法，掌握最优树的构造过程。实验前作好准备，分析问题并确定算法，设计代码。做实验过程中认真分析和调试程序，记录并分析实验结果。实验后完成实验报告，实验报告包括实验目的、实验内容、源程序、运行结果及分析。可以使用C、VC或MATLAB完成实验。实验题目包括真值计算、关系闭包计算、计算两结点间长度为m的路的数目、最优树的构造四个实验，每个实验要求2个学时完成。

三、实验设备及环境

PC机一台，软件C、VC或MATLAB

四、实验内容

实验一：真值计算

1.实验目的

熟悉五个常用联结词合取、析取、条件和双条件的概念，掌握真值表技术。

2.实验内容与要求

定义1 设P表示一个命题，由命题联结词┐和命题P连接成┐P，称┐P为P的否定式复合命题， ┐P读“非P”。称┐为否定联结词。┐P是真，当且仅当P为假；┐P是假，当且仅当P为真。

定义2 设P和Q为两个命题，由命题联结词∧将P和Q连接成P∧Q，称P∧Q为命题P和Q的合取式复合命题，P∧Q读做“P与Q”，或“P且Q”。称∧为合取联结词。当且仅当P和Q的真值同为真，命题P∧Q的真值才为真；否则，P∧Q的真值为假。

定义3 设P和Q为两个命题，由命题联结词∨把P和Q连接成P∨Q，称P∨Q为命题P和Q的析取式复合命题，P∨Q读做“P或Q”。称∨为析取联结词。当且仅当P和Q的真值同为假，P∨Q的真值为假；否则，P∨Q的真值为真。

定义4 设P和Q为两个命题，由命题联结词→把P和Q连接成P→Q，称P→Q为命题P和Q的条件式复合命题，简称条件命题。P→Q读做“P条件Q”或者“若P则Q”。称→为条件联结词。当P的真值为真而Q的真值为假时，命题P→Q的真值为假；否则，P→Q的真值为真。

定义5 令P、Q是两个命题，由命题联结词 $\longleftrightarrow$ 把P和Q连接成P $\longleftrightarrow$ Q，称P $\longleftrightarrow$ Q为命题P和Q的双条件式复合命题，简称双条件命题，P $\longleftrightarrow$ Q读做“P当且仅当Q”，或“P等价Q”。称«为双条件联结词。当P和Q的真值相同时，P $\longleftrightarrow$ Q的真值为真；否则，P $\longleftrightarrow$ Q的真值为假。

本实验要求从键盘输入两个命题P和Q的真值，求它们的合取、析取、条件和双条件的真值。用C语言或MATLAB实现。

3、实验报告要求

列出实验目的、实验内容、实验步骤、源程序和实验结果。

4.实验步骤

1.熟悉定义1-5。

2.确定程序的编写逻辑，进行手推演算。

3.进行程序编写。

4.验证程序的正确性。

5.源程序

#include<iostream>
using namespace std;
int main(){
    bool p,q;
    cout<<"Please enter the Truth Value of P: ";
    cin>>p;
    cout<<"Please enter the Truth Value of Q: ";
    cin>>q;
    //合取
    if(p && q)
    {
        cout<<"p ∧ q = 1"<<endl;
    }
    else
    {
         cout<<"p ∧ q = 0"<<endl;
    }
    //析取
    if(p || q)
    {
        cout<<"p ∨ q = 1"<<endl;  
    }
    else
    {
       cout<<"p ∨ q = 0"<<endl; 
    }
    //条件
    if((p && q) || !p)
    {
        cout<<"p → q = 1"<<endl;
    }
    else
    {
        cout<<"p → q = 0"<<endl;
    }
    //双条件
    if(p == q)
    {
        cout<<"p ←→ q = 1"<<endl;
    }
    else
    {
        cout<<"p ←→ q = 0"<<endl;
    }
}

6.实验结果

示例一：
《离散数学》实验报告HEBUT

示例二：
《离散数学》实验报告HEBUT

示例三：
《离散数学》实验报告HEBUT

示例四：
《离散数学》实验报告HEBUT

实验二：真值表

1.实验目的

熟悉五个真值表，掌握真值表技术。

2.实验内容与要求

定义1 设命题变元P1、P2、P3、…、Pn是出现在公式G中的所有命题变元，指定P1、P2、P3、…、Pn 的一组真值，则这组真值称为G的一个解释或指派，常记为Ｉ。

定义2 真值表：公式G在其所有可能的解释下所取真值的表。

本实验要求从键盘输入一个命题公式列出其真值表。用C语言或MATLAB实现。

3.实验报告要求

列出实验目的、实验内容、实验步骤、源程序和实验结果。

4. 实验步骤

1.熟悉真值表的制图方法。

2.分析程序大致流程逻辑。

3.分块实现程序功能。

4.程序调试。

5.程序验证。

5. 源程序

#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<algorithm>

using namespace std;

//提取变量     
void extractVariables(string str, string& var, int& count)
{
    // 26个字母
	int letter[26] = {0};
	for (int i = 0; i != str.size(); i++){
        // 字母字符
		if (isalpha(str[i])){
			letter[str[i] - 'a'] += 1;
        }
    }
	for (int i = 0; i < 26; i++){
		if (letter[i]){
			// 提取变量
			var.push_back(i + 97);
			count++;
		}
    }
}
//非
void notLogic(string& str)
{
	for (int i = 0; i != str.size(); i++){
		if (i + 1 < str.size() && str[i] == '!' && str[i + 1] == '0'){
			str.replace(i, 2 , "1");
		}else if ( i + 1 < str.size() && str[i] == '!' && str[i + 1] == '1'){
			str.replace(i, 2, "0");
        }
	}
} 
//合取          
void conjunctiveLogic(string& str)
{
	for (int i = 0;i != str.size();i++){
		if (str[i] == '1' && i + 2 < str.size() && str[i + 2] == '1' && str[i + 1] == '&'){
			str.replace(i, 3 , "1");
		}else if (i + 2 < str.size() && str[i + 1] == '&' && ((str[i] == '1' && str[i + 2] == '0')
			|| (str[i] == '0' && str[i + 2] == '1') || (str[i] == '0' && str[i + 2] == '0'))){
			str.replace(i, 3, "0");
        }
	}
}
//析取       
void disjunctiveLogic(string& str)
{
	for (int i = 0; i != str.size(); i++){
		if (str[i] == '0' && i + 2 < str.size() && str[i + 2] == '0' && str[i + 1] == '|'){
			str.replace(i, 3, "0");
		}else if (i + 2 < str.size() && str[i + 1] == '|' && ((str[i] == '1' && str[i + 2] == '0')
			|| (str[i] == '0' && str[i + 2] == '1') || (str[i] == '1' && str[i + 2] == '1'))){
			str.replace(i, 3, "1");
        }
	}
}  
//条件       
void implicationLogic(string& str)
{
	for (int i = 0; i != str.size(); i++){
		if (str[i + 1] == '>' && str[i] == '1' && str[i + 2] == '0'){
			str.replace(i, 3, "0");
		}else if (str[i + 1] == '>' && ((str[i] == '1' && str[i + 2] == '1')
			|| str[i] == '0' && (str[i + 2] == '1' || str[i + 2] == '0'))){
			str.replace(i, 3, "1");
        }
	}
}
//双条件          
void doubleImplicationLogic(string& str)
{
	for (int i = 0; i != str.size(); i++){
		if (str[i + 1] == '-' && ((str[i] == '1' && str[i + 2] == '1') || (str[i] == '0' && str[i + 2] == '0'))){
			str.replace(i, 3, "1");
        }else if (str[i + 1] == '-' && ((str[i] == '1' && str[i + 2] == '0') || (str[i] == '0' && str[i + 2] == '1'))){
			str.replace(i, 3, "0");
        }
	}
}   
//给变量赋值   
void assignValuesToVariables(string& str, int val[])
{
	for (int i = 0; i != str.size(); i++){
		if (isalpha(str[i])){
			str.replace(i, 1, val[str[i] - 'a'] ? "1" : "0");
        }
	}
}
//去除无用的括号,ps:（括号内只有一个变量的情况）   
void removeBrackets(string& str)
{
	for (int i = 0; i != str.size(); i++){
		if (str[i] == '(' && i + 2 < str.size() && str[i + 2] == ')'){
			string s;
			s += str[i + 1];
			str.replace(i, 3, s);
		}
	}
}      
//进行所有逻辑计算并输出
void process(string var, string str, int count)
{
    string tmp = str;
    int val[30] = {0};
	for (int i = 0; i < var.size(); i++){
		cout << var[i] << "\t";
    }
	cout << str << endl;
	for (int i = 0; i != pow(2, count); i++){
		for (int j = 0; j != count; ++j){
			val[var[j] - 'a'] = (1 & (i >> (count - 1 - j)));    //位运算赋值
        }
		for (int j = 0; j != count; ++j){
			cout << val[var[j] - 'a'] << "\t";
        }
		assignValuesToVariables(str, val);
		while (str.size() != 1){
			removeBrackets(str);
			notLogic(str);
			conjunctiveLogic(str);
			disjunctiveLogic(str);
			implicationLogic(str);
			doubleImplicationLogic(str);
		}
		cout << str << endl;
		str = tmp;
	}
}
int main()
{
	cout << "请输入命题公式(做如下规定:！为非 &为合取 |为析取 >为条件 -为双条件)" << endl;
    //命题公式字符串
	string expression;
	//变量字符串序列
	string varSeq;
	//变量个数
	int varCount = 0;
	cin >> expression;
	//全部变为小写
    for(int i = 0; i < expression.size(); i++){
        expression[i] = tolower(expression[i]);
    }
	extractVariables(expression, varSeq, varCount);
	process(varSeq, expression, varCount);
    return 0;
}

6.实验结果

示例一：
《离散数学》实验报告HEBUT
示例二：

实验三：关系性质判断

1.实验目的

熟悉关系的性质，掌握求判断关系性质的方法。

2.实验内容与要求

定义1 设R是集合X上的二元关系，对任意的x∈X，都满足<x,x>∈R，则R是自反的。

定义2 设R是集合X上的二元关系，对任意的x∈X，都满足<x,x> $\notin$ R，则R是反自反的。

定义3 设R是集合X上的二元关系，对任意的x,y∈X，满足<x,y>∈R $\Longrightarrow$ <y,x>∈R，则R是对称的。

定义4 设R是集合X上的二元关系，对任意的x,y∈X，满足<x,y>∈R∧<y,x>∈R $\Longrightarrow$ x＝y,则R是反对称的。

定义5 设R是集合X上的二元关系，对任意的x,y,z∈X，满足<x,y>∈R∧<y,z>∈R $\Longrightarrow$ <x,z>∈R,则R是传递的。

本实验要求从键盘输入一个关系的关系矩阵，判断该关系是否是自反的、对称的、传递的、反自反的、反对称的。用C语言或MATLAB实现。

3.实验步骤

1.熟悉关系的性质：自反的、对称的、传递的、反自反的、反对称的。

2.熟悉针对关系矩阵如何判断关系的性质。

自反：主对角线元素全为1
反自反：主对角线元素全为0
对称：关于主对角线对称
反对称：关于主对角线0与对称
传递：传递闭包与原关系矩阵相等

3.程序实现

4.程序调试和验证

4.源程序

#include<iostream>
using namespace std;
int main(){
    cout<<"Please enter the order of the square matrix: ";
    int order;
    cin>>order;
    cout<<"Please enter the square matrix:"<<endl;
    int square [order][order];
    for(int i = 0; i < order; i ++){
        for(int j = 0; j < order; j ++){
            cin >> square[i][j];
        }
    }
    cout<<endl;
    //自反和反自反
    int coin1 = 0;
    for(int i = 0; i < order ; i ++){
        if(square[i][i] == 1){
            coin1 ++;
        }
    }
    if(coin1 == order){
        cout<<"R是自反的"<<endl;
    }
    if(coin1 == 0){
        cout<<"R是反自反的"<<endl;
    }
    //对称和反对称
    int coin2 = 0;
    int coin3 = 0;
    for(int i = 0; i < order ; i ++){
        for(int j = 0; j < order ; j ++){
            if(square[i][j] != square[j][i]){
                coin2 ++;
            }else{
                coin3 ++;
            }
        }
    }
    if(coin2 == 0){
        cout<<"R是对称的"<<endl;
    }
    if((coin3) - order == 0){
        cout<<"R是反对称的"<<endl;
    }
    //传递
    //若其为传递的则其传递闭包与原矩阵相等
    int temp[order][order];
    for(int i = 0; i < order ; i ++){
        for(int j = 0; j < order ;j ++){
            temp[i][j] = square[i][j];
        } 
    }
    for(int i = 0; i < order ; i ++){
        for(int j = 0; j < order ;j ++){
            if(temp[j][i] == 1){
                for(int k = 0; k < order; k ++){
                   temp[j][k] = temp[j][k] || temp[i][k];
                }
            }
        } 
    }
    int coin4 = 0;
    for(int i = 0; i < order ; i ++){
        for(int j = 0; j < order ;j ++){
            if(temp[i][j] != square[i][j]){
                coin4 ++;
            }
        } 
    }
    if(coin4 == 0){
        cout<<"R是传递的"<<endl;
    }

}

5.实验结果

示例一：
《离散数学》实验报告HEBUT

示例二：
《离散数学》实验报告HEBUT

示例三：
《离散数学》实验报告HEBUT

示例四：
《离散数学》实验报告HEBUT

实验四：关系闭包计算

1.实验目的

熟悉Warshall算法，掌握求关系的自反闭包、对称闭包和传递闭包的方法。

2.实验内容与要求

定义1 设R是A上的二元关系，R的自反（对称、传递）闭包是关系R1，则

① R1是自反的（对称的、传递的）

② R $\subseteq$ R1

③ 对任何自反的（对称的、传递的）关系R2，若R $\subseteq$ R2，则R1 $\subseteq$ R2。

R的自反、对称和传递闭包分别记为r®、s®和t®。

定理1 令R $\subseteq$ A×A，则

① r®=R∪IA

② s®=R∪ $R^-1$

③ t®=R∪ $R^2$ ∪ $R^3$ …

Warshall算法：设R是n个元素集合上的二元关系，M是R的关系矩阵；

(1) 置新矩阵A:=M

(2) 置i:=1；

(3) for j=1 to n do

if A[j,i]=1 then do

for k=1 to n do

A[j,k]:=A[j,k]+A[i,k]

(4) i=i+1；

(5) if i<=n then to (3)

else stop

本实验要求从键盘输入一个关系的关系矩阵，计算其自反闭包、对称闭包和传递闭包，计算传递闭包时使用Warshall算法。用C语言或MATLAB实现。

3.实验报告要求

列出实验目的、实验内容、实验步骤、源程序和实验结果。

4.实验步骤

1.熟悉通过关系矩阵求自反闭包、对称闭包和传递闭包（warshall算法）。

2.程序设计：自反闭包和对称闭包以面向过程为思想，传递闭包以面向对象为思想。

3.程序编写及调试。

4.程序验证。

5.源程序

#include<iostream>
using namespace std;
int main(){
    cout<<"Please enter the order of the square matrix: ";
    int order;
    cin>>order;
    cout<<"Please enter the square matrix:"<<endl;
    int square [order][order];
    for(int i = 0; i < order; i ++){
        for(int j = 0; j < order; j ++){
            cin >> square[i][j];
        }
    }
    //拷贝
    int temp1[order][order];
    int temp2[order][order];
    int temp3[order][order];
    for(int i = 0; i < order ; i ++){
        for(int j = 0; j < order ;j ++){
            temp1[i][j] = square[i][j];
            temp2[i][j] = square[i][j];
            temp3[i][j] = square[i][j];
        } 
    }
    //自反闭包
    cout<<"R的自反闭包为:"<<endl;
    int cont1 = 0;
    for(int i = 0; i < order ; i ++){
        for(int j = 0; j < order ;j ++){
            if(i == j){
                cout<<"1 ";
                cont1 ++;
            }else{
                cout<<temp1[i][j]<<" ";
                cont1 ++;
            }
            if(cont1 % order == 0){
                cout<<endl;
            }
        } 
    }
    //对称闭包
    cout<<"R的对称闭包为:"<<endl;
    int cont2 = 0;
    for(int i = 0; i < order ; i ++){
        for(int j = 0; j < order ;j ++){
           if(temp2[i][j] != temp2[j][i]){
              temp2[i][j] = temp2[j][i] = 1;
            }
            cout<<temp2[i][j]<<" "; 
            cont2 ++;
            if(cont2 % order == 0){
                cout<<endl;
            }
        }        
    }
    //传递闭包
    //存在顺序问题，解决对称和自反闭包的时候，不影响对面元素，而传递闭包处理时会影响
    //不注意区分面向对象编程和面向过程编程造成的问题
    cout<<"R的传递闭包为:"<<endl;
    int cont3 = 0;
    for(int i = 0; i < order ; i ++){
        for(int j = 0; j < order ;j ++){
            if(temp3[j][i] == 1){
                for(int k = 0; k < order; k ++){
                   temp3[j][k] = temp3[j][k] || temp3[i][k]; 
                }
            }
        } 
    }
    for(int i = 0; i < order ; i ++){
        for(int j = 0; j < order ;j ++){
            cout<<temp3[i][j]<<" ";
            cont3 ++;
            if(cont3 % order == 0){
                cout<<endl;
            }
        } 
    }
}

6.实验结果

示例一：

《离散数学》实验报告HEBUT

实验五：计算两结点间长度为m的路的数目

1.实验目的

熟悉邻接矩阵和两结点间长度为m的路的数目的关系并编程计算。

2.实验内容与要求

定义1 给定简单图G=<V，E>，V={ $v_1$ ， $v_2$ ，…， $v_n$ }，V中的结点按下标由小到大编序，则n阶方阵A=( $a_{ij}$ )称为图G的邻接矩阵。其中

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UjUcanHe-1672477553009)(实验报告.assets/wps1.png)] i，j=1，2，…，n。

定理1 设A为简单图G的邻接矩阵，则 $A^m$ 中的i行j列元素 $a^m_{ij}$ 等于G中联结 $v_i$ 到 $v_j$ 的长度为m的链(或路)的数目。

本实验要求从键盘输入图的邻接矩阵和一正整数m，计算结点两两之间长度为m的路的数目。考虑有向图和无向图。用C语言或MATLAB实现。

3.实验报告要求

列出实验目的、实验内容、实验步骤、源程序和实验结果。

4.实验步骤

1.熟悉通过邻接矩阵求长度为m的路的方法。

2.设计程序。

3.编写及调试程序。

4.程序验证。

5.源程序

#include<iostream>
using namespace std;
int main(){
    cout<<"Please enter the order of the square matrix: ";
    int order;
    cin>>order;
    cout<<"Please enter the square matrix:"<<endl;
    int square [order][order];
    for(int i = 0; i < order; i ++){
        for(int j = 0; j < order; j ++){
            cin >> square[i][j];
        }
    }
    cout<<"Please enter the length of the road: ";
    int length;
    cin>>length;
    //拷贝乘数给被乘数
    int multiplicand_array[order][order];
    int temp[order][order] = {0};
    for(int i = 0; i < order; i++){
        for(int j = 0; j < order; j++){
            multiplicand_array[i][j] = square[i][j];
        }
    }
    //进行lenght次矩阵乘法运算
    for(int m = 1; m < length; m++){
        for(int i = 0; i < order; i++){
            for(int j = 0; j < order; j++){
                int temp_sum = 0;
                for(int k = 0; k < order; k++){
                    temp_sum = square[k][j] * multiplicand_array[i][k] + temp_sum;  
                }
                temp[i][j] = temp_sum;
            }
        }
        for(int i = 0; i < order ;i++){
            for(int j = 0; j < order; j++){
                multiplicand_array[i][j] = temp[i][j];
            }
        }
    }
    //输出
    int sum = 0;
    for(int i = 0; i < order; i++){
        for(int j = 0; j < order; j++){
            sum = temp[i][j] + sum;
        }        
    }
    cout<<"结点两两之间长度为"<<length<<"的路的数目有: "<<sum<<" 条";
}

6.实验结果

示例一：
《离散数学》实验报告HEBUT

示例二：
《离散数学》实验报告HEBUT

示例三：
《离散数学》实验报告HEBUT

实验六：最小生成树的构造

1.实验目的

熟悉最小生成树的构造算法，掌握最小生成树的构造过程。

2.实验内容与要求

定义1 设T是一个连通且回路的无向图，则称T为无向树，简称树。树中度数为1的结点称为树叶，度数大于1的结点称为分枝点(或内点)。

定义2设G＝<V，E>是一个连通的无向图，若G的某个生成子图是一棵树，则称该树为G的生成树，记为 $T_G$ 。

定义3假定图G是具有n个结点的连通图。对应于G的每一条边e，指定一个正数C(e)，把C(e)称作边e的权，(可以是长度、运输量、费用等）。G的生成树也具有一个树权C(T)，它是T的所有边权的和。

定义4 在带权的图G的所有生成树中，树权最小的那棵生成树，称作最小生成树。

定理1 (Kruskal) 设图G有n个结点，执行如下步骤

⑴ 选择权最小的边 $e_i$ ,置边数i←1；

⑵ i=n-1结束，否则转⑶；

⑶ 设定已选定 $e_1$ , $e_2$ ,…, $e_i$ 在G中选取不同于 $e_1$ , $e_2$ ,…, $e_i$ 的边 $e_{i+1}$ ，使{ $e_1$ , $e_2$ … $e_i$ $e_{i+1}$ }无回路且 $e_{i+1}$ 是满足此条件的权最小的边。

⑷ i←i+1,转⑵。

本实验要求从键盘输入一个赋权图（边权，以矩阵形式输入），求出对应的最小生成树。用C语言或MATLAB实现。

3.实验步骤

1.熟悉Kruskal算法。

2.了解Krusakl算法的程序实现过程。

3.根据本实验要求设计程序。

4.程序编写及调试。

5.程序验证。

4.实验报告要求

列出实验目的、实验内容、实验步骤、源程序和实验结果。

5.源程序

#include<iostream>
#include<math.h>
using namespace std;
class Edge{
    public:
        int begin,end;
        int weight;
        bool isRight;
};
int findRoot(int parent[],int v)
{
    int now = v;
    while (parent[now] > -1)
    {
        now = parent[now];
    }
    return now;
}
int main(){
    cout<<"Please enter the order of the square matrix: ";
    int order;
    cin>>order;
    int square [order][order];
    cout<<"Please enter the square matrix (注意:以8848代表两个结点间无边):"<<endl;
    //读取临接矩阵到二维数组
    for(int i = 0; i < order; i ++){
        for(int j = 0; j < order; j ++){
            cin >> square[i][j];
        }
    }
    //获取有效边的数量
    int edgesNum = 0;
    for(int i = 0; i < order; i ++){
        for(int j = 0; j < order; j ++){
            if(square[i][j] != 8848){
                edgesNum ++;
            }
        }
    }
    edgesNum = edgesNum / 2;
    //建立有效边edge类数组
    Edge edges[edgesNum];
    int m = 0;
    for(int i = 0; i < order  ;i++){
        for(int j = i + 1; j < order ; j++){
            if(square[i][j] != 8848){
                edges[m].weight = square[i][j];
                edges[m].begin = i;
                edges[m].end = j;
                m ++;
            }
        }
    }
    //Kruskal
    for(int i = 0; i < edgesNum - 1; i++){
        for(int j = 0; j < edgesNum - 1 - i; j++){
            if(edges[j].weight > edges[j + 1].weight){
                Edge temp;
                temp = edges[j];
                edges[j] = edges[j + 1];
                edges[j + 1] = temp;
            }
        }
    }
    //初始化边的isRight
    for(int i = 0; i < edgesNum; i++){
        edges[i].isRight = false;
    }
    //parent数组用来检查结点是否在一个联通集中，申请并初始化
    int parent[order];
    for(int i = 0; i < order ; i++){
        parent[i] = -1;
    }
    int count = 0;
    for(int i = 0; i < edgesNum; i++){
        int vex1,vex2;
        vex1 = findRoot(parent,edges[i].begin);
        vex2 = findRoot(parent,edges[i].end);
        if(vex1 != vex2){
            edges[i].isRight = true;
            parent[vex2] = vex1; //合并生成树
            count ++;
        }
        if(count == order - 1){
            break;
        }
    }
    cout<<"最小生成树如下："<<endl;
    int k = 1;
    for(int i = 0; i < edgesNum; i++){
        if (edges[i].isRight == true)
        {
            cout<<"Edge"<<k;
            cout<<" begin vex "<<edges[i].begin<<" to vex "<<edges[i].end<<" weight "<<edges[i].weight<<endl;
            k ++;
        }     
    }
}