最小生成ツリーのkruskalアルゴリズムのjava実装を探します
18818 ワード
最小生成ツリーkruskalアルゴリズムのjava実装を探します
ここ数週間は試験に追われ、ここ数日は休みだったので、前回に続いて最小生成木の実現が今日まで延期されました.最小生成ツリーの実現リングに関する検出はここを見ることができる.
最小生成ツリーkruskalの考え方は以下の通りです.)図中のすべての辺を重みで小さいから大きいに並べ替えて、集合Gの中に置くと仮定して、結合Sは最小生成木を構成するために選択された辺を放して、最初は結合Sは空の集合 である.2)重みが最も小さいエッジが徐々に選択する、このエッジが既に選択されているエッジとリングを構成していない場合、Sセット中の に入れる.3)Sセットの辺の数がG(頂点数-1) になるまで、第2のステップを繰り返す.
思想はやはり比較的に簡単で、比較的に分かりやすくて、くだらない話は多く言わないで、直接コードに行きます辺の類は以下の である.頂点クラスは以下の である.判定ループのクラスは、以下の である.主関数クラスは以下の である.
上のコードの中の注釈は比較的に詳しく書いて、ここで詳しく説明しないで、後で私はやはり私たちのよくあるいくつかのアルゴリズムを実現することを堅持します.
ここ数週間は試験に追われ、ここ数日は休みだったので、前回に続いて最小生成木の実現が今日まで延期されました.最小生成ツリーの実現リングに関する検出はここを見ることができる.
最小生成ツリーkruskalの考え方は以下の通りです.
思想はやはり比較的に簡単で、比較的に分かりやすくて、くだらない話は多く言わないで、直接コードに行きます
package org.wrh.algorithmdemo;
//
public class Edge implements Comparable<Edge> {
/* * * */
private int src;
/* * * */
private int dest;
/* * * */
private int weight;
public Edge(int src, int dest,int weight) {
super();
this.src = src;
this.dest = dest;
this.weight=weight;
}
public int getSrc() {
return src;
}
public void setSrc(int src) {
this.src = src;
}
public int getDest() {
return dest;
}
public void setDest(int dest) {
this.dest = dest;
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
@Override
public int compareTo(Edge o) {
// TODO Auto-generated method stub
if(this.weight<o.weight)
return -1;
else if(this.weight>o.weight)
return 1;
else
return 0;
}
public String toString(){
return "("+src+","+dest+","+weight+")"+"
";
}
}
package org.wrh.algorithmdemo;
import java.util.Arrays;
import java.util.List;
//
public class Graph {
/* * * */
private int vertices_number;
/* * * */
private int edges_number;
/* * * */
private List<Edge> edges;
public Graph(){
}
public Graph(int vertices_number, int edges_number) {
super();
this.vertices_number = vertices_number;
this.edges_number = edges_number;
}
public int getVertices_number() {
return vertices_number;
}
public void setVertices_number(int vertices_number) {
this.vertices_number = vertices_number;
}
public int getEdges_number() {
return edges_number;
}
public void setEdges_number(int edges_number) {
this.edges_number = edges_number;
}
public List<Edge> getEdge() {
return edges;
}
public void setEdge(List<Edge> edge) {
this.edges = edge;
}
/* * ： , * * */
public Edge[] sort(){
Edge [] arrayEdge=new Edge[edges.size()];
for(int i=0;i<edges.size();i++){
arrayEdge[i]=edges.get(i);
}
Arrays.sort(arrayEdge);
return arrayEdge ;
}
@Override
public String toString() {
StringBuffer sb=new StringBuffer();
for(Edge edge:edges){
sb.append("(").append(edge.getSrc()).append(",").append(edge.getDest()).append(",").append(edge.getWeight()).append(")").append("
");
}
return new String(sb);
}
}
package org.wrh.algorithmdemo;
public class DisjuntSetCircle {
/* * true ， false * */
public static boolean isCycle(Graph graph,int[] parent) {
int num=graph.getEdge().size();
int src_represent;
int dest_represent;
for(int i=0;i<num;i++){
int src=graph.getEdge().get(i).getSrc();//
int dest=graph.getEdge().get(i).getDest();//
src_represent=find(parent,src);
//System.out.println("src="+src);
dest_represent=find(parent,dest);
//System.out.println("dest="+dest);
if(src_represent==dest_represent){// ， ， ， " "
return true;
}
else{// ，
union(parent,src_represent,dest_represent);
}
}
return false;
}
/* * * */
private static void union(int[] parent, int src, int dest) {
/* * " "， “ ” * */
parent[src]=dest;
}
/* * X " " * */
private static int find(int[] parent, int x) {
/* * x " -1"， -1， ， ， ； * -1， ， ， * */
if(parent[x]==-1){
return x;
}
return find(parent,parent[x]);
}
}
package org.wrh.kruskalalg;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import org.wrh.algorithmdemo.DisjuntSetCircle;
import org.wrh.algorithmdemo.Edge;
import org.wrh.algorithmdemo.Graph;
//kurskal java
/* * ： * 1) ， G ， S ， ， S * 2) ， ， S * 3) ， S G ( -1) * */
public class KurskalAlgorithm {
public static void main(String[] args) {
/* * * */
int vertices_num=9;
int edges_num=13;
/* * new Graph * */
Graph graph=new Graph(vertices_num,edges_num);
/* * edges_num Edge * */
List<Edge> edge=new ArrayList<Edge>();
edge.add(new Edge(0,1,4));
edge.add(new Edge(0,7,8));
edge.add(new Edge(1,7,11));
edge.add(new Edge(1,2,8));
edge.add(new Edge(2,3,7));
edge.add(new Edge(2,8,2));
edge.add(new Edge(2,5,4));
edge.add(new Edge(3,4,9));
edge.add(new Edge(3,5,14));
edge.add(new Edge(4,5,10));
edge.add(new Edge(5,6,2));
edge.add(new Edge(6,7,1));
edge.add(new Edge(6,8,6));
/* * * */
graph.setEdge(edge);// 4 4
/* * parent " "; * ： " " * * */
/* * ， * */
Edge[] arrEdges=graph.sort();
System.out.println(Arrays.toString(arrEdges));
int parent []=new int[vertices_num];
/* * -1， * */
for(int i=0;i<parent.length;i++){
parent[i]=-1;
}
graph=findMST(graph,arrEdges,parent);
System.out.println(" ："+graph);
}
/* * graph: * arrEdges: * parent: “ ” * */
private static Graph findMST(Graph graph, Edge[] arrEdges,int parent []) {
/* * edgesMST * */
List<Edge> edgeList=new ArrayList<Edge>();
/* * * */
edgeList.add(arrEdges[0]);
/* * new Graph * */
Graph graphMST=new Graph();
/* * for edgeList.size()<graph.getVertices_number() MST * */
for(int i=1;i<graph.getEdges_number()&&edgeList.size()<graph.getVertices_number();i++){
/* * * */
edgeList.add(arrEdges[i]);
System.out.println(" edgeList："+edgeList);
/* * ： parent , ， * isCircle find “ ” ， * * parent ， ， ， parent ， * ： * Graph graphTemp=new Graph();graphTemp.setEdge(new ArrayList(arrEdges[i]))； * for graphMST graphTemp ， * if(DisjuntSetCircle.isCycle(graphTemp,parent)){// ， System.out.println(" "+i+" "); edgeList.remove(arrEdges[i]); //graphMST.setEdge(edgeList);// MST } * */
for(int j=0;j<parent.length;j++){
parent[j]=-1;
}
graphMST.setEdge(edgeList);
if(DisjuntSetCircle.isCycle(graphMST,parent)){// ，
System.out.println(" "+i+" ");
edgeList.remove(arrEdges[i]);
//graphMST.setEdge(edgeList);// MST
}
}
return graphMST;
}
}
上のコードの中の注釈は比較的に詳しく書いて、ここで詳しく説明しないで、後で私はやはり私たちのよくあるいくつかのアルゴリズムを実現することを堅持します.