下载文档原格式
最小生成树实验报告最小生成树实验报告一、引言最小生成树是图论中的一个重要概念，它在实际问题中有着广泛的应用。
本次实验旨在通过编程实现最小生成树算法，并通过实验数据对算法进行分析和评估。
二、算法介绍最小生成树算法的目标是在给定的带权无向图中找到一棵生成树，使得树上所有边的权重之和最小。
本次实验我们选择了两种经典的最小生成树算法：Prim 算法和Kruskal算法。
1. Prim算法Prim算法是一种贪心算法，它从一个顶点开始，逐步扩展生成树的规模，直到包含所有顶点为止。
算法的具体步骤如下：（1）选择一个起始顶点，将其加入生成树中。
（2）从与生成树相邻的顶点中选择一个权重最小的边，将其加入生成树中。
（3）重复上述步骤，直到生成树包含所有顶点。
2. Kruskal算法Kruskal算法是一种基于并查集的贪心算法，它首先将图中的边按权重从小到大进行排序，然后逐个加入生成树中，直到生成树包含所有顶点为止。
算法的具体步骤如下：（1）将图中的边按权重从小到大进行排序。
（2）逐个加入边，如果该边的两个顶点不在同一个连通分量中，则将其加入生成树中。
（3）重复上述步骤，直到生成树包含所有顶点。
三、实验过程本次实验我们使用C++语言实现了Prim算法和Kruskal算法，并通过随机生成的图数据进行了测试。
1. Prim算法的实现我们首先使用邻接矩阵表示图的结构，然后利用优先队列来选择权重最小的边。
具体实现过程如下：（1）创建一个优先队列，用于存储生成树的候选边。
（2）选择一个起始顶点，将其加入生成树中。
（3）将与生成树相邻的顶点及其边加入优先队列。
（4）从优先队列中选择权重最小的边，将其加入生成树中，并更新优先队列。
（5）重复上述步骤，直到生成树包含所有顶点。
2. Kruskal算法的实现我们使用并查集来维护顶点之间的连通关系，通过排序后的边序列来逐个加入生成树中。
具体实现过程如下：（1）将图中的边按权重从小到大进行排序。
数据结构实验三实验报告数据结构实验三实验报告一、实验目的本次实验的目的是通过实践掌握树的基本操作和应用。
具体来说，我们需要实现一个树的数据结构，并对其进行插入、删除、查找等操作，同时还需要实现树的遍历算法，包括先序、中序和后序遍历。
二、实验原理树是一种非线性的数据结构，由结点和边组成。
树的每个结点都可以有多个子结点，但是每个结点只有一个父结点，除了根结点外。
树的基本操作包括插入、删除和查找。
在本次实验中，我们采用二叉树作为实现树的数据结构。
二叉树是一种特殊的树，每个结点最多只有两个子结点。
根据二叉树的特点，我们可以使用递归的方式实现树的插入、删除和查找操作。
三、实验过程1. 实现树的数据结构首先，我们需要定义树的结点类，包括结点值、左子结点和右子结点。
然后，我们可以定义树的类，包括根结点和相应的操作方法，如插入、删除和查找。
2. 实现插入操作插入操作是将一个新的结点添加到树中的过程。
我们可以通过递归的方式实现插入操作。
具体来说，如果要插入的值小于当前结点的值，则将其插入到左子树中；如果要插入的值大于当前结点的值，则将其插入到右子树中。
如果当前结点为空，则将新的结点作为当前结点。
3. 实现删除操作删除操作是将指定的结点从树中移除的过程。
我们同样可以通过递归的方式实现删除操作。
具体来说，如果要删除的值小于当前结点的值，则在左子树中继续查找；如果要删除的值大于当前结点的值，则在右子树中继续查找。
如果要删除的值等于当前结点的值，则有三种情况：- 当前结点没有子结点：直接将当前结点置为空。
- 当前结点只有一个子结点：将当前结点的子结点替代当前结点。
- 当前结点有两个子结点：找到当前结点右子树中的最小值，将其替代当前结点，并在右子树中删除该最小值。
4. 实现查找操作查找操作是在树中寻找指定值的过程。
同样可以通过递归的方式实现查找操作。
具体来说，如果要查找的值小于当前结点的值，则在左子树中继续查找；如果要查找的值大于当前结点的值，则在右子树中继续查找。
实验5 最小生成树算法的设计与实现一、实验目的1、根据算法设计需要, 掌握连通图的灵活表示方法；2、掌握最小生成树算法，如Prim、Kruskal算法；3、基本掌握贪心算法的一般设计方法；4、进一步掌握集合的表示与操作算法的应用。
二、实验内容1、认真阅读算法设计教材和数据结构教材内容, 熟习连通图的不同表示方法和最小生成树算法；2、设计Kruskal算法实验程序。
有n个城市可以用（n-1）条路将它们连通，求最小总路程的和。
设计测试问题,修改并调试程序, 输出最小生成树的各条边, 直至正确为止。
三、Kruskal算法的原理方法边权排序:1 3 14 6 23 6 41 4 52 3 53 4 52 5 61 2 63 5 65 6 61. 初始化时：属于最小生成树的顶点U={}不属于最小生成树的顶点V={1，2，3，4，5，6}2. 根据边权排序，选出还没有连接并且权最小的边（1 3 1），属于最小生成树的顶点U={1，3}，不属于最小生成树的顶点V={2,4,5,6}3. 根据边权排序，选出还没有连接并且权最小的边（4 6 2），属于最小生成树的顶点U={{1，3}，{4，6}}（还没有合在一起，有两颗子树），不属于最小生成树的顶点V={2,5}4. 根据边权排序，选出还没有连接并且权最小的边（3 6 4），属于最小生成树的顶点U={1，3，4，6}（合在一起），不属于最小生成树的顶点V={2,5}5. 根据边权排序，选出还没有连接并且权最小的边（3 6 4），属于最小生成树的顶点U={1，2，3，4，6},，不属于最小生成树的顶点V={5}6. 根据边权排序，选出还没有连接并且权最小的边（3 6 4），属于最小生成树的顶点U={1，2，3，4，5，6}此时，最小生成树已完成四、实验程序的功能模块功能模块：bool cmp(Edge a,Edge b)； //定义比较方法x)；//在并查集森林中找到x的祖先int g etfa(intint s ame(int x,int y)； //判断祖先是否是同一个，即是否联通 void merge(int x,int y); //合并子树，即联通两子树sort(e+1,e+m+1,cmp); //对边按边权进行升序排序详细代码：#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define M AXN_E 100000#define M AXN_V 100000using namespace std;struct Edge{int f m,to,dist;//边的起始顶点，边的到达顶点，边权}e[MAXN_E];int f a[MAXN_V],n,m; //顶点数组，顶点总数，边总数 //定义比较，只是边权比较bool cmp(Edge a,Edge b){return a.dist < b.dist;}//查找x的祖先是在并查集森林中找到x的祖先x){//getfaint g etfa(intreturn fa[x];if(fa[x]==x)else r eturn fa[x] = getfa(fa[x]);}//判断祖先是否是同一个，即是否联通int s ame(int x,int y){return getfa(x)==getfa(y);}//合并两棵树void merge(int x,int y){int f ax=getfa(x),fay=getfa(y);fa[fax]=fay;}int m ain(){int i;cout<<"请输入顶点数目和边数目："<<endl;cin>>n>>m;//n为点数，m为边数//输出顶点信息cout<<"各个顶点值依次为："<<endl;for(i=0;i<n;i++){fa[i]=i;if(i!=0)cout<<fa[i]<<" ";}cout<<endl;cout<<"请输入边的信息（例子：1 4 5 从顶点1到顶点4的边权为5）"<<endl;for(i=1;i<=m;i++)用边集数组存放边，方便排序和调用 cin>>e[i].fm>>e[i].to>>e[i].dist;//sort(e+1,e+m+1,cmp); //对边按边权进行升序排序表示目前的点共存在于多少个集合中，初始情况是每 int r st=n,ans=0;//rst个点都在不同的集合中for(i=1;i<=m && rst>1;i++){int x=e[i].fm,y=e[i].to;函数是查询两个点是否在同一集合中 if(same(x,y))continue;//sameelse{函数用来将两个点合并到同一集合中 merge(x,y);//mergerst--;//每次将两个不同集合中的点合并，都将使rst值减1这条边是最小生成树中的边，将答案加上边权 ans+=e[i].dist;//}}cout<<ans;return 0;}五、测试数据和相应的最小生成树Input:6 101 2 61 3 11 4 52 3 52 5 63 4 53 5 63 6 44 6 25 6 6Putout:18生成树为：七、思考题1、微软面试题一个大院子里住了50户人家，每家都养了一条狗，有一天他们接到通知说院子里有狗生病了，并要求所有主人在发现自己家狗生病的当天就要把狗枪杀掉。
图的最短路径与最小生成树算法实践在计算机科学中，图（Graph）是一种抽象的数据结构，它由节点（Vertex）和边（Edge）组成。
图的最短路径和最小生成树是图算法中的两个重要问题，它们在网络、交通、社交网络等领域有着广泛的应用。
本文将介绍图的最短路径算法和最小生成树算法的实践。
一、图的最短路径算法实践图的最短路径算法用于求解两个节点之间的最短路径，常用的算法有迪杰斯特拉算法（Dijkstra Algorithm）和弗洛伊德算法（Floyd Algorithm）。
（这里可以介绍迪杰斯特拉算法和弗洛伊德算法的思想和流程，注意使用文字和图示来说明）在实际应用中，最短路径算法可以被用于许多场景，比如导航系统中的路径规划、物流配送中的最优路线选择等。
例如，在一座城市中，我们需要规划出从A地到B地的最短路径，可以使用最短路径算法来求解。
二、图的最小生成树算法实践图的最小生成树算法用于找到一个连通图的最小生成树，最常用的算法是普里姆算法（Prim Algorithm）和克鲁斯卡尔算法（Kruskal Algorithm）。
（这里可以介绍普里姆算法和克鲁斯卡尔算法的思想和流程，注意使用文字和图示来说明）最小生成树算法在实际应用中也有很多用途，比如电力系统的最优输电线路规划、通信网络的构建等。
例如，在一个城市的交通网络中，我们希望为每个区域之间建立电缆线路，以便实现高速、稳定的通信，可以使用最小生成树算法来求解。
三、图的最短路径和最小生成树算法在实践中的应用图的最短路径和最小生成树算法在现代社会中有广泛的应用，下面将介绍一些实际应用场景。
1. 路径规划最短路径算法可以用于导航系统中的路径规划。
通过输入起点和终点，最短路径算法可以帮助我们找到从起点到终点的最短路径，以便在导航系统上为驾驶员提供准确的路线指引。
2. 物流配送在物流配送中，最短路径算法可以用于选择最优路线，以节省时间和成本。
通过计算各个配送点之间的距离和路径，可以帮助物流公司规划出最佳配送路线，提高配送效率。
实验报告实验原理：Kruskal 算法是一种按照图中边的权值递增的顺序构造最小生成树的方法。
其基本思想是：设无向连通网为G＝（V，E），令G 的最小生成树为T，其初态为T＝（V，{}），即开始时，最小生成树T 由图G 中的n 个顶点构成，顶点之间没有一条边，这样T 中各顶点各自构成一个连通分量。
然后，按照边的权值由小到大的顺序，考察G 的边集E 中的各条边。
若被考察的边的两个顶点属于T 的两个不同的连通分量，则将此边作为最小生成树的边加入到T 中，同时把两个连通分量连接为一个连通分量；若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路，如此下去，当T 中的连通分量个数为1 时，此连通分量便为G 的一棵最小生成树。
如教材153页的图4.21(a)所示，按照Kruskal 方法构造最小生成树的过程如图 4.21 所示。
在构造过程中，按照网中边的权值由小到大的顺序，不断选取当前未被选取的边集中权值最小的边。
依据生成树的概念，n 个结点的生成树，有n－1 条边，故反复上述过程，直到选取了n－1 条边为止，就构成了一棵最小生成树。
实验目的：本实验通过实现最小生成树的算法，使学生理解图的数据结构存储表示，并能理解最小生成树Kruskal 算法。
通过练习，加强对算法的理解，提高编程能力。
实验内容：（1）假定每对顶点表示图的一条边，每条边对应一个权值；（2）输入每条边的顶点和权值；（3）输入每条边后，计算出最小生成树；（4）打印最小生成树边的顶点及权值。
实验器材（设备、元器件）：PC机一台，装有C语言集成开发环境。
数据结构与程序：#include <iostream>#include <cstdio>#include <algorithm>using namespace std;#define X 105typedef struct Edge{int w;int x, y;} Edge; //储存边的struct，并储存边两端的结点class GraphNode{public:int data;int father;int child;} GraphNode[X]; //储存点信息的并查集类（点的值，父结点，子结点）Edge edge[X*X];bool comp(const Edge, const Edge);void update(int);int main(){int node_num;int sum_weight = 0;FILE *in = fopen("C:\\Users\\瑞奇\\Desktop\\编程实验\\数据结构实验\\FileTemp\\in.txt", "r");cout << "Reading data from file..." << endl << endl;//cout << "Please input the total amount of nodes in this Graph: ";//cin >> node_num;fscanf(in, "%d", &node_num);//cout << "Please input the data of each node: " << endl;for(int i = 1;i <= node_num;i++){//cin >> GraphNode[i].data;fscanf(in, "%d", &GraphNode[i].data);GraphNode[i].father = GraphNode[i].child = i;} //初始化点集//cout << "Please input the relation between nodes in this format and end with (0 0 0):" << endl << "(first_node second_node egde_weight)" << endl;int x, y, w, tmp_cnt = 1;//while(cin >> x >> y >> w && w)while(fscanf(in, "%d%d%d", &x, &y, &w) != EOF && w)edge[tmp_cnt].w = w, edge[tmp_cnt].x = x, edge[tmp_cnt++].y = y;fclose(in);sort(edge+1, edge+tmp_cnt, comp); //对边权进行排序cout << "The MinSpanTree contains following edges: " << endl << endl;for(int i = 1;i <= tmp_cnt;i++) //循环找最小边if(GraphNode[edge[i].x].father != GraphNode[edge[i].y].father){int n = edge[i].x;int m = n;if(GraphNode[m].father != m) //使用并查集对边是否可用进行判断{m = GraphNode[m].father;GraphNode[m].father = GraphNode[edge[i].y].father;}GraphNode[edge[i].x].father = GraphNode[edge[i].y].father;GraphNode[edge[i].y].child = GraphNode[edge[i].x].child;while(GraphNode[n].child != n)n = GraphNode[n].child;update(n); //在合并点集后对并查集进行更新sum_weight += edge[i].w; //计算总权cout << "\t" << "The edge between " << GraphNode[edge[i].x].data << " & " << GraphNode[edge[i].y].data << " with the weight " << edge[i].w << endl;}cout << endl << "And the total weight of the MinSpanTree add up to: " << sum_weight << endl;return 0;}bool comp(const Edge a, const Edge b){return a.w < b.w;}void update(int n){if(GraphNode[n].father == n)return;GraphNode[GraphNode[n].father].child = GraphNode[n].child;//更新孩子结点update(GraphNode[n].father); //递归更新GraphNode[n].father = GraphNode[GraphNode[n].father].father;//更新父结点}程序运行结果：运行程序，程序读取文件，获取文件中关于图的信息：结点数，结点值，结点间边权。
数据结构树的实验报告数据结构树的实验报告引言：数据结构是计算机科学中的重要基础，它涉及到如何组织和存储数据以便有效地使用。
树是一种常见的数据结构，它具有层次结构和分支特征，被广泛应用于各个领域。
本实验旨在通过实践操作和观察，深入理解树的特性和应用。
一、实验目的本实验的目的是通过实践操作，掌握树的基本概念、特性和常见操作。
具体目标包括：1. 了解树的基本概念和术语；2. 掌握树的构建和遍历方法；3. 理解树的应用场景和相关算法。
二、实验过程1. 树的构建在本实验中，我们使用Python编程语言实现了树的构建。
首先，我们定义了树的节点类，节点包含一个值和指向子节点的指针。
然后，我们通过递归的方式构建了一棵树，树的每个节点都可以有多个子节点。
2. 树的遍历树的遍历是指按照一定的顺序访问树的所有节点。
在本实验中，我们实现了树的三种遍历方式：前序遍历、中序遍历和后序遍历。
前序遍历是先访问根节点，然后依次递归遍历左子树和右子树；中序遍历是先递归遍历左子树，然后访问根节点，最后递归遍历右子树；后序遍历是先递归遍历左子树和右子树，最后访问根节点。
3. 树的应用树作为一种重要的数据结构，在实际应用中有着广泛的应用。
在本实验中，我们选择了两个常见的树的应用场景进行了实践操作。
（1）文件系统文件系统可以看作是一棵树，根目录为根节点，各级子目录和文件为子节点。
通过实践操作，我们可以模拟文件系统的创建、删除、查找等操作，加深对树的理解。
（2）家谱家谱也可以看作是一棵树，根节点为家族的祖先，各级子节点为后代。
通过实践操作，我们可以实现家谱的构建、查询和修改，了解家谱的组织和维护方式。
三、实验结果与分析通过实验操作，我们成功构建了树的数据结构，并实现了树的遍历和应用。
在文件系统的实践中，我们能够灵活地创建、删除和查找文件和目录，实现了对文件系统的基本操作。
在家谱的实践中，我们能够方便地构建和查询家族成员的关系，加深了对家谱的理解。
数据结构实验报告名称：最小生成树班级：122姓名：*****学号：*********** 指导老师：********一、设计目的与任务1.1课程设计目的本课程设计的目的是了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发。
1.2课程设计的任务问题描述: 已知一个无向连通网表示n个城市以及城市间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边上的权值表示相应的代价。
对于n个点的连通网能建立许多不同的生成树，每一棵生成树都可以是一个通信网。
我们要选择一棵生成树，使总的耗费最小。
二、设计方案2.1需求分析（1）建立一个图，其存储方式可以采用邻接矩阵形式或者邻接表；（2）利用普利姆算法或者克鲁斯卡尔算法求出网的最小生成树；（3）输入各城市的数目以及各个城市之间的距离。
将城市之间的距离当做网中各点之间的权值。
按顺序输出生成树中各条边以及它们的权值。
2.2数据结构分析构造最小生成树的方法：最初生成树为空，即没有一个结点和一条边，首先选择一个顶点作为生成树的根，然后每次从不在生成树中的边中选择一条权值尽可能小的边，为了保证加入到生成树中的边不会造成回路，与该边邻接的两个顶点必须一个已经在生成树中，一个则不在生成树中，若网中有n个顶点（这里考虑的网是一个连通无向图），则按这种条件选择n-1边就可以得到这个网的最小生成树了。
详细的过程可以描述为：设置2个集合，U集合中的元素是在生成树中的结点，V-U集合中的元素是不在生成树中的顶点。
首先选择一个作为生成树根结点的顶点，并将它放入U集合，然后在那些一端顶点在U集合中，而另一端顶点在V-U集合中的边中找一条权最小的边，并把这条边和那个不在U集合中的顶点加入到生成树中，即输出这条边，然后将其顶点添加到U集合中，重复这个操作n-1次。
弧<v,w>的意义或信息}2.3最小生成树的算法分析在该函数中主要有五段代码块，分别是主函数代码块、邻接矩阵定义模块代码、创建链接矩阵模块代码、最小生成树Prim 算法及代价模块代码与最小生成树kruskal算法及代价模块代码，五段代码块分别有着不同的作用，共同满足了课题所需要实现的功能。
2.4邻接矩阵定义模块代码typedef struct ArcCell{int adj; char *info;}ArcCell,AdjMatrix[20][20];typedef struct {char vexs[20]; AdjMatrix arcs;int vexnum,arcnum;}MGraph_L;int localvex(MGraph_L G,char v){ int i=0; while(G.vexs[i]!=v) { ++i;} return i;}用typedef struct定义邻接矩阵，通过二维数组来存储邻接矩阵，并设定参数的最大值为20。
2.5创建邻接矩阵模块代码int creatMGraph(MGraph &G){char v1,v2;int i,j,w;printf("建立邻接矩阵:\n");printf("请输入图G顶点（城市）和弧（边）的个数:");scanf("%d",&G.vexnum);scanf("%d",&G.arcnum);printf("输入所有顶点:");for(i=0;i<G.vexnum;++i){cin>>G.vexs[i];}for(i=0;i<G.vexnum;i++)for(j=0;j<G.vexnum;j++){G.arcs[i][j].adj=int_max;G.arcs[i][j].info=NULL;}printf("输入所有边及依附的顶点（城市）和权（距离）:\n"); for(int k=0;k<G.arcnum;k++){cin>>v1>>v2>>w;i=localvex(G,v1);j=localvex(G,v2);G.arcs[i][j].adj=w;G.arcs[j][i].adj=w;}ljjzprint(G);printf("图G邻接矩阵创建成功！\n");return G.vexnum;}该语句是从键盘输入顶点数和边数，输入顶点和权值，通过循环语句的调用，最后调用creatMGraph_L（）创建连接矩阵。
2.6最小生成树kruskal算法及代价模块代码void MiniSpanTree(MGraphA *D)//生成最小生成树{int i, j, n, m, SUM=0; int k = 1;int parent[M]; edge edges[M];for ( i = 1; i < D->vexnum; i++){for (j = i + 1; j <= D->vexnum; j++){ if (D->arc[i][j].adj == 1){edges[k].begin = i; edges[k].end = j;edges[k].weight = D->arc[i][j].weight; k++;}}}sort(edges, D);for (i = 1; i <= D->arcnum; i++){parent[i] = 0;}printf("最小生成树为:\n");for (i = 1; i <= D->arcnum; i++)//核心部分{n = Find(parent, edges[i].begin);m = Find(parent, edges[i].end);if (n != m){ parent[n] = m;printf("<< %d, %d >> %d\n",)edges[i].begin,edges[i].end,edges[i].weight);SUM=SUM+edges[i].weight;}}cout<<"最少生成树的代价:";cout<<SUM.该语句运用一系列的循环语句来实现的，利用前面的创建好的链接矩阵，通过各边权值的比较，最后调用MiniSpanTree ()函数，实现最小生成树的生成，同时运用sum把最小生成树各边权值相加得到最小生成树的代价。
四、调试分析。
运行程序后出界面，运行结果如下图所示：初界面图与邻接矩阵的生成另一组数据：六、结论经过我不懈的努力我们终于完成了本次课程设计，通过这次课程设计，我感觉到要真正做出一个程序并不很容易，但只要用心去做，总会有收获，特别是当我遇到一个问题，想办法去解决，最后终于找到方法时，心里的那份喜悦之情真是难以形容。
编写程序中遇到问题再所难免，我遇到了一些或大或小的问题，但是不论问题大小都会导致程序不能运行，这就要求我们要既有耐心又要细心，仔细推敲程序，从出现问题的地方起，并联系前后程序，逐个排查，直到最终搞清为止。
我们本次做的是图的最小生成树问题。
通过本次课程设计我们发现我们对于C语言和数据结构还有很多地方不知道，今后需要努力学习。
七、程序部分源代码Typedef struct{int adj;int weight;}AdjMatrix[MAX][MAX];Typedef struct{djMatrix arc;int vexnum, arcnum;}MGraphtypedef struct ArcCell{int adj; char *info;}ArcCell,AdjMatrix[20][20];typedef struct {char vexs[20]; AdjMatrix arcs;int vexnum,arcnum;}MGraph_L;int localvex(MGraph_L G,char v){ int i=0; while(G.vexs[i]!=v) { ++i;} return i;} int creatMGraph(MGraph &G){char v1,v2;int i,j,w;printf("建立邻接矩阵:\n");printf("请输入图G顶点（城市）和弧（边）的个数:");scanf("%d",&G.vexnum);scanf("%d",&G.arcnum);printf("输入所有顶点:");for(i=0;i<G.vexnum;++i){cin>>G.vexs[i];}for(i=0;i<G.vexnum;i++)for(j=0;j<G.vexnum;j++){G.arcs[i][j].adj=int_max;G.arcs[i][j].info=NULL;}printf("输入所有边及依附的顶点（城市）和权（距离）:\n");for(int k=0;k<G.arcnum;k++){cin>>v1>>v2>>w;i=localvex(G,v1);j=localvex(G,v2);G.arcs[i][j].adj=w;G.arcs[j][i].adj=w;}ljjzprint(G);printf("图G邻接矩阵创建成功！\n");return G.vexnum;void MiniSpanTree(MGraphA *D)//生成最小生成树{int i, j, n, m, SUM=0; int k = 1;int parent[M]; edge edges[M];for ( i = 1; i < D->vexnum; i++){for (j = i + 1; j <= D->vexnum; j++){ if (D->arc[i][j].adj == 1){edges[k].begin = i; edges[k].end = j;edges[k].weight = D->arc[i][j].weight; k++;} }}sort(edges, D);for (i = 1; i <= D->arcnum; i++){parent[i] = 0;}printf("最小生成树为:\n");for (i = 1; i <= D->arcnum; i++)//核心部分{n = Find(parent, edges[i].begin);m = Find(parent, edges[i].end);if (n != m){ parent[n] = m;printf("<< %d, %d >> %d\n",)edges[i].begin,edges[i].end,edges[i].weight);SUM=SUM+edges[i].weight;}}cout<<"最少生成树的代价:";cout<<SUM.。
