下载文档原格式
最小生成树实验报告最小生成树实验报告一、引言最小生成树是图论中的一个重要概念，它在实际问题中有着广泛的应用。
本次实验旨在通过编程实现最小生成树算法，并通过实验数据对算法进行分析和评估。
二、算法介绍最小生成树算法的目标是在给定的带权无向图中找到一棵生成树，使得树上所有边的权重之和最小。
本次实验我们选择了两种经典的最小生成树算法：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）将图中的边按权重从小到大进行排序。
求最小生成树(Kruskal算法)实验报告一、实验目的通过本次实验，掌握Kruskal算法的基本原理，能够使用该算法求解最小生成树问题，并能够进行实际应用。
同时，为学习算法的设计和分析打下基础。
二、实验内容1. 理解Kruskal算法的基本原理。
2. 实现Kruskal算法，并将其应用于求解最小生成树问题。
3. 设计实验测试用例，验证程序正确性并进行性能分析。
三、实验原理Kruskal算法是最小生成树问题的一种解决方法。
该算法基于贪心策略，通过不断选择最短的边来构造最小生成树。
实现步骤如下：1. 将所有边按权重从小到大进行排序。
2. 遍历所有边，每次选择一条没有出现在生成树中的最短边，并将该边所连接的两个顶点合并到同一连通分量中。
3. 直到所有的边都被遍历过，即可得到最小生成树。
四、实验设计本次实验的主要任务是实现Kruskal算法，并运用到最小生成树问题中。
为了测试算法的正确性和性能，需要设计适当的测试用例。
具体的实验步骤如下：1. 设计数据结构在Kruskal算法中，需要维护边的信息，并对边进行排序，同时需要维护顶点的信息。
为方便实现，可以使用C++语言的STL库中的vector和set数据结构。
vector用于存储顶点信息，set用于存储排序后的边信息。
其中，顶点包含顶点编号和连通分量编号，边包含起点、终点和边权重。
为了方便生成测试数据，定义两个常量：MAX_VERTEX和MAX_EDGE。
MAX_VERTEX表示最大顶点数量，MAX_EDGE表示最大边数量。
2. 生成测试数据为了测试算法的正确性和性能，需要生成不同大小的测试数据。
可以随机生成若干个顶点和相应的边，其中顶点编号从1开始连续编号，边的起点和终点使用随机数生成，边的权重也使用随机数生成。
3. 实现Kruskal算法根据算法原理，可以实现基本的Kruskal算法。
具体实现过程如下：1. 首先将所有的边按照权重从小到大排序，并分别初始化每个顶点的连通分量编号。
一、问题简述题目：图的操作。
要求：用kruskal算法求最小生成树。
最短路径：①输入任意源点，求到其余顶点的最短路径。
②输入任意对顶点，求这两点之间的最短路径和所有路径。
二、程序设计思想首先要确定图的存储形式。
经过的题目要求的初步分析，发现该题的主要操作是路径的输出，因此采用边集数组（每个元素是一个结构体，包括起点、终点和权值）和邻接矩阵比较方便以后的编程。
其次是kruskal算法。
该算法的主要步骤是：GENERNIC-MIT(G,W)1. A←2. while A没有形成一棵生成树3 do 找出A的一条安全边(u,v);4.A←A∪{(u,v)};5.return A算法设置了集合A，该集合一直是某最小生成树的子集。
在每步决定是否把边(u,v)添加到集合A中，其添加条件是A∪{(u,v)}仍然是最小生成树的子集。
我们称这样的边为A 的安全边，因为可以安全地把它添加到A中而不会破坏上述条件。
然后就是Dijkstra算法。
Dijkstra算法基本思路是：假设每个点都有一对标号 (d j, p j)，其中d j是从起源点s到点j的最短路径的长度 (从顶点到其本身的最短路径是零路(没有弧的路)，其长度等于零)；p j则是从s到j的最短路径中j点的前一点。
求解从起源点s到点j的最短路径算法的基本过程如下：1) 初始化。
起源点设置为：① d s=0, p s为空;②所有其他点: d i=∞, p i=?;③标记起源点s，记k=s,其他所有点设为未标记的。
2) 检验从所有已标记的点k到其直接连接的未标记的点j的距离，并设置：d j=min［d j, d k+l kj］式中，l kj是从点k到j的直接连接距离。
3) 选取下一个点。
从所有未标记的结点中，选取d j中最小的一个i：d i=min［d j, 所有未标记的点j］点i就被选为最短路径中的一点，并设为已标记的。
4) 找到点i的前一点。
从已标记的点中找到直接连接到点i的点j*，作为前一点,设置：i=j*5) 标记点i。
c语言数据结构kruskal算法两种构造最小生成树算法1. 引言1.1 概述本篇文章将讨论C语言数据结构中的Kruskal算法以及它的两种构造最小生成树的方法。
数据结构是计算机科学中至关重要的概念，它用于组织和存储数据以便于使用和操作。
C语言是一种广泛应用于系统开发和嵌入式软件的编程语言，而Kruskal算法则是解决图论中最小生成树问题的一种有效方法。
1.2 文章结构本文共分为五个部分。
首先，我们将介绍C语言中的数据结构，包括其概念、在C语言中的实现以及在算法中应用的重要性。
接下来，我们将对Kruskal算法进行简要介绍，包括最小生成树的概念和应用场景、Kruskal算法原理及思路以及详细步骤解析。
然后，我们将探讨Kruskal算法的两种构造最小生成树的方法：按边权重顺序遍历并加入最小生成树中和使用并查集维护连通性信息并进行判断和合并操作。
最后，我们将总结评估这两种方法，并讨论适用情景与选择依据。
文章最后将给出结论与总结，并对该算法的效率、应用案例以及未来的可扩展和改进方向进行分析。
1.3 目的本文旨在深入介绍C语言数据结构中Kruskal算法的两种构造最小生成树的方法，并对它们进行比较与选择依据分析。
通过阅读本文，读者将能够理解数据结构在算法中的应用、掌握Kruskal算法的原理和步骤，并了解如何选择合适的构造最小生成树方法。
此外，本文还将讨论该算法的效率、实际应用案例以及未来可能的发展方向，以便读者更全面地了解该算法并从中受益。
2. C语言数据结构简介：2.1 数据结构概念数据结构是计算机存储、组织和管理数据的方式。
它涉及到如何将不同类型的数据元素组合在一起，以便有效地进行操作和处理。
常见的数据结构包括数组、链表、栈、队列、树等。
2.2 C语言中的数据结构C语言提供了基本的数据类型，如整型、浮点型和字符型等，同时还支持用户自定义的数据结构。
通过使用struct关键字可以定义自己的复合类型，其中可以包含多个不同类型的成员变量。
武汉纺织大学《数据结构》实验报告班级：管工类专业班：序号：实验时间：2014 年5 月16 日指导教师：实验三：图的基本操作与应用一、实验目的：1、掌握图的几种主要存储方法及基本操作2、掌握图的两种遍历方法3、掌握利用普里姆算法和克鲁斯卡尔算法求取最小生成树的方法4、掌握求取AOE网关键路径的方法，以实现项目时间管理二、实验内容：1、编写程序，输出图的邻接矩阵，输出两种遍历序列，并求出最小生成树。
实验步骤：①、在Java语言编辑环境中新建程序，输入顶点集合和边集合，构造一个图7-15所示的带权图，可参考书本225页示例程序；②、对该带权图，进行插入顶点、插入边、删除顶点、删除边操作，并输出操作后的邻接矩阵，可参考书本226-228页示例程序；③、输出从顶点'A'开始的深度优先遍历和广度优先遍历的序列，可参考书本238、240页示例程序；④、输出运用普里姆算法求出的最小生成树，可参考书本245页示例程序。
2、设计一个程序求出完成整项工程至少需要多少时间以及整项工程中的关键实验步骤：①、在Java语言编辑环境中新建程序，输入如下图所示的AOE网；②、按照关键路径求取步骤，求出各个顶点的最早开始时间和最迟开始时间；③、求出各个活动的最早开始时间和最迟开始时间；④、找出该AOE网的关键路径，并计算出该项目的完成时间。
关键路径相关时间知识点：设活动ai由弧<j,k>(即从顶点j到k)表示，其持续时间记为dut(<j,k>),则：e(i)=ve(j) l(i)=vl(k)-dut(<j,k>)求ve(i)和vl(j)分两步：（1）.从ve(1)=0开始向前递推ve(j)=Max{ve(i)+dut(<i,j>)}<i,j>∈T, 2<=j<=n ，其中，T是所有以j为弧头的弧的集合。
（2）.从vl(n)=ve(n)开始向后递推vl(i)=Min{vl(j)-dut(<i,j>)}<i,j>∈S,1<=i<=n-1，其中，S是所有以i为弧尾的弧的集合。
合肥学院计算机科学与技术系课程设计报告2013～2014 学年第 2 学期课程数据结构与算法课程设计题目名称用Kruskal算法求解其所有的最小生成树学生姓名童子轩学号1204013037专业班级12级计本3班指导教师何立新2014 年 9 月题目设计程序完成如下功能：对给定的网和起点，用Kruskal算法的基本思想求解其所有的最小生成树。
一、问题分析及问题定义题目中的要求是用Kruskal算法来求解最小生成树，首先要弄清楚最小生成树是什么，怎么生成最小生成树以及Kruskal算法的基本思想。
最小生成树的定义是：在图论中，常常将树定义为一个无回路连通图。
对于一个带权的无向连通图，其每个生成树所有边上的权值之和可能不同，我们把所有边上权值之和最小的生成树称为图的最小生成树。
在一给定的无向图G = (V, E)中，(u, v)代表连接顶点u与顶点v的边，而 w(u,v) 代表此边的权重，若存在T为 E 的子集且为无循环图，使得权重之和w(T) 最小，则此T为G的最小生成树。
最小生成树的特性有：任意一棵树的最小生成树边上的权值之和最小，最小生成树可能不唯一，因为它们的权值之和相等。
大多数解决该类问题的算法都基于最小生成树的MST性质。
在一个连通网N={V,{E}}中，U是顶点集V的一个非空子集。
如果存在一条具有最小权值的边(u,v)，其中u∈U,v∈(U-V),则必存在一棵包含(u,v)的最小生成树。
克鲁斯卡尔算法的基本思想是：假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。
之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。
数据结构实验报告-最小生成树（精选5篇）第一篇：数据结构实验报告-最小生成树电子科技大学实验报告学生姓名：XXX 学号：20***指导教师：刘峤实验地点：信软楼306实验时间：5月17日一、实验室名称：软件实验室二、实验项目名称：数据结构与算法—图三、实验学时：4四、实验原理：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）打印最小生成树边的顶点及权值。
七、实验器材（设备、元器件）：八、数据结构及程序#include #include #include typedefstruct {intvex;intgno;}TVex,*TpVex;typedefstruct {intvhead, vtail;intwght;intflag;}TEdge,*TpEdge;typedef struct{TpVex VexList;TpEdge EdgeList;int nvex, nedge;}TGraph, *TpGraph;void begin(TpGraph G){ int i;for(i=1;i<=G->nvex;i++){G->VexList[i-1].gno=i;G->EdgeList[i-1].flag=0;} } int findmin(TpGraph G){ int i,j;int minwght=G->EdgeList[0].wght;for(i=0,j=-1;inedge;i++){ PC机一台，装有C/C++语言集成开发环境。
大连民族学院计算机科学与工程学院实验报告实验题目：最小生成树的Kruskal算法课程名称：离散数学实验类型：□演示性□验证性□操作性■设计性□综合性专业：软件工程班级：111学生姓名：xx学号：xx实验日期：2012年12月6-28日实验地点：金石滩校区机房201 实验学时：10学时实验成绩：指导教师：焉德军姜楠2012年12月28 日[实验原理]设所给定无向连通加权图具有n个结点，m条边，首先，将各条边的权按从小到大的顺序排序。
然后依次将这些边按所给图的结构放到生成树中去。
如果在放置某一条边时，使得生成树形成回路，则删除这条边。
这样，直至生成树具有n-1条边时，我们所得到的就是一棵最小生成树。
[实验内容]给定无向连通加权图，编程设计求出其一棵最小生成树。
[实验目的]通过算法设计并编程实现求出给定无向连通加权图的一棵最小生成树，加深学生对求最小生成树的Kruskal算法的理解。
[实验步骤]（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；l j⇒S（i）；j+1⇒j，转（3）。
（6）输出最小生成树S。
（7）结束。
具体程序的C++实现如下：#include<iostream>using namespace std;const int MaxVertex = 20;const int MaxEdge = 100;const int MaxSize = 100;struct EdgeType{int from;int to;int weight;};struct EdgeGraph{char vertex[MaxVertex];EdgeType edge[MaxEdge];int vertexNum;int edgeNum;};int FindRoot(int parent[], int v);void InputInfo();void Kruskal(EdgeGraph G){int vex1,vex2,f,t;int i,num;int parent[MaxVertex];for(i=0; i<G.vertexNum; i++){parent[i] = -1;}for(num =0,i=0; i<G.edgeNum; i++){vex1 = FindRoot(parent, G.edge[i].from);vex2 = FindRoot(parent, G.edge[i].to);if(vex1 != vex2){cout << "(" << G.edge[i].from << "," << G.edge[i].to << ")" << endl;f = G.edge[i].from;t = G.edge[i].to;cout << "(" << G.vertex[f] << "," << G.vertex[t] << ")" << " Weight: " << G.edge[i].weight << endl;cout << endl;parent[vex2] = vex1;num++;if(num == G.vertexNum-1) return;}}return;}int FindRoot(int parent[], int v){int t;t = v;if(parent[t] > -1){t = parent[t];}return t;}void InputInfo(){EdgeGraph G;cout << "Please input vertexNum , edgeNum: " << endl;cin >> G.vertexNum >> G.edgeNum;cout << "Please input the information of edges:" << endl;for(int i=0; i<G.vertexNum; i++){cin >> G.vertex[i];}cout << "Please input this edge attaches two vertices subscript and its weight" << endl;for(int j=0; j<G.edgeNum; j++){cin >> G.edge[j].from >> G.edge[j].to >> G.edge[j].weight;}Kruskal(G);}int main(){InputInfo();system("pause");return 0;}实验过程中遇到的问题及解决过程比如不知道如何存储边集数组，以及比知道如何声明一些变量，函数和怎样去调用Kruskal函数……解决：通过设置结构体EdgeType与结构体EdgeGraph的联合来存储边集，因为在刚开始我在主函数中用EdgeGraph声明变量G，来作为形参去调用Kruskal(G)，编译时就会警告未被初始化的G，的程序出错，后来我将Kruskal(G)在InputInfo() 中调用，因为InputInfo()函数中声明了变量G，并使得G初始化，从而是的程序能正常运行。
数据结构实验报告最小生成树实验目的：掌握最小生成树的概念和算法，培养分析和解决实际问题的能力。
实验内容：利用Kruskal算法求解带权无向连通图的最小生成树。
实验原理：最小生成树是指一个连通图的生成树，其中所有边的权值和最小。
最小生成树问题在图论中有着重要的应用，如网络设计、集成电路布线等领域。
本次实验使用Kruskal算法求解最小生成树。
Kruskal算法基于一个贪心的思想：每次选择权值最小的边，直到生成树中包含所有的节点。
具体算法如下：1.根据给定的连通图构造一个边的集合E，E中包含图中所有的边。
2.将E中的边按照权值从小到大排序。
3.依次遍历排序后的边，如果该边的两个节点不在同一个连通分量中，则选择该边，并将这两个节点合并到一个连通分量中。
4.重复第3步，直到生成树中包含所有的节点。
实验步骤及结果：1.根据给定的连通图构造边的集合E，并将E中的边按照权值从小到大排序。
2.初始化一个空的集合T作为最小生成树的边集合。
3.依次遍历排序后的边，如果该边的两个节点不在同一个连通分量中，则选择该边，并将这两个节点合并到一个连通分量中，同时将该边添加到集合T中。
4.重复第3步，直到生成树中包含所有的节点。
实验结果分析：通过Kruskal算法，可以得到带权无向连通图的最小生成树。
最小生成树具有多个优点，如能够保证连通、权值最小、无回路。
在实际应用中，最小生成树常常用于网络设计、集成电路布线等领域。
实验总结：通过本次实验，我掌握了最小生成树的概念和Kruskal算法的原理和实现方法。
实验中，我通过定义边的数据结构和构造边的集合，实现了Kruskal算法求解最小生成树。
通过实验，我深刻认识到数据结构在解决实际问题中的重要性和实用性。
最小生成树作为一种常用的图论算法，在实际应用中具有广泛的应用和重要的价值。
掌握了最小生成树的概念和算法，我相信能够在今后的学习和工作中更好地应用数据结构算法解决实际问题。
数据结构实验五图的基本操作一、实验目的1、使学生可以巩固所学的有关图的基本知识。
2、熟练掌握图的存储结构。
3、熟练掌握图的两种遍历算法。
二、实验内容[问题描述]对给定图，实现图的深度优先遍历和广度优先遍历。
[基本要求]以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。
以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。
【测试数据】由学生依据软件工程的测试技术自己确定。
三、实验前的准备工作1、掌握图的相关概念。
2、掌握图的逻辑结构和存储结构。
3、掌握图的两种遍历算法的实现。
四、详细设计五、源程序#define INFINITY 10000#define MAX_VERTEX_NUM 40#define MAX 40#include<stdlib.h>#include<stdio.h>#include<conio.h>#include<string.h>typedef struct ArCell{int adj;}ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct{char name[20];}infotype;typedef struct{infotype vexs[MAX_VERTEX_NUM];AdjMatrix arcs;int vexnum,arcnum;}MGraph;int LocateVex(MGraph *G,char* v){ int c=-1,i;for(i=0;i<G->vexnum;i++)if(strcmp(v,G->vexs[i].name)==0){c=i;break;}return c;}MGraph * CreatUDN(MGraph *G)//初始化图，接受用户输入{int i,j,k,w;char v1[20],v2[20];printf("请输入图的顶点数,弧数:");scanf("%d%d",&G->vexnum,&G->arcnum);printf("结点名字:\n");for(i=0;i<G->vexnum;i++){printf("No.%d:",i+1);scanf("%s",G->vexs[i].name);}for(i=0;i<G->vexnum;i++)for(j=0;j<G->vexnum;j++)G->arcs[i][j].adj=INFINITY;printf("请输入一条边依附的两个顶点和权值:\n");for(k=0;k<G->arcnum;k++){printf("第%d条边:\n",k+1);printf("起始结点:");scanf("%s",v1);printf("结束结点:");scanf("%s",v2);printf("边的权值:");scanf("%d",&w);i=LocateVex(G,v1);j=LocateVex(G,v2);if(i>=0&&j>=0){G->arcs[i][j].adj=w;G->arcs[j][i]=G->arcs[i][j];}}return G;}int FirstAdjVex(MGraph *G,int v){int i;if(v<=0 &&v<G->vexnum){ //v合理for(i=0;i<G->vexnum;i++)if(G->arcs[v][i].adj!=INFINITY)return i;}return -1;}void VisitFunc(MGraph *G,int v){printf("%s ",G->vexs[v].name);}int NextAdjVex(MGraph *G,int v,int w){int k;if(v>=0 && v<G->vexnum && w>=0 && w<G->vexnum)//v,w合理{for( k=w+1;k<G->vexnum;k++)if(G->arcs[v][k].adj!=INFINITY)return k;}return -1;}int visited[MAX];void DFS(MGraph *G,int v)//从第v个顶点出发递归地深度优先遍历图G {int w;visited[v]=1;VisitFunc(G,v);//访问第v个结点for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))if(!visited[w]){DFS(G,w);printf("%d ",G->arcs[v][w].adj);}}void DFSTraverse(MGraph *G,char *s)//深度优先遍历{int v,k;for(v=0;v<G->vexnum;v++)visited[v]=0;k=LocateVex(G,s);if(k>=0&&k<G->vexnum){for(v=k;v>=0;v--){if(!visited[v])DFS(G,v);}for(v=k+1;v<G->vexnum;v++)if(!visited[v])DFS(G,v);}}typedef struct Qnode{int vexnum;struct Qnode *next;}QNode,*QueuePtr;typedef struct{QueuePtr front;QueuePtr rear;}LinkQueue;int InitQueue(LinkQueue *Q){Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q->front)exit(0);Q->front->next=NULL;return 1;}void EnQueue(LinkQueue *Q,int a ){QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(0);p->vexnum=a;p->next=NULL;Q->rear->next=p;Q->rear=p;}int DeQueue(LinkQueue *Q,int *v){ QueuePtr p;if(Q->front==Q->rear){printf("结点不存在!\n");exit(0);}p=Q->front->next;*v=p->vexnum;Q->front->next=p->next;if(Q->rear==p)Q->front=Q->rear;return *v;}int QueueEmpty(LinkQueue *Q){if(Q->rear==Q->front)return 0;return 1;}int Visited[MAX];void BFSTraverse(MGraph *G,char *str)//广度优先遍历{int w,u,v,k;LinkQueue Q,q;for(v=0;v<G->vexnum;v++) Visited[v]=0;InitQueue(&Q);InitQueue(&q);k=LocateVex(G,str);for(v=k;v>=0;v--)if(!Visited[v]){Visited[v]=1;VisitFunc(G,v);EnQueue(&Q,v);//v入队while(!QueueEmpty(&Q)){DeQueue(&Q,&u);//出队for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w)) if(!Visited[w]){Visited[w]=1;VisitFunc(G,v);EnQueue(&Q,w);}}}for(v=k+1;v<G->vexnum;v++)if(!Visited[v]){Visited[v]=1;VisitFunc(G,v);EnQueue(&Q,v);//v入队while(!QueueEmpty(&Q)){DeQueue(&Q,&u);//出队for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w)) if(!Visited[w]){Visited[w]=1;VisitFunc(G,v);EnQueue(&Q,w);}}}}void main(){MGraph *G,b;char v[10];G=CreatUDN(&b);printf("请输入起始结点名称:");scanf("%s",v);printf("\n深度优先遍历:\n");DFSTraverse(G,v);printf("\n广度优先遍历:\n");BFSTraverse(G,v);getch();}六、测试数据及调试实验六图的应用一、实验目的1、使学生可以巩固所学的有关图的基本知识。
西北农林科技大学信息工程学院数据结构与C语言综合训练实习报告题目：图的遍历及用克鲁斯卡尔算法求该图的最小生成树学号xxxxxxxxxx姓名xxx专业班级软件工程xxx班指导教师xxx实践日期2010.7.19——2010.7.30目录一、综合训练目的与要求 (3)二、综合训练任务 (3)三、总体设计 (3)设计思想： (3)四、详细设计说明 (4)五、调试与测试 (7)六、实习日志 (10)七、实习总结 (12)八、附录：核心代码清单 (12)一、综合训练目的与要求1. 巩固和加深对C 语言、数据结构课程的基本知识的理解和掌握；2. 利用C 语言进行基本的软件以及算法设计；3. 掌握C 语言编程和程序调试的基本技能；4. 提高运用C 语言、数据结构解决实际问题的能力；5.掌握书写程序设计说明文档的能力。
二、综合训练任务题目：图的遍历及用克鲁斯卡尔算法求该图的最小生成树要求：用邻接矩阵实现图的遍历，并用克鲁斯卡尔算法求出图的最小生成树。
三、总体设计设计思想：采用邻接矩阵来存储图，然后对图进行遍历。
最后采用克鲁斯卡尔算法求出最小生成树。
图3-1函数流程1．定义结构体。
主函数引用函数模块一、二、三，实现算法设计 函数模块一 （图的创建） 采用邻接矩阵做存储结构函数模块二 （图的遍历） 采用深度优先遍历方式结构体定义函数模块三 （求最小生成树） 克鲁斯卡尔算法2．采用邻接矩阵做存储结构创建图（函数模块一）。
3．采用图的深度优先遍历方法进行图的遍历（函数模块二）。
4．采用克鲁斯卡尔算法求出该图的最小生成树（函数模块三）。
5．在主函数里面分别调用以上各个函数，最终实现设计目的。
.四、详细设计说明1．程序结构·函数CreateMGraph用来实现图的创建，以及图的相关信息的存储。
图的存储采用邻接矩阵存储结构。
·函数DFSTraverseM用来读取输入的数据实现图的遍历。
图的遍历可以采用的深度优先的遍历方法，也可以采用广度优先的遍历方法，本段代码设计使用的是深度优先遍历的方法。
·函数minitree_KRUSKAL用来求图的最小生成树。
图的最小生成树有普利姆算法和克鲁斯卡尔算法可以实现，本段代码使用的是克鲁斯卡尔算法，这也是本题所要求使用的。
·各个函数间的联系先调用函数CreateMGraph实现图的创建，然后调用函数DFSTraverseM完成该图的遍历，最后调用函数minitree_KRUSKAL求出该图的最小生成树2．设计说明·在开始的时候添加一些限制条件方便函数的功能实现例如：#define MaxVertexNum 100 //最大顶点个数#define QueueSize 30#define M 30·模块一：图的创建·结构体定义为：typedef struct{VertexType vexs[MaxVertexNum]; //顶点表Link edges[MaxVertexNum][MaxVertexNum]; //图中当前的相连接的两个顶点int n,e; //图中当前的顶点数和边数}MGraph;·函数定义为：MGraph CreateMGraph(){MGraph G;int i,j,k,ch3;char ch1,ch2;printf("请输入该图的顶点数和边数(输入格式为:顶点数,边数<例：4，3>):\n");scanf("%d,%d",&(G.n),&(G.e));printf("请输入该图的顶点信息(顶点名或顶点序号<ch>)每个顶点以回车作为结束:\n");for(i=1;i<=G.n;i++){getchar();scanf("%c",&(G.vexs[i]));}for(i=1;i<=G.n;i++)for(j=1;j<=G.n;j++)G.edges[i][j].w=0;printf("请输入该图每条边对应的两个顶点的名称(输入样例为:a b):\n");for(k=1;k<=G.e;k++){scanf("%c",&ch1);printf("请输入第%d条边的顶点序号：",k);scanf("%c %c",&ch1,&ch2);printf("请输入第%d条边的权值大小：",k);scanf("%d",&ch3);for(i=1;ch1!=G.vexs[i];i++);for(j=1;ch2!=G.vexs[j];j++);e[p].vexh=i;e[p].vext=j;e[p].weight=G.edges[i][j].w=ch3; //权值e[p].flag=0;p++;}return G;}创建图使用的是函数MGraph CreateMGraph()，该图的存储结构是邻接矩阵，先对图的结构体进行定义，再进行初始化。
在函数中需要手动输入图的参数（如顶点数、边数、顶点信息、相连接的顶点、边的权值等）用来建立图并且确定图的邻接矩阵。
最后在完成图的信息输入即建立图以后输出图的邻接矩阵表。
·模块二：图的遍历。
图的遍历用的是深度优先遍历方法，在该方法中采用了递归算法。
void DFSM(MGraph *G,int i){int j;visited[i]=TRUE; //访问顶点viprintf("-->结点%c\n",G->vexs[i]); //打印深度优先遍历结果for(j=1;j<=G->n;j++) //依次搜索邻接点if(G->edges[i][j].w!=0 && !visited[j])DFSM(G,j); //对尚未访问的结点调用DFSM }void DFSTraverseM(MGraph *G){int i;printf("深度优先遍历结果：\n");for(i=1;i<=G->n;i++)visited[i]=FALSE;for(i=1;i<=G->n;i++)if(!visited[i])DFSM(G,i);printf("\n");}·模块二算法解析：1.访问结点v并标记结点v为已访问；再查找结点v的第一个邻接结点w；2.若结点v的邻接结点w存在，则继续进行，否则算法结束；3.若结点w尚未被访问，则递归访问结点w；4.查找结点v的w邻接的下一个邻接结点w，转到步骤3.在图的遍历步骤中不需要进行数据的输入，程序会自动从内存中读取创建图时输入的图的信息进行计算，然后输出遍历结果打印在屏幕上。
·模块三：求图的最小生成树。
该步骤应用的是克鲁斯卡尔算法，它的基本思想是：每次选不属于同一连通分量(保证不生成圈)且边权值最小的顶点，将边加入MST（Minimum Spanning Tree最小生成树），并将所在的2个连通分量合并，直到只剩一个连通分量五、调试与测试刚开始的时候编写出来的代码出了许多的问题，修改起来十分麻烦，后来我改变了编写方法，决定先单独实现一个功能，比如遍历、克鲁斯卡尔最小生成树···这样调试起来就简单的多了。
但是后来又发现这样做虽然前期比较方便，可是后期将他们融合到一起更加麻烦！这是因为单独写的时候忽视了变量名统一的问题，融合的时候出现了许多没有定义的东西花费了大量时间去修改。
但是最后在老师和同学的帮助下总算是完成了。
图5-1 图的创建部分代码的编译结果图5-2 用邻接矩阵存储图，并输出该图的邻接矩阵表图5-3 图的建立和遍历代码的运行结果图5-4克鲁斯卡尔算法求图的最小生成树的完整代码运行结果5-5 完图整代码的初步运行结果图5-6 完整代码修改后的运行结果六、实习日志2010年7月19日星期一今天是我们暑期实习的第一天，早上大家早早的来到机房准备开始实习。
拿到题目的时候小小的郁闷了一下，因为我原来选的是一个比较简单的二叉树遍历的题目，可是现在被调换成了一个算法题，叫什么“克鲁斯卡尔算法求图的最小生成树”。
对于这个算法根本就是不懂啊。
没办法看着大家都已经开始做了我也就只好看下去了，忙了一天，上网查找资料，看书本上的讲解，总算是弄懂了一点儿，但是代码还是没有能写几行。
2010年7月20日星期二实习第二天，突然听说有人已经完成了实习任务，看了看自己写的几行代码，觉得应该要努力了，要不然到实习结束的时候估计还弄不完呢！整个上午都在看克鲁斯卡尔算法的讲解，还是不太明白，没有C语言实现该算法的代码只是看书本上的算法感觉还是写不出来。
于是上网搜索了一下，找了好几个不同的用克鲁斯卡尔算法求图的最小生成树的C语言代码来看，感觉差不多了才开始编写自己的代码。
但是发现了又一个麻烦的问题，那就是关于题目中说的“用邻接矩阵遍历图”到底是怎么个遍历法啊？真是的马虎了，没看清题目。
2010年7月21日星期三实习的第三天，由于昨天被卡在“用邻接矩阵遍历图”这个问题上了，于是今天一来我就赶紧找老师去问这个到底该怎么去做。
原来是要用邻接矩阵来存储图，然后在进行图的遍历。
知道了怎么去做于是接下来就是紧张的代码编写过程了。
建立工作区，写入头文件，定义函数······由于自己好多地方都不会，所以写的很慢一天下来写的也没多少东西。
2010年7月22日星期四实习的第四天，继续昨天的内容。
昨天完成了图的建立和遍历部分的代码，今天开始的时候就没有继续写最小生成树的代码，我觉得应该首先把已经写好的代码进行调试。
结果编译了一下错误竟然有好几十个，哎，代码也就几十行而已。
花了好久也没能全部改正，最后只能是找老师帮忙了。
不过还好今天总算是把前面这一部分弄好了，接下来只是写最小生成树部分的代码了。
2010年7月23日星期五今天是实习的第五天，自己一直以为昨天的工作已经完成了，可是今天来了以后连接上U盘才发现昨天做的东西在里面根本找不到！可能是昨天结束的时候忘了保存······哎，没办法，只能重新写了。
于是又一次打开编译器，引用头文件······忙了一天还是没能赶上昨天的进度，遍历部分还没有写完。
不过吸取了昨天的教训牢记下机前要保存已经完成的东西，要不然又得重新来过了。
