java - 随机游览生成问题

Question

我正在尝试从图表中生成随机游览。我正在使用邻接列表方法。

顶点有问题。当我将顶点添加到特定列表时，该顶点将添加到图中的所有列表中。我不懂为什么!代码如下:

public static void main(String[] args) {
    defaultData(6);
}

public static void defaultData(int n) {
    Integer costs[] = { 26, 95, 38, 74, 80, 73, 73, 92, 22, 97, 13, 81, 41,
      17, 4, 2, 47, 54, 21, 68, 78, 4, 77, 3, 66, 55, 99, 42, 62, 39, 8, 36,
      53, 74, 26, 8, 42, 66, 30, 58, 69, 14, 49, 39, 85, 98, 72, 3, 18, 99,
      96, 66, 64, 36, 17, 44, 70, 0, 8, 14, 62, 41, 84, 59, 94, 27, 5, 27,
      96, 10, 15, 52, 43, 20, 2, 86, 45, 43, 32, 17, 49, 92, 9, 15, 6, 49,
      72, 7, 51, 21, 2, 26, 63, 82, 98, 48, 21, 96, 16 };

    ArrayList<ArrayList<Integer>> costGraph = new ArrayList<>();
    ArrayList<ArrayList<Integer>> completeGraph = new ArrayList<>();

    Random rand = new Random(System.currentTimeMillis());

    int costIndex = 0;
    for (int i = 0; i <= n; i++) {
        ArrayList<Integer> cost = new ArrayList<>();
        ArrayList<Integer> edge = new ArrayList<>();

        for (int j = 0; j <= n; j++) {
            if (i == j) {
                continue;
            }

            edge.add(j);
            cost.add(costs[costIndex]);
            costIndex++;
        }

        completeGraph.add(edge);
        costGraph.add(cost);
    }

    System.out.println(completeGraph);

    ArrayList<ArrayList<Integer>> dummyGraph =
      (ArrayList<ArrayList<Integer>>)completeGraph.clone();
    ArrayList<ArrayList<Integer>> randomTour = new ArrayList<>();
    ArrayList<Integer> dummyList = new ArrayList<>();

    for (int i = 0; i <= n; i++) {
        randomTour.add(dummyList);
    }

    System.out.println(dummyGraph);

    int edgeCount = 0;
    Integer row = rand.nextInt(n);
    Integer start = row;

    while(edgeCount <= n-1){
        //dummyList = dummyGraph.get(row);

        // To keep the bounds of the random equal
        // to the new reduced size of the lists in the graph 
        Integer col = dummyGraph.get(row).get(rand.nextInt(n-edgeCount));

        randomTour.get(row).add(col);

        System.out.println(row);
        System.out.println(randomTour);

        edgeCount++;
        for(int k = 0; k < n; k++)
            dummyGraph.get(k).remove(row);
        row = col;
    }

    randomTour.get(row).add(start);
    System.out.println(randomTour);
}

如果您能及时回复，我将不胜感激。提前致谢!

Answer 1

您不想这样做:

for (int i = 0; i <= n; i++) {
    randomTour.add(dummyList);
}

它会多次添加相同的引用，因此 ArrayList 中的所有 ArrayList 实际上都是同一个对象。

相反，你想这样做:

for (int i = 0; i <= n; i++) {
    randomTour.add(new ArrayList<Integer>());
}

这样 ArrayList 中的 ArrayList 实例都是不同的。

我希望这个答案足够及时!