数据结构最小生成树问题实习报告.pdfVIP

实习报告 题目：最小生成树问题 班级 姓名：张旭 学号 完成日期：第十一周 一、需求分析 1.问题描述：在n 个城市间建设信网络，只需要架设 n-1 条线路即可。以最低的代价建设这 个通信网，即求图的最小生成树。 2.基本功能：程序运用普利姆算法或克鲁斯卡尔算法求网的最小生成树及它们之间的权值, 输入各城市的数目以及各个城市之间的距离。将城市之间的距离当做网中各点之间的权值。 3.输入输出：输出结果为文本形式的最小生成树和它们之间的权值。程序演示过程是以用 户和计算机对话的形式进行的，即在计算机终端中显示提示信息后，用户自主选择下一步命 令，然后计算机显示相应的输入数据和运算结果。 二、 概要设计 1.设计思路： 1）给出数据结构的相关定义。 2）采用数组(邻接矩阵)表示法,构造无向网G。 3）用普里姆算法或kruskal的算法构造网G的最小生成树T,输出T的各条边。 克鲁斯卡尔(Kruskal)算法简介： 算法思想：设连通网N=(V,{E})，令最小生成树 （1）初始状态为只有n个顶点而无边的非连通图T=(V,{})，每个顶点自 成一个连通分量； （2）在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分 量上，则将此边加入到中；否则，舍去此边，选取下一条代价最小的边； （3）依此类推，直至T中所有顶点都在同一连通分量上为止。 2.程序结构设计： 本程序主要包括四个模块： （1）主程序模块 （2）堆排序模块 ：包括heapadjust 和 heapsort （3）kruskal 算法模块，采用堆排序，有优化 （4）并查集模块：MFSet 三、 详细设计 #includeiostream #includealgorithm #includectime using namespace std; struct edge { int v1,v2,w; } ; struct MFSet { public: int set[31]; int n; void initial() { for(int i=1;i=n;i++) set[i]=i; } int find(int a) { return set[a]; } bool merge(int a,int b) { int x=set[a]; int y=set[b]; if(x!=y) { set[a]=set[a]--; set[b]=set[b]--; } else return false; return true; } } ; void swap(edge a,edge b) { edge temp; temp=a; a=b; b=temp; } void heapadjust(edge *edges,int i,int n) { while(2*i=n) { int temp=i; if(edges[i].wedges[2*i].w) temp=2*i;