最小生成树Prim、Kruskal算法整理版VIP专享VIP免费

标准文案大全一、树及生成树的基本概念树是无向图的特殊情况，即对于一个N个节点的无向图，其中只有N-1条边，且图中任意两点间有且仅有一条路径，即图中不存在环，这样的图称为树，一般记为T。树定义有以下几种表述：(1)、T连通、无圈、有n个结点，连通有n－1条边；(2)、T无回路，但不相邻的两个结点间联以一边，恰得一个圈；(3)、T连通，但去掉任意一边，T就不连通了（即在点集合相同的图中，树是含边数最少的连通图）；(4)、T的任意两个结点之间恰有一条初等链。例如：已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。若用六个点v1⋯v6代表这六个城市，在任意两个城市之间架设电话线，即在相应的两个点之间连一条边。这样，六个城市的一个电话网就作成一个图。任意两个城市之间均可以通话，这个图必须是连通图，且这个图必须是无圈的。否则，从圈上任意去掉一条边，剩下的图仍然是六个城市的一个电话网。图5-6是一个不含圈的连通图，代表了一个电话线网。生成树（支撑树）定义：如果图G’是一棵包含G的所有顶点的树，则称G’是G的一个支撑树或生成树。例如,图5-7b是图5-7a的一个支撑树。定理：一个图G有生成树的条件是G是连通图。证明:必要性显然；充分性:设图G是连通的，若G不含圈，则按照定义，G是一个树，从而G是自身的一个生成树。若G含圈，则任取G的一个圈，从该圈中任意去掉一条边，得到图G的一生成子图G1。若G1不含圈，则G1是G的一个生成树。若G1仍然含圈，则任取G1的一个圈，再从圈中任意去掉一条边，得到图G的一生成子图G2。依此类推，可以得到图G的一个生成子图GK，且不含圈，从而GK是一个生成树。寻找连通图生成树的方法：破圈法：从图中任取一个圈，去掉一条边。再对剩下的图重复以上步骤，直到不含圈时为止，这样就得到一个生成树。取一个圈(v1,v2,v3,v1)，在一个圈中去掉边e3。在剩下的图中，再取一个圈（v1,v2,v4,v3,v1），去掉边e4。再从圈（v3,v4,v5,v3）中去掉边e6。再从圈(v1,v2,v5,v4,v3,v1）中去掉边e7，这样，剩下的图不含圈，于是得到一个支撑树，如图所示。避圈法：也称为生长法，从图中某一点开始生长边，逐步扩展成长为一棵树，每步选取与已入树的边不构成圈的那些边。标准文案大全二、最小生成树概念：设G=(V,E)是无向连通带权图，即一个网络。E中每条边(v,w)的权为c[v,w]。所有生成树G’上各边权的总和最小的生成树称为G的最小生成树。应用：如在设计通信网络时，用图的顶点表示城市，用边(v,w)的权c[v，w]表示建立城市v、w之间的通信线路所需的费用，则最小生成树就给出了建立通信网络最经济的方案。性质：设G=(V,E)是连通带权图，U是V的真子集。若(u,v)E，且uU，vV-U，且在所有这样的边中，(u,v)的权c[u，v]最小，那么一定存在G的一棵最小生成树，它以(u,v)为其中一条边。这个性质也称为MST性质。算法：经典方法有两种：kruskal、prim算法（贪心思想）：一次生成一条最短边。【Prim算法】：算法思想：任意时刻的中间结果都是一棵树，每次花费最小的代价，用一条边把不在树中的结点加进来。按结点来贪，因此适用于稠密图的处理.算法内容：①设置顶点集合V和边集E，它们的初始状态为空集。②任意选取一个顶点A加入V中。③重复以下过程直到V中已经包含原图的所有节点：1、选一条权值最小的边(u,v)，并使其满足u,v两节点只有一个在点集V中。2、将两个节点中不在V的那个点加入集合V中，并将边(u,v)加入边集E中。④所得的子图G’=(V,E)即为所求的最小生成树。关键：找出当前最优得一条边,穷举每一条不在集合E中的边，找出符合条件且最优的边。时间复杂度：O（V*E），即顶点数乘以边数。代码：varn,i,j,k,min,sum:longint;a:array[1..1000,1..1000]oflongint;b,d:array[1..1000]oflongint;procedureprim;beginsum:=0;标准文案大全fori:=1tondod[i]:=a[1,i];forj:=2tondobeginmin:=maxlongint;fori:=1tondoif(d[i]0)thenbeginmin:=d[i];k:=i;end;sum:=sum+d[k];d[k]:=0;fori:=1tondoif(a[k,i]k)thend[i]:=a[k,i];end;end;beginreadln(n);fori:=1tondoforj:=1tondobeginread(...