Hi
I was reading Robert Sedgewick´s "Algorithms in Java" and stumbled on the part about Graphs. I have never done much in this area and decided to try and implement some simple Prim, Kruskal and maybe Dijkstra.
The examples in the book are near to impossible to follow as Robert takes every effort to only use one letter variable and array names plus he implements his own small environment for algorithms, which I can't get a hold on... shame on You Robert!
Well, the very abstract steps in the Kruskal algorithm sounds simple at first:
Quote:Kruskal'’s algorithm works as follows: Take a graph with 'n' vertices, keep adding the shortest (least cost) edge, while avoiding the creation of cycles, until (n - 1) edges have been added. (NOTE: Sometimes two or more edges may have the same cost. The order in which the edges are chosen, in this case, does not matter. Different MSTs may result, but they will all have the same total cost, which will always be the minimum cost)
I made a weighted graph, composed by an ArrayList of n random points (Vertex(x, y), then I made an ArrayList with every possible edge, this is an Edge object containing start Vertex, end Vertex and weight (distance).
Now I sorted that ArrayList with respect to weight, ascending.
Ok, already and now what? The definition states that I start out by taking the Edges with the smallest weights, *that does not create a cycle* and add these to my minimum spanning tree until I added n-1 edges.
The part about not creating a cycle is what Im having a hard time realizing:
Code:
ArrayList vertices, edges;
int numOfVertex = 100;
void setup()
{
size(600, 500);
background(0);
stroke(255, 255, 255, 45);
strokeWeight(2);
fill(255, 255, 255, 100);
vertices = new ArrayList();
edges = new ArrayList();
for(int i = 0; i < numOfVertex; i++)
{
vertices.add(new Vertex(random(width), random(height))); //add the random vertices
Vertex v = (Vertex) vertices.get(i);
ellipse(v.x, v.y, 4, 4); //draw it to the screen
}
buildEdges();
drawEdges();
}
void buildEdges()
{
int currentVertex = 0;
while(currentVertex < numOfVertex) //first measure n weights, then n-1 weights and so on.
{
for(int i = currentVertex; i < numOfVertex-1; i++)
{
edges.add(new Edge((Vertex)vertices.get(currentVertex), (Vertex)vertices.get(i+1)));
}
currentVertex++;
}
Collections.sort(edges); //sort the edges so edges with smaller weights are first
}
void drawEdges()
{
for(int i = 0; i < numOfVertex; i++) //draw edges
{
Edge e = (Edge)edges.get(i);
line(e.start.x, e.start.y, e.end.x, e.end.y);
}
}
Code:
class Edge implements Comparable{
//Edges consists of a start Vertex, end Vertex and a weight
public Vertex start;
public Vertex end;
public float weight;
Edge(Vertex s, Vertex e)
{
start = s;
end = e;
weight = dist(s.x, s.y, e.x, e.y);
}
public int compareTo(Object edge) //overrides compareTo so I can use Collections to sort the edges
{
Edge n = (Edge) edge;
float w1 = weight;
float w2 = n.getWeight();
return w1 == w2 ? 0 : (w1 > w2 ? 1 : -1);
}
public float getWeight()
{
return weight;
}
}
Code:
class Vertex{
//Could use PVector, but this does just fine
public float x;
public float y;
Vertex(float _x, float _y)
{
x = _x;
y = _y;
}
}
Any help is appreciated :)
Pages: 1
Weighted graph Kruskal, next step help (Read 1656 times)