数据结构最小生成树克鲁晓夫法和普利姆算法分析总结
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数据结构最小生成树克鲁晓夫法和普利姆算法分析总结，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3666字，纯文字阅读大概需要6分钟。
内容图文
理论：
Prim：
基本思想：假设G＝(V，E)是连通的，TE是G上最小生成树中边的集合。算法从U＝{u0}（u0∈V）、TE＝{}开始。重复执行下列操作：
在所有u∈U，v∈V－U的边(u，v)∈E中找一条权值最小的边(u0,v0)并入集合TE中，同时v0并入U，直到V＝U为止。
此时，TE中必有n-1条边，T=(V，TE)为G的最小生成树。
Prim算法的核心:始终保持TE中的边集构成一棵生成树。
Kruskal：
假设连通网N＝（V，{E}）。则令最小生成树的初始状态为只有n个顶点而无边的非连通图T＝（V，{}），图中每个顶点自成一个连通分量。
在E中选择最小代价的边，若该边依附的顶点落在T中不同的连通分量中，则将该边加入到T中，否则舍去此边而选择下一条代价最小的边，依次类推，直到T中所有顶点都在同一连通分量上为止。
两者比较；
prim算法适合稠密图，其时间复杂度为O(n^2)，其时间复杂度与边得数目无关，而kruskal算法的时间复杂度为O(eloge)跟边的数目有关，适合稀疏图。
java实现
Vertex.java
package 图;
public class Vertex{
String value;
boolean isVisited;
Vertex(String value)
{
this.value=value;
this.isVisited=false;
}
public String getValue() {
return value;
}
public void setValue(String value) {
this.value = value;
}
public boolean isVisited() {
return isVisited;
}
public void setVisited(boolean isVisited) {
this.isVisited = isVisited;
}
}
Edge.java
package 图;
public class Edge{
Vertex start;
Vertex end;
int value;
public Vertex getStart() {
return start;
}
public void setStart(Vertex start) {
this.start = start;
}
public Vertex getEnd() {
return end;
}
public void setEnd(Vertex end) {
this.end = end;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
Edge(Vertex start,Vertex end, int value){
this.start=start;
this.end=end;
this.value=value;
}
}
Graph.java
package 图;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;
public class Graph {
public static List<Vertex> vertexList=new ArrayList<Vertex>();
public static List<Edge> EdgeQueue=new ArrayList<Edge>();
public static List<Vertex> newVertex=new ArrayList<Vertex>();
public static List<Edge> newEdge=new ArrayList<Edge>();
public static void buildGraph(){
Vertex a=new Vertex("a");
vertexList.add(a);
Vertex b=new Vertex("b");
vertexList.add(b);
Vertex c=new Vertex("c");
vertexList.add(c);
Vertex d=new Vertex("d");
vertexList.add(d);
Vertex e=new Vertex("e");
vertexList.add(e);
Vertex f=new Vertex("f");
vertexList.add(f);
addEdge(a, b, 3);
addEdge(a, e, 6);
addEdge(a, f, 5);
addEdge(b, a, 3);
addEdge(b, c, 1);
addEdge(b, f, 4);
addEdge(c, b, 1);
addEdge(c, d, 6);
addEdge(c, f, 4);
addEdge(d, c, 6);
addEdge(d, f, 5);
addEdge(d, e, 8);
addEdge(e, d, 8);
addEdge(e, f, 2);
addEdge(e, a, 6);
addEdge(f, a, 5);
addEdge(f, b, 4);
addEdge(f, c, 4);
addEdge(f, d, 5);
addEdge(f, e, 2);
}
public static void addEdge(Vertex start,Vertex end,int value){
Edge e=new Edge(start,end,value);
EdgeQueue.add(e);
}
public static boolean containVertex(Vertex v){
for(Vertex each:newVertex)
{
if(each.value.equals(v.value))
return true;
}
return false;
}
public static void prim(){
buildGraph();
Vertex start=vertexList.get(0);
newVertex.add(start);
for(int i=0; i<vertexList.size(); i++)
{
Vertex temp=new Vertex(start.value);
Edge tempEdge=new Edge(start, start, 1000);
for(Vertex v:newVertex)
{
for(Edge e:EdgeQueue)
{
if(e.start==v && !containVertex(e.end))
{
if(tempEdge.value>e.value)
{
tempEdge=e;
temp=e.end;
}
}
}
}
newVertex.add(temp);
}
Iterator<Vertex>i=newVertex.iterator();
while(i.hasNext())
{
Vertex v=i.next();
System.out.print(v.value+" ");
}
}
public static void kruskal(){
buildGraph();
sort();
}
public static void sort(){
Comparator<Edge>comparator=new Comparator<Edge>(){
@Override
public int compare(Edge e1, Edge e2) {
// TODO Auto-generated method stub
return e1.getValue()-e2.getValue();
}
};
Collections.sort(EdgeQueue,comparator);
}
public static void main(String[] args) {
prim();
}
}
原文：http://www.cnblogs.com/lyxcode/p/8025094.html
内容总结
以上是互联网集市为您收集整理的数据结构最小生成树克鲁晓夫法和普利姆算法分析总结全部内容，希望文章能够帮你解决数据结构最小生成树克鲁晓夫法和普利姆算法分析总结所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。