5 Replies - 32579 Views - Last Post: 17 June 2010 - 05:55 PM Rate Topic: -----

#1 Manbearpig101  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 15
  • View blog
  • 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.io.FileReader;
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 {
        Scanner sc = new Scanner(new FileReader("C:/Users/Josh/Desktop/division_A/jungle_roads/jungle.in"));
        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++) {
                f.vertices.add(ALPHABET[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());
                    edgePool.add(e);
                }
            }
            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  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12189
  • View blog
  • Posts: 45,251
  • 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.
Was This Post Helpful? 1
  • +
  • -

#3 Manbearpig101  Icon User is offline

  • D.I.C Head
  • member icon

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

Re: Kruskal's algorithm java implementation

Posted 17 June 2010 - 04:19 PM

View Postmacosxnerd101, 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. =)
Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12189
  • View blog
  • Posts: 45,251
  • 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.
Was This Post Helpful? 0
  • +
  • -

#5 Manbearpig101  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 15
  • View blog
  • 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 ;)
Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12189
  • View blog
  • Posts: 45,251
  • 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.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1