# Kruskal's algorithm java implementation

Page 1 of 1

## 5 Replies - 32861 Views - Last Post: 17 June 2010 - 05:55 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=178144&amp;s=741bae98209d3e1fe7a52ecef60cb3fd&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 Manbearpig101

Reputation: 15
• Posts: 62
• Joined: 17-June 10

# Kruskal's algorithm java implementation

Posted 17 June 2010 - 02:26 PM

I am unsure about adding edges, what conditions to use to reject/accept an edge.

Here is my current code:
```/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/

package a;

import java.io.FileNotFoundException;
import java.util.Collections;
import java.util.Scanner;
import java.util.ArrayList;

/**
* Using Kruskal's algorithm. Needs the actual algorithm implementation.
* @author Josh
*/
public class JungleRoads {

static String[] ALPHABET = new String[] {
"A", "B", "C", "D", "E",
"F", "G", "H", "I", "J",
"K", "L", "M", "N", "O",
"P", "Q", "R", "S", "T",
"U", "V", "W", "X", "Y",
"Z"
};

public static void main(String[] args) throws FileNotFoundException {
while (true) {
int villages = Integer.parseInt(sc.nextLine());
if (villages == 0) break;
ArrayList<Edge> edgePool = new ArrayList<Edge>();
Forest f = new Forest();
for (int i = 0; i < villages; i++) {
}
for (int i = 0; i < villages - 1; i++) {
String s = sc.nextLine();
Scanner scan = new Scanner(s);
String from = scan.next();
int iter = scan.nextInt();
for (int n = 0; n < iter; n++) {
Edge e = new Edge(from, scan.next(), scan.nextInt());
}
}
f.edges = (ArrayList<Edge>) edgePool.clone();
Collections.sort(edgePool);
Forest mst = new Forest();
//Add edges, this part is what I am unsure about
System.out.println(mst.getCost());
}
}

static class Forest {
public ArrayList<String> vertices;
public ArrayList<Edge> edges;
public Forest() {
vertices = new ArrayList<String>();
edges = new ArrayList<Edge>();
}
public int getCost() {
int N = 0;
for (Edge e : edges) {
N += e.cost;
}
return N;
}
}

static class Edge implements Comparable {
public String from;
public String to;
public int cost;
public Edge(String from, String to, int cost) {
this.from = from;
this.to = to;
this.cost = cost;
}
public int compareTo(Object o) {
Edge arg = (Edge) o;
if (cost == arg.cost) {
return 0;
} else if (cost > arg.cost) {
return 1;
} else if (cost < arg.cost) {
return -1;
}
return 0;
}
@Override
public String toString() {
return from + " TO " + to + " COSTS " + cost;
}
}
}

```

Is This A Good Question/Topic? 0

## Replies To: Kruskal's algorithm java implementation

### #2 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12324
• Posts: 45,424
• Joined: 27-December 08

## Re: Kruskal's algorithm java implementation

Posted 17 June 2010 - 03:34 PM

Maybe this animation will help you some. Basically, you are validating the following:
• Is there only one path to get to the vertex? If so, add the Edge.
• If not, is this the end of the shortest path to this vertex? If so, add the Edge.

Keep in mind that this is also a Greedy algorithm, so you are searching for the shortest path. To find the shortest path, you may also find Dijkstra's algorithm helpful here.

### #3 Manbearpig101

Reputation: 15
• Posts: 62
• Joined: 17-June 10

## Re: Kruskal's algorithm java implementation

Posted 17 June 2010 - 04:19 PM

macosxnerd101, on 17 June 2010 - 02:34 PM, said:

Maybe this animation will help you some. Basically, you are validating the following:
• Is there only one path to get to the vertex? If so, add the Edge.
• If not, is this the end of the shortest path to this vertex? If so, add the Edge.

Keep in mind that this is also a Greedy algorithm, so you are searching for the shortest path. To find the shortest path, you may also find Dijkstra's algorithm helpful here.

I just took another go at doing this, and I think (I need to test it with a couple more cases) I implemented the algorithm correctly. I didn't understand how to implement Dijkstra's algorithm with it, so I just keep on trying the ideas floating in my head. Thank you for the reply though. =)

### #4 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12324
• Posts: 45,424
• Joined: 27-December 08

## Re: Kruskal's algorithm java implementation

Posted 17 June 2010 - 04:24 PM

To utilize Dijkstra's algorithm, you're going to want to work with a sub-Graph within your forrest/main Graph. So for example, you start off at Edge in a rectangular Graph, and you need to find the shortest path to the opposite corner on the diagonal. You would use Dijkstra's algorithm to check the sum of the weights along either path to find the shortest.

Essentially, you are using it to find the shortest local paths on sub-Graphs on your main Graph to determine what Edges (not) to omit in your Minimum Spanning Graph.

### #5 Manbearpig101

Reputation: 15
• Posts: 62
• Joined: 17-June 10

## Re: Kruskal's algorithm java implementation

Posted 17 June 2010 - 04:53 PM

Is this just as a check, or is it in Kruskal's algorithm? It seems interesting though, a professor at a university was telling me about Dijkstra's algorithm, but now I forgot about it. I am going to look at it on wikipedia though

### #6 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12324
• Posts: 45,424
• Joined: 27-December 08

## Re: Kruskal's algorithm java implementation

Posted 17 June 2010 - 05:55 PM

In this implementation, Dijkstra's algorithm would be part of Kruskal's algorithm, specifically the "find the shortest path" step.