I'm learning minimum spanning trees and I encountered this question and decided to give it a shot...
Implement the minimum spanning tree algorithm on a randomly generated directed graph network of 100 vertices and 800 edges
public static int[][] getRandomArray(int n){
int[][] a = new int[n][n];
Random r = new Random();
for(int i = 0; i < a.length; i++){
for(int j = 0; j < a[i].length; j++){
a[i][j] = r.nextInt();
}
}
return a;
}
public static void main (String [] args)
{
int x[];
//TreeSet is used to sort the edges before passing to the algorithm
TreeSet<Edge> edges = new TreeSet<Edge>();
Random random = new Random();
edges.add(new Edge("0", "1", 2));
edges.add(new Edge("0", "3", 1));
edges.add(new Edge("1", "2", 3));
edges.add(new Edge("2", "3", 5));
System.out.println("Graph");
KEdges vv = new KEdges();
for (Edge edge : edges) {
System.out.println(edge);
vv.insertEdge(edge);
}
System.out.println("Kruskal algorithm");
int total = 0;
for (Edge edge : vv.getEdges()) {
System.out.println(edge);
total += edge.getEdgeWeight();
}
System.out.println("Total weight is " + total);
}
static class Edge implements Comparable<Edge>
{
String vertexA;
String vertexB;
int weight;
public Edge(String vertexA, String vertexB, int weight)
{
this.vertexA = vertexA;
this.vertexB = vertexB;
this.weight = weight;
}
public String getVertexA()
{
return vertexA;
}
public String getVertexB()
{
return vertexB;
}
public int getEdgeWeight()
{
return weight;
}
public String toString()
{
return "("+ vertexA + ", " + vertexB + ") : weight "+ weight ;
}
@Override
public int compareTo(Edge o) {
return (this.weight < o.weight)? -1 : 1;
}
}
static class KEdges
{
Vector<HashSet<String>> vertexGroups = new Vector<HashSet<String>>();
TreeSet<Edge> kruskalEdges = new TreeSet<Edge>();
public TreeSet<Edge> getEdges()
{
return kruskalEdges;
}
public HashSet<String> getVertexGroup(String vertex)
{
for (HashSet<String> vertexGroup : vertexGroups)
{
if (vertexGroup.contains(vertex))
{
return vertexGroup;
}
}
return null;
}
public void insertEdge(Edge edge)
{
String vertexA = edge.getVertexA();
String vertexB = edge.getVertexB();
HashSet<String> vertexGroupA = getVertexGroup(vertexA);
HashSet<String> vertexGroupB = getVertexGroup(vertexB);
if (vertexGroupA == null)
{
kruskalEdges.add(edge);
if (vertexGroupB == null){
HashSet<String> htNewVertexGroup = new HashSet<String>();
htNewVertexGroup.add(vertexA);
htNewVertexGroup.add(vertexB);
vertexGroups.add(htNewVertexGroup);
}
}
else{
if (vertexGroupB == null)
{
vertexGroupA.add(vertexB);
kruskalEdges.add(edge);
}
else if (vertexGroupA != vertexGroupB)
{
vertexGroupA.addAll(vertexGroupB);
vertexGroups.remove(vertexGroupB);
kruskalEdges.add(edge);
}
}
}
}
I'm stuck on how to generate the random edges and vertices... Any suggestions and ideas...