贪婪的算法破坏了实现

Question

我试图实现下面的贪婪算法，所以我试图遵循算法细节的要点，但我在IF语句中遇到了一个错误：java.lang.IndexOutOfBoundsException:Index:4，Size:4有人知道我应该如何处理以下方法吗？

1. 使用第一种颜色为第一个顶点着色

2. 对剩余的V-1顶点执行以下操作。

   a） 考虑当前拾取的顶点，并使用以前从未使用过的编号最低的颜色与其相邻的彩色顶点。如果所有以前使用的颜色出现在与v相邻的顶点上，为其指定新颜色。*/

public void greedy(LinkedHashMap<String, Node> nodes) {         
    ArrayList<Integer> colors = new ArrayList<Integer>();
    ArrayList<Integer> colorsUsed = new ArrayList<Integer>();
    nodes.entrySet().iterator().next().getValue().currentColor = 1; 
    colorsUsed.add(1);
    for (Map.Entry<String,Node> entry : nodes.entrySet()) {
        for (int i = 0; i < nodes.entrySet().size(); i++) {
            if(entry.getValue().edges.get(i).currentColor == 0) {
                //assign a color
                System.out.println(colors.get(i));
            }
        }
    }
}

Answer 1

您的嵌套循环没有多大意义，这是异常的原因（您在节点数而不是每个节点的边数处停止i，因此索引i超出集合entry.getValue().edges的边界）。

你可能应该更换

for (int i = 0; i < nodes.entrySet().size(); i++) {
                    ^^^^^^^^^^^^^^^^^^^^^^^
    if(entry.getValue().edges.get(i).currentColor == 0) {

使用类似的东西

for (int i = 0; i < entry.getValue().edges.size(); i++) {
                    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    if(entry.getValue().edges.get(i).currentColor == 0) {

（假设Node#edged实现java.util.List）

此外，colors.get(i)也没有多大意义。。。

Answer 2

IndexOutOfBoundsException告诉您，您的程序正试图访问ArrayList中无法访问的位置，因为该位置的大小小于索引。如果您想了解有关此异常的更多信息，请查看此处。

您应该检查您的代码，尤其是检查您的循环。