《最小生成树论文-》由会员分享，可在线阅读，更多相关《最小生成树论文-（7页珍藏版）》请在金锄头文库上搜索。
1、最小生成树最小生成树问题摘要：本文通过对最小生成树两种算法（Kruskal算法和Prim算法）的分析，用C语言写出了Kruskal算法的C语言源程序，通过计算机实现求一个连通图的最小生成树问题。关键词：最小生成树 Kruskal算法 Prim算法 C语言源程序引言 现实中一些实际应用问题可通过利用连通图、生成树的模型来建立求解，找出最优的方法，而在任意一个连通图中存在许多条生成树，如何从这些生成树中找出一条权最小的生成树对解决现实生活中实际应用问题具有重大意义，所以经过数学家的研究，目前最小生成树的算法主要有Kruskal算法和Prim算法，那么对这两种方法在计算机上的实现也关系着效率的提高，
2、两种算法的C语言程序也应运而出。正文一 对最小生成树问题中的认识: G(V，E)是一个树，若p(G)2，则G中至少有两个悬挂点。 树G(V，E)中不相邻的两个点间添上一条边，则得到只含一个圈的图G；若在图G中从该圈中再去掉任意一条边得到图G，则图G又成为树。二 最小生成树的算法： Kruskal算法（避圈法）： 令i=1，E0=(空集)； 选一条eiEEi-1,使ei是所有不在Ei-1中且与Ei-1不构成圈的边中权最小的边，如果这样的边不存在，算法终止，此时Ei-1=m-1,则T=（V，Ei-1）是最小树；若Ei-1m-1，则说明原图G=（V,E）不是连通的。 令Ei= Ei-1ei，ii+1
3、，转步。定理：G=(V,E)是连通图，则上述Kruskal算法一定有限终止，且终止时得到的子图T一定是图G的最小生成树。 Prim算法： 从任意一个节点i开始，找到离节点i最近的节点j。令V1=i,j，E1=( i,j),称V1的节点为连通节点集合，网络中其余的节点V1=VVi称作非联通节点集。E1=( i,j)将在最小生成树中。令k=1. 若Vk=,算法终止，已找到最小生成树，Vk为相应的节点集，Ek为相应的边集；否则从Vk中选择一个离Vk最近的成员节点p（如果Vk中有两个或两个以上的节点离Vk最近，则从中选一个；如果Vk中所有节点均不能与Vk连通，则说明图G不是连通的）。设q是表示Vk中离
4、p最近的节点，则边（p,q）将在最小生成树中。更新Vk和 Vk，令Vk+1Vkp, Vk+1Vkp,Ek+1Ek(p,q)。 令k=k+1，转步。三 C语言源程序：#include #include #define MAX 100#define MAXCOST 0x7fffffff int graphMAXMAX; int Prim(int graphMAX, int n)/* lowcosti记录以i为终点的边的最小权值，当lowcosti=0时表示终点i加入生成树 */int lowcostMAX; /* msti记录对应lowcosti的起点，当msti=0时表示起点i加入生成树 */i
5、nt mstMAX; int i, j, min, minid, sum = 0; /* 默认选择1号节点加入生成树，从2号节点开始初始化 */for (i = 2; i = n; i+)/* 最短距离初始化为其他节点到1号节点的距离 */lowcosti = graph1i; /* 标记所有节点的起点皆为默认的1号节点 */msti = 1; /* 标记1号节点加入生成树 */mst1 = 0; /* n个节点至少需要n-1条边构成最小生成树 */for (i = 2; i = n; i+)min = MAXCOST;minid = 0; /* 找满足条件的最小权值边的节点minid */f
6、or (j = 2; j = n; j+)/* 边权值较小且不在生成树中 */if (lowcostj min & lowcostj != 0)min = lowcostj;minid = j;/* 输出生成树边的信息:起点，终点，权值 */printf(%c - %c : %dn, mstminid + A - 1, minid + A - 1, min); /* 累加权值 */sum += min; /* 标记节点minid加入生成树 */lowcostminid = 0; /* 更新当前节点minid到其他节点的权值 */for (j = 2; j = n; j+)/* 发现更小的权值
7、*/if (graphminidj lowcostj)/* 更新权值信息 */lowcostj = graphminidj; /* 更新最小权值边的起点 */mstj = minid;/* 返回最小权值和 */return sum; int main()int i, j, k, m, n;int x, y, cost;char chx, chy; /* 读取节点和边的数目 */printf(输入连通图的节点和边的数目:n);scanf(%d%d, &m, &n);getchar(); /* 初始化图，所有节点间距离为无穷大 */for (i = 1; i = m; i+)for (j = 1;
8、 j = m; j+)graphij = MAXCOST; /* 读取边信息 */for (k = 0; k n; k+)printf(输入第%d条边的信息:,k+1);scanf(%c %c %d, &chx, &chy, &cost);getchar();i = chx - A + 1;j = chy - A + 1;graphij = cost;graphji = cost; /* 求解最小生成树 */printf(最小生成树为:n);cost = Prim(graph, m); /* 输出最小权值和 */printf(最小权值和为:%dn, cost); /system(pause);
9、return 0;四 C程序解题：编写程序:对于如下一个带权无向图，给出节点个数以及所有边权值，用Kruskal算法求最小生成树。输入数据:7 11A B 7A D 5B C 8B D 9B E 7C E 5D E 15D F 6E F 8E G 9F G 11运行结果为：结论：最小生成树的两种算法各有各的优点，要视具体问题决定使用哪种方法解决问题，但本质上都是选择加入当前剩余边集中最短的边，被成为“贪婪”算法；将数学方法和计算机语言结合起来将极大提高解题的效率，通过这种形式既加深了对最小生成树算法的理解，又对计算机语言的使用更加了解和使用。参考文献1.王周宏 运筹学基础 清华大学出版社/北京交通大学出版社2.何钦铭 颜晖 C语言程序设计 高等教育出版社3.耿祥义 张跃平 C语言程序设计实用教程 清华大学出版社4.王敬华 林萍 张清国 骆昌日 C语言程序设计实用教程习题解答与实验指导 清华大学出版社
