隨機生成邊和頂點

Question

我學習最小生成樹，我遇到了這個問題，並決定給它一個鏡頭...

實現最小隨機生成有向圖網絡上生成樹算法 100個頂點和800個邊緣

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); 
     } 
    } 
    } 

} 

我卡在如何生成隨機邊和頂點...... 任何建議和想法......

Answer 1

import java.util.Random; 

Random random = new Random(); 

Edge[] edges = new Edge[800]; 
for(int i = 0; i < edges.length; i++) { 
    edges[i] = new Edge(
     Integer.toString(random.nextInt(100)), 
     Integer.toString(random.nextInt(100))); 
     random.nextInt(300) //weights from 0 to 299 
    ); 
}