Kruskal算法:

 

MST_kruskal_en

 

 

public class Kruskal {
public class data{
public int start;//开始点
public int end;//结束点
public int val;
data(){
start = 0;
end = 0;
val  = Integer.MAX_VALUE;
}
public void printout(){
System.out.println(start +"---"+ end+" val:"+val);
}
}
public void kruscal(int graph[][]){
int n = graph.length;
data []edges = new data[n * (n-1) /2];//生成n*(n-1)/2条边的存储对象
int edgeCount = 0;//边数最多n * (n-1) /2
for (int i = 0; i < graph.length; i++) {
for (int j = i+1; j < graph.length; j++) {
if (graph[i][j] > 0 && graph[i][j] < Integer.MAX_VALUE){
edges[edgeCount] = new data();
edges[edgeCount].start = i;
edges[edgeCount].end = j;
edges[edgeCount].val = graph[i][j];
edgeCount++;
}
}
}
sortEdges(edges, 0, edgeCount-1);
ArrayList<data> result = kruscalMst(edges, edgeCount,n);
//  printEdges(result);
}
/**
*
* 根据已经排好序的边,以不成环为原则,选出前n-1条边
* */
public ArrayList<data> kruscalMst(data[] edges, int count, int vertex) {
ArrayList<data> edge = new ArrayList<data>();
LinkedList<HashSet<Integer>> u = new LinkedList<HashSet<Integer>>();
//初始化
for (int i = 0; i < vertex; i++) {
u.add(new HashSet<Integer>());
u.get(i).add(i);//集合0是a0,集合1是a1,集合2是a2
}
for (int i = 0; i < count; i++) {
if(!inSameSet(u,edges[i])){
edge.add(edges[i]);
}
}
return edge;
}
/**
* 判断边edge中的两个点,是否已经在一个集合中
* */
private boolean inSameSet(LinkedList<HashSet<Integer>> u, data edge) {
int start = edge.start;
int end = edge.end;
int together1 = -1;
int together2 = -1;
for (HashSet<Integer> set : u){
if(set.contains(start) ){
together1 = u.indexOf(set);
}
if(set.contains(end) ){
together2 = u.indexOf(set);
}
}
if (together1 != together2){
u.get(together1).addAll(u.get(together2));//第二个集合放到第一个集合中
u.remove(together2);//删除第二个集合
return false;
}else{
return true;
}
}
private void printEdges(ArrayList<data> edges) {
for (data d :edges) {
d.printout();
}
}
/**
* quick sort,按边的权值排序
* */
private void sortEdges(data[] edges, int left, int right) {
if (left < right){
int i = left;
int j =right;
int tmp = edges[left].val;
int tmpStart = edges[left].start;
int tmpEnd = edges[left].end;
while (i < j){
while (i < j && tmp <= edges[j].val)
j--;
if (i < j){
edges[i].val = edges[j].val;
edges[i].start = edges[j].start;
edges[i].end = edges[j].end;
i++;
}
while (i < j && tmp > edges[i].val)
i++;
if (i < j){
edges[j].val = edges[i].val;
edges[j].start = edges[i].start;
edges[j].end = edges[i].end;
j--;
}
}
edges[i].val = tmp;
edges[i].start = tmpStart;
edges[i].end = tmpEnd;
sortEdges(edges , left, i-1);
sortEdges(edges, i+1, right);
}
}
}

 

 

 

Prim算法:

Prim-algorithm-animation-2

 

 

 

/**
* Created by chris on 15/5/2.
* 求最小生成树的辅助类
*/
public class Closedge {
private  int lowcost;//最小权值
private  int vertex;
Closedge(){
vertex = 0;
lowcost = Integer.MAX_VALUE;
}
public int getLowcost() {
return lowcost;
}
public int getVertex() {
return vertex;
}
public void setLowcost(int lowcost) {
this.lowcost = lowcost;
}
public void setVertex(int vertex) {
this.vertex = vertex;
}
}
package com.company;
import java.util.ArrayList;
/**
* Created by chris on 15/5/1.
* Prim algorithm
*/
public class Prim {
/**
*   Prim 最小生成树算法,
* @param adjMatrix 临接矩阵表示图
* @param u 存储生成的最小树,初始值输入是一个起点
* @param closedge 辅助,用来存放某点点最低权值
* */
void miniSpanTreePrim(int adjMatrix[][], ArrayList<Integer> u, Closedge closedge[]){
closedge[u.get(0)].setLowcost(0);//初始化,u只有一个点,设置这个点的最低权值是 0
for (int i = 0; i < adjMatrix.length; i++) {
if (i != u.get(0)) {
closedge[i].setVertex(u.get(0));//对v-u中的顶点i,初始化closedge[i]
closedge[i].setLowcost(adjMatrix[u.get(0)][i]);
}
}
for (int i = 1; i <= adjMatrix.length-1; i++) {//找 n-1条边
int minVertex = minimumOfCloseEdge(closedge);//找相邻边中,最小权值的点
u.add(minVertex);
//System.out.println(closedge[minVertex].getVertex() +"---"+ minVertex);
closedge[minVertex].setLowcost(0);
//在 minVertex并入 u 点后,更新closedge[i]
for (int j = 0; j < adjMatrix.length; j++) {
//如果u中不包含 j 点,就看刚才添加到u中的minVertex点到j点的权值是否更小
if (!u.contains(j)
&& adjMatrix[minVertex][j]!=0
&& adjMatrix[minVertex][j] < closedge[j].getLowcost() ){
closedge[j].setLowcost(adjMatrix[minVertex][j]);
closedge[j].setVertex(minVertex);
}
}
}
// printArrayList(u);
}
/**
* 输出集合中vertex的顺序
* */
private void printArrayList(ArrayList<Integer> u) {
for (Integer i : u){
System.out.print(i + ",");
}
System.out.println();
}
/**
* 找到辅助数组中的最小正数
* */
private int minimumOfCloseEdge(Closedge[] closedge) {
int min = closedge[0].getLowcost();
int minPos = 0;
for (int i = 1; i < closedge.length; i++) {
if (min == 0 && closedge[i].getLowcost()!=0
|| closedge[i].getLowcost()!=0 && min > closedge[i].getLowcost()){
minPos = i;
min = closedge[i].getLowcost();
}
}
return minPos;
}
}

 



分类: Java开发算法

发表评论

电子邮件地址不会被公开。 必填项已用*标注