java - 避免在顶点之间创建多个边(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)，则问题会稍微复杂一些，但仍然很容易解决。

这些选项都不能生成距离大于 1 的无环图。这样做将需要更复杂的编码。