JAVA:Havel-Hakimi算法(判断数列是否可以表示图中顶点度数的算法)

Question

我想用 Java 编写一段代码，帮助您确定数字是否可以表示图中顶点的度数。我们在算法图论类(class)中被告知，有一种简单的方法可以使用如下所示的算法来解决该问题:

1. 你把数字按降序排列

   3,3,2,1
   

2. 然后你取最大的一个(在本例中为 3)，“删除它”(我猜是在数组中将其设置为零)然后从后面的 n 个数字中减去 1(n 等于值这个最大的数字，在这种情况下，你从以下 3 个数字中减去一个)

   0,2,1,0
   

如果需要，将数字重新降序排列并重复算法，删除最大的数字并从后面的 n 个数字中减去 1。

这样做直到你:

a) 遇到负数，在这种情况下，这意味着您的数字序列不能表示图中顶点的度数或

b) 你在算法的末尾，所有数字都是零，这意味着这些数字可以表示图中顶点的度数

对于这些特定的数字，它应该是这样的

3,3,2,1
0,2,1,0
0,0,0,-1

因为有 -1，这意味着这个数字序列不能表示图中顶点的度数。

到目前为止，我的算法代码和检查它是否完成看起来像这样(我已经有了带有扫描仪的主要方法，因此用户可以写下他想要了解的顶点数和度数，这个就是我不知道下一步该做什么的地方):

public void alg() {

        int size = this.vertices.length;
        do  {
            this.check();

            for (int i = 0; i < size; i++) {
                int biggest = i;
                int max = this.vertices[biggest];
                this.vertices[biggest] = 0; 

                for (int j = 0; j <= max + 1; j++) {
                    this.vertices[j+1]--;
                    System.out.println(Arrays.toString(this.vertices)); 
                    biggest++;
                } 

            }         
        } while (this.finished != true);
    }    

    public void check() {
        Integer[] zeroes = new Integer[this.vertices.length];
        Arrays.fill(zeroes, 0); //this probably isn't necessary
        int count = 0;
        for (int i = 0; i < this.vertices.length; i++) {
            if (this.vertices[i] < 0) {
                this.finished = true;
                System.out.println("not a graph");
            } 
            if(this.vertices[i] == 0) {
                count++;
            }
        }
        if (Arrays.equals(this.vertices, zeroes)) {
            System.out.println("a graph");
        }
    }

所以如果用户的数字序列是3,3,2,1，程序只会打印出这个，不会继续

[3, 3, 2, 1]
[0, 2, 2, 1]
[0, 2, 1, 1]
[0, 2, 1, 0]

我想我在循环中遗漏了一些东西，但我不知道是什么。提前感谢您的帮助!

Answer 1

问题似乎出在您内部的 for 循环中。在您的示例中，它从 j = 0 运行到 j = 4。

在循环内，您尝试访问 this.vertices[j+1]，这将是此循环结束时此数组的第 5 个条目。您应该在此处获得 Java 运行时的异常。

第二个问题是，您总是从数组的第一个索引开始。

尝试将此 for 循环更改为

for (int j = i+1; j <= max + i ; j++) {
        this.vertices[j]--;
        System.out.println(Arrays.toString(this.vertices)); 
        biggest++;
}