文档介绍：实 验 报 告
试验原理:
Kruskal 算法是一个根据图中边权值递增次序结构最小生成树方法。其基础思想是: 设无向连通网为G＝（V, E）, 令G 最小生成树为T, 其初态为T＝（V, {}）, 即开始时, 最小生成树T 由图G 中n 个顶点组成, 顶点之间没有一条边, 这么T 中各顶点各自组成一个连通分量。然后, 根据边权值由小到大次序, 考察G 边集E 中各条边。若被考察边两个顶点属于T 两个不一样连通分量, 则将此边作为最小生成树边加入到T 中, 同时把两个连通分量连接为一个连通分量; 若被考察边两个顶点属于同一个连通分量, 则舍去此边, 以免造成回路, 如此下去, 当T 中连通分量个数为1 时, 此连通分量便为G 一棵最小生成树。
(a)所表示, 根据Kruskal 所表示。在结构过程中, 根据网中边权值由小到大次序, 不停选择目前未被选择边集中权值最小边。依据生成树概念, n 个结点生成树, 有n－1 条边, 故反复上述过程, 直到选择了n－1 条边为止, 就组成了一棵最小生成树。
试验目:
本试验经过实现最小生成树算法, 使学生了解图数据结构存放表示, 并能了解最小生成树Kruskal 算法。经过练****加强对算法了解, 提升编程能力。
试验内容:
（1）假定每对顶点表示图一条边, 每条边对应一个权值;
（2）输入每条边顶点和权值;
（3）输入每条边后, 计算出最小生成树;
（4）打印最小生成树边顶点及权值。
试验器材（设备、 元器件）:
PC机一台, 装有C语言集成开发环境。
数据结构与程序:
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define X 105
typedef 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\\", "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", &nod