贪心算法Word格式文档下载.docx
《贪心算法Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《贪心算法Word格式文档下载.docx（17页珍藏版）》请在冰点文库上搜索。
3.最小生成树
3.1.最小生成树性质
用贪心算法设计策略可以设计出构造最小生成树的有效算法。
本节介绍的构造最小生成树的Prim算法和Kruskal算法都可以看作是应用贪心算法设计策略的例子。
尽管这2个算法做贪心选择的方式不同，它们都利用了下面的最小生成树性质：
设G=（V,E）是连通带权图，U是V的真子集。
如果（u,v）E，且uU，vV-U，且在所有这样的边中，（u,v）的权c[u][v]最小，那么一定存在G的一棵最小生成树，它以（u,v）为其中一条边。
这个性质有时也称为MST性质。
3.2.Prim算法
设G=（V,E）是连通带权图，V={1,2,…,n}。
构造G的最小生成树的Prim算法的基本思想是：
首先置S={1}，然后，只要S是V的真子集，就作如下的贪心选择：
选取满足条件iS，jV-S，且c[i][j]最小的边，将顶点j添加到S中。
这个过程一直进行到S=V时为止。
在这个过程中选取到的所有边恰好构成G的一棵最小生成树。
3.3.Kruskal算法
Kruskal算法构造G的最小生成树的基本思想是，首先将G的n个顶点看成n个孤立的连通分支。
将所有的边按权从小到大排序。
然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：
当查看到第k条边（v,w）时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边（v,w）将T1和T2连接成一个连通分支，然后继续查看第k+1条边；
如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。
这个过程一直进行到只剩下一个连通分支时为止。
四、[实验代码]
packageArith_Sort;
importjava.util.ArrayList;
importjava.util.List;
publicclassHoffmann{
/**
*哈夫曼算法—java实现
*/
publicstaticvoidmain（String[]args）{
/*****************初始化树**********************/
int[]A={1,2,3,5};
char[]C={'
a'
'
b'
c'
d'
};
ListTree=newArrayList（）;
for（inti=0;
i<
A.length;
i++）
{
TreeNodetreeNode=newTreeNode（A[i],C[i]+"
"
）;
Tree.add（treeNode）;
}
//开始建树
（newHoffmann（））.buildTree（Tree,0,A.length）;
//获得最小生成树的根节点
TreeNodetreeNode=（TreeNode）Tree.get（Tree.size（）-1）;
//遍历这棵树，同时给出每个字符对应的编码
（newHoffmann（））.seekTree（treeNode,"
}
publicvoidseekTree（TreeNodetreeNode,Stringcode）
{
if（treeNode!
=null）
{
seekTree（treeNode.getLeftNode（）,code+"
0"
if（treeNode.getCharValue（）!
System.out.println（"
字符：
+treeNode.getCharValue（）+"
频数：
+treeNode.getNodeValue（）+"
编码：
+code）;
seekTree（treeNode.getRightNode（）,code+"
1"
*建立最小生成树将两个节点组合而成的节点添置列表末尾，新一轮的排序起始位置向后移两位，自由节点数目减少1
*@paramTree
*@paramstart排序列表中剩余自由节点的起始位置
*@paramfreeNodeNum列表中的自由节点数量
publicvoidbuildTree（ListTree,intstart,intfreeNodeNum）
if（Tree!
=null&
&
freeNodeNum>
=2）
QuickSort（Tree,start,Tree.size（）-1）;
//取权值最小的两个节点组合成为新节点，根据排序规则，最小的两个数位于列表的前两位
TreeNodenewNode=newTreeNode（（（TreeNode）Tree.get（start））.getNodeValue（）+（（TreeNode）Tree.get（start+1））.getNodeValue（）,null）;
newNode.setLeftNode（（TreeNode）Tree.get（start））;
newNode.setRightNode（（TreeNode）Tree.get（start+1））;
Tree.add（newNode）;
//将两个节点组合而成的节点添置列表末尾
freeNodeNum--;
//自由节点数减一
buildTree（Tree,start+2,freeNodeNum）;
*快速排序方法实现
*@paramp
*@paramr
publicvoidQuickSort（ListTree,intp,intr）
intq=0;
if（p<
r）
{
q=partion（Tree,p,r）;
QuickSort（Tree,p,q-1）;
QuickSort（Tree,q+1,r）;
}
publicintpartion（ListTree,intp,intr）
intx=（（TreeNode）Tree.get（r））.getNodeValue（）;
inti=p-1;
for（intj=p;
j<
=r-1;
j++）
//换个方向就是从大到小
if（（（TreeNode）Tree.get（j））.getNodeValue（）<
=x）
i++;
Objecttemp=Tree.get（i）;
Tree.set（i,Tree.get（j））;
Tree.set（j,temp）;
Objecttemp=Tree.get（i+1）;
Tree.set（i+1,Tree.get（r））;
Tree.set（r,temp）;
returni+1;
}
/**
*节点类
*@authors001
*
classTreeNode{
//左节点
TreeNodeleftNode;
//右节点
TreeNoderightNode;
//节点值-频度
intnodeValue;
StringcharValue;
publicTreeNode（intnodeValue,StringcharValue）
this.nodeValue=nodeValue;
this.charValue=charValue;
publicStringgetCharValue（）{
returncharValue;
publicvoidsetCharValue（StringcharValue）{
this.charValue=charValue;
publicTreeNodegetLeftNode（）{
returnleftNode;
publicvoidsetLeftNode（TreeNodeleftNode）{
this.leftNode=leftNode;
publicTreeNodegetRightNode（）{
returnrightNode;
publicvoidsetRightNode（TreeNoderightNode）{
this.rightNode=rightNode;
publicintgetNodeValue（）{
returnnodeValue;
publicvoidsetNodeValue（intnodeValue）{
this.nodeValue=nodeValue;
importjava.util.Scanner;
publicclassDijkstra{
privatestaticintn;
//G图中的顶点个数
privatestaticint[]distent=null;
//最短路径长度
privatestaticint[]previous=null;
//前驱顶点集合
publicstaticvoidDijkstras（intv,int[][]a,int[]dist,int[]prev）
{
//单元最短路径的Dijkstra算法
intn=dist.length-1;
if（v<
1||v>
n）return;
boolean[]s=newboolean[n+1];
//初始化
for（inti=1;
i<
=n;
i++）
dist[i]=a[v][i];
s[i]=false;
if（dist[i]==Float.MAX_VALUE）
prev[i]=0;
else
prev[i]=v;
dist[v]=0;
s[v]=true;
for（inti=1;
n;
i++）{
floattemp=Float.MAX_VALUE;
intu=v;
for（intj=1;
j<
j++）
if（（!
s[j]）&
（dist[j]<
temp））{
u=j;
temp=dist[j];
s[u]=true;
（a[u][j]<
Float.MIN_VALUE））
intnewdist=dist[u]+a[u][j];
if（newdist<
dist[j]）{
dist[j]=newdist;
prev[j]=u;
}}}
for（intk=2;
k<
k++）{
System.out.print（dist[k]+"
"
}System.out.println（dist[n]）;
publicstaticvoidmain（String[]args）{
//TODOAuto-generatedmethodstub
intv=1;
Scannersc=newScanner（System.in）;
System.out.println（"
请输入定点个数:
Stringline=sc.nextLine（）;
n=Integer.parseInt（line）;
distent=newint[n+1];
previous=newint[n+1];
inta[][]=newint[n+1][n+1];
请输入顶点的权重:
for（inti=1;
i<
i++）{
line=sc.nextLine（）;
String[]str=line.split（"
for（intj=1;
=str.length;
j++）{
a[i][j]=Integer.parseInt（str[j-1]）;
}}
Dijkstras（v,a,distent,previous）;
3.最小生成树
importjava.util.Arrays;
publicclassPrim{
privatestaticintMAX=100;
privatedoublecost[][]=newdouble[MAX][MAX];
privateArrayList<
Edge>
edge=newArrayList<
（）;
privateint[]near=newint[MAX];
privatestaticdoubleINFINITY=99999999.99;
//定义无穷大
privatedoublemincost=0.0;
//最小成本
privateintn;
//结点个数
publicPrim（）{}
publicstaticvoidmain（Stringargs[]）{
Primsp=newPrim（）;
sp.init（）;
sp.prim（）;
sp.print（）;
publicvoidinit（）{
Scannerscan=newScanner（System.in）;
intp,q,w;
System.out.println（"
spanningtreebegin!
Inputthenodenumber:
n=scan.nextInt（）;
//二维数组的填充要注意
for（inti=0;
MAX;
++i）{
Arrays.fill（cost[i],INFINITY）;
Inputthegraph（-1,-1,-1toexit）"
while（true）{p=scan.nextInt（）;
q=scan.nextInt（）;
w=scan.nextInt（）;
if（p<
0||q<
0||w<
0）{
break;
}cost[p][q]=w;
cost[q][p]=w;
}
Edgetmp=getMinCostEdge（）;
edge.add（tmp）;
p=tmp.start;
q=tmp.end;
mincost=cost[p][q];
for（inti=1;
if（cost[i][p]<
cost[i][q]）{
near[i]=p;
}else{
near[i]=q;
near[p]=near[q]=0;
//寻找最小成本的边
publicEdgegetMinCostEdge（）{
Edgetmp=newEdge（）;
doublemin=INFINITY;
for（intj=i+1;
++j）{
if（cost[i][j]<
min）{
min=cost[i][j];
tmp.start=i;
tmp.end=j;
}}
//System.out.println（min）;
returntmp;
//prim算法主体
publicvoidprim（）{
//找剩下的n-2条边
for（inti=2;
doublemin=INFINITY;
Edgetmp=newEdge（）;
for（intj=1;
if（near[j]!
=0&
cost[j][near[j]]<
tmp.start=j;
tmp.end=near[j];
min=cost[j][near[j]];
}
mincost+=cost[tmp.start][tmp.end];
edge.add（tmp）;
near[tmp.start]=0;
for（intk=1;
k<
++k）{
if（near[k]!
cost[k][near[k]]>
cost[k][tmp.start]）{
near[k]=tmp.start;
if（mincost>
=INFINITY）{
nospanningtree"
//打印结果
publicvoidprint（）{
edge.size（）;
Edgee=edge.get（i）;
the"
+（i+1）+"
thedge:
+e.start+"
---"
+e.end）;
classEdge
{
publicintstart;
//始边
publicintend;
//终边
}
五、[实验结果]
请输入一组数，中间用空格分隔：
0.010.030.070.130.190.260.31
输出结果为：
0.01:
01000码长：
5
0.03:
01001码长：
0.07:
0101码长：
4
0.13:
011码长：
3
0.19:
00码长：
2
0.26:
10码长：
0.31:
11码长：
24-2-4
246-1
58-35
-295-7
4-2-4
Inputthegraph（-1,-1,-1toexit）
1352
2351
3253
3214
-1-1-1-1
the1thedge:
2---3
the2thedge:
1---3
the3thedge:
0---0
升级会员 