public class UnionFind {
int [] parents;
int [] ranks;
public UnionFind(int size) {
parents = new int[size+1];
ranks = new int[size+1];
}
public void union(int index1, int index2) {
int temp1 = find(index1);
int temp2 = find(index2);
if(temp1 != temp2) link(temp1, temp2);
}
public void makeSet() {
for(int i = 0; i < parents.length; i++) {
parents[i] = i;
ranks[i] = 0;
}
}
private void link(int node1, int node2) {
if (ranks[node1] > ranks[node2]) parents[node2] = node1;
else {
parents[node1] = node2;
if (ranks[node1] == ranks[node2]) ranks[node2]++;
}
}
private int find(int index) {
return parents[index];
}
public int[] getTree() {
return parents;
}
}Naja das tue ich hier:
public void runOp() {
ArrayList<GraphNode> spanningTree = new ArrayList<>();
ArrayList<GraphNode> unusedNodes = graph.getAllNodes();
ArrayList<Integer> usedNodes = new ArrayList<>();
UnionFind s = new UnionFind(graph.numberOfNodes);
Collections.sort(unusedNodes);
while(!unusedNodes.isEmpty()) {
GraphNode current = unusedNodes.remove(0);
if(s.find(current.startNode) != s.find(current.endNode)) {
spanningTree.add(current);
s.link(s.find(current.startNode), s.find(current.endNode));
}
}
this.printSpanningTree(spanningTree);
}import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
public class Kruskal {
private Graph graph;
private double timeForTest = 0.0;
public long runOp() {
GraphArc [] arcs = new GraphArc[graph.numberOfArcs];
arcs = graph.getArray();
UnionFind s = new UnionFind(graph.numberOfNodes);
Arrays.sort(arcs);
long wayCost = 0;
for(int i = 0; i < arcs.length; i++) {
GraphArc current = arcs[i];
if(s.union(current.startNode, current.endNode)) {
wayCost += current.weight;
}
}
return wayCost;
}
public void readGraph(String filename) {
try {
BufferedReader in = new BufferedReader(new FileReader(filename));
String line = "";
String[] parts = null;
while((line = in.readLine()) != null) {
//System.out.println("Current Line: " + line);
if(line.charAt(0) == 'c') {
}else if(line.charAt(0) == 'p') {
parts = line.split(" ");
graph = new Graph(convertInt(parts[2]), convertInt(parts[3]));
}else if(line.charAt(0) == 'a') {
parts = line.split(" ");
//System.out.println(Arrays.toString(parts));
int start = convertInt(parts[1]);
int end = convertInt(parts[2]);
int weightNode = convertInt(parts[3]);
graph.add(start, end, weightNode);
//System.out.println(graph.toString());
}else {
System.out.println("This Character is not valid!!!");
}
}
//System.out.println(graph.toString());
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
private int convertInt(String input) {
return Integer.parseInt(input);
}
}public class UnionFind {
private int[] parents;
private int[] rank;
public UnionFind(int numberOfNodes) {
parents = new int[numberOfNodes+1];
rank = new int[numberOfNodes+1];
this.makeSet();
}
private void makeSet() {
for(int i = 0; i < parents.length; i++) {
parents[i] = i;
rank[i] = 0;
}
}
public boolean union(int value1, int value2) {
int temp1 = find(value1);
int temp2 = find(value2);
if(temp1 != temp2) {
link(temp1, temp2);
return true;
}
return false;
}
private void link(int value1, int value2) {
if (rank[value1] < rank[value2])
parents[value1] = value2;
else if (rank[value2] < rank[value1])
parents[value2] = value1;
else {
parents[value1] = value2;
rank[value2] += 1;
}
}
private int find(int value) {
return parents[value];
}
}import java.util.ArrayList;
public class Graph {
private ArrayList<ArrayList<GraphArc>> adjazenzlist;
private GraphArc[] arcs;
private int counter;
public int numberOfNodes;
public int numberOfArcs;
public Graph(int numberOfNodes, int numberOfPaths) {
adjazenzlist = new ArrayList<ArrayList<GraphArc>>();
arcs = new GraphArc[numberOfPaths];
counter = 0;
this.numberOfNodes = numberOfNodes;
this.numberOfArcs = numberOfPaths;
for(int i = 0; i < numberOfNodes+1; i++) {
adjazenzlist.add(new ArrayList<GraphArc>());
}
}
public void add(int startNode, int endNode, int weight) {
adjazenzlist.get(startNode).add(new GraphArc(startNode, endNode, weight));
arcs[counter] = new GraphArc(startNode, endNode, weight);
counter++;
}
public GraphArc[] getArray() {
return arcs;
}
public String toString() {
StringBuilder sb = new StringBuilder();
for(int i = 0; i < adjazenzlist.size(); i++) {
if(adjazenzlist.get(i).size() == 0) continue;
sb.append(i + ": ");
for(int j = 0; j < adjazenzlist.get(i).size(); j++) {
GraphArc s = adjazenzlist.get(i).get(j);
sb.append("(" + i + ", " + s.endNode + ", " + s.weight + ")");
if(j != adjazenzlist.get(i).size() - 1) {
sb.append(", ");
}
}
sb.append("\n");
}
return sb.toString();
}
}public class GraphArc implements Comparable<GraphArc>{
public int startNode;
public int endNode;
public int weight;
public GraphArc(int startNode, int endNode, int weight) {
this.startNode = startNode;
this.endNode = endNode;
this.weight = weight;
}
@Override
public int compareTo(GraphArc o) {
if(o.weight > this.weight) return -1;
else if(o.weight == this.weight) return 0;
else return 1;
}
public String toString() {
return "(" + this.startNode + ", " + this.endNode + ", " + this.weight + ")";
}
}import static org.junit.jupiter.api.Assertions.assertEquals;
import org.junit.jupiter.api.Test;
public class KruskalTest {
@Test
public void kruskalLastTest() {
Kruskal s = new Kruskal();
String directory = "/Users/userNameHere/Desktop/instances/";
s.readGraph(directory + "USA-road-d.NY.gr");
long result = s.runOp();
assertEquals(261159288, result, "Got " + result + " but expected 261159288!");
System.out.println("OK!");
s.readGraph(directory + "USA-road-d.BAY.gr");
result = s.runOp();
assertEquals(435798417, result, "Got " + result + " but expected 435798417!");
System.out.println("OK!");
s.readGraph(directory + "USA-road-d.COL.gr");
result = s.runOp();
assertEquals(1323900090, result, "Got " + result + " but expected 1323900090!");
System.out.println("OK!");
s.readGraph(directory + "USA-road-d.FLA.gr");
result = s.runOp();
assertEquals(1806814846, result, "Got " + result + " but expected 1806814846!");
System.out.println("OK!");
s.readGraph(directory + "USA-road-d.NW.gr");
result = s.runOp();
assertEquals(3522586810L, result, "Got " + result + " but expected 3522586810!");
System.out.println("OK!");
s.readGraph(directory + "USA-road-d.NE.gr");
result = s.runOp();
assertEquals(2131122758L, result, "Got " + result + " but expected 2131122758!");
System.out.println("OK!");
}
}private void link(int value1, int value2) {
int searchValue = 0;
int replaceValue = value2;
if (rank[value1] < rank[value2]) {
searchValue = value1;
replaceValue = value2;
parents[value1] = value2;
}else if (rank[value2] < rank[value1]) {
searchValue = value2;
replaceValue = value1;
}else {
searchValue = value1;
replaceValue = value2;
}
for(int i = 0; i < parents.length; i++) {
if(parents[i] == searchValue) {
parents[i] = replaceValue;
rank[replaceValue]++;
}
}
}Ach stimmt xD Da habe ich mich verwirrt xD Ich meinte etwas anderes xD Mir hat mal jemand erzählt das wohl in Netwerken wenn man nicht nur static routing sondern auch einen DHCP Part hat, das irgendwie da Minimum Spanning Tree verwendet wird oder so xD Oder hat ich das auch falsch im Gedächtnis?😵
