避免在顶点之间创建多条边(java.util、linkedList、Graph)

Question

 for(int i=0;i<k;i++)     {

         int numero2 = (int) (Math.random() * k);
         int numero3 = (int) (Math.random() * k);

         g.addEdge(numero2, numero3 );

     } 

提前谢了。特别是如果有一个答案，甚至更好，一个很好的答案来回答我的问题。

完整的代码是：

import java.util.*;
import java.util.Random;


class Graph{
    class Edge{
        int v;
        public Edge(int v){
            this.v=v;
        }
        @Override
        public String toString(){
            return "("+v+")";
        }
    }
    List<Edge> G[];
    public Graph(int n){
        G=new LinkedList[n];
        for(int i=0;i<G.length;i++)
            G[i]=new LinkedList<Edge>();
    }

    void addEdge(int u,int v){
        G[u].add(0,new Edge(v)); 
    }
    @Override
    public String toString(){
        String result="";
        for(int i=0;i<G.length;i++)
            result+=i+"=>"+G[i]+"\n";
        return result;
    }


}

    public class Graph01 {


    public static void main(String[] args) {

    int k = (int) (Math.random() * 5) + 5;          


     Graph g; 
     g = new Graph(k);

     for(int i=0;i<k;i++)     {

         int numero2 = (int) (Math.random() * k);
         int numero3 = (int) (Math.random() * k);

         g.addEdge(numero2, numero3 );

     }                                     


        System.out.println(g);


        }
}

Answer 1

有三种可能：

1. 生成一个随机边；如果该边存在，则生成不同边；重复，直到有所有需要的边
2. 预先枚举所有可能的边；从这个集合中随机选择边缘，并在“使用”它们时将它们从集合中删除。
3. 遍历所有节点，一次一个，生成n输出边，其中n符合您的要求。

在选项3中，如果你的边不是定向的，或者你想避免距离-1循环(A->B和B->a)，这个问题稍微复杂一点，但仍然很容易解决。