使用 java 中的列表列表

Question

我正在编写一个代码，理论上应该采用具有多个顶点、边和边列表的图的文本文件表示，并使用深度优先搜索来确定它是否是二分图。但是，我正在使用列表的 Arraylist 来存储邻接列表，并且我不断收到 java.lang.IndexOutOfBoundsException: Index: 1, Size: 0 error at the for loop in the childColor method

import java.io.File;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.*;
import static java.lang.System.*;
import java.util.*;

public class detect_bipartite {
    public static void main(String[] args){
        int bipartCheck = 1;
        List<Integer> numList = new ArrayList<Integer>();   
        File inFile = null;
        //separate white space
        if (0 < args.length) {
            inFile = new File(args[0]);
        }        

        BufferedReader reader = null;
        try {
            reader = new BufferedReader(new FileReader(inFile));
            String text = null;

            while ((text = reader.readLine()) != null) {
                String[] tmp = text.split(" ");
                for(String str: tmp)
                    if(!str.equals("")){
                        numList.add(Integer.parseInt(str));}

            }
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            try {
                if (reader != null) {
                    reader.close();
                }
            } catch (IOException e) {
            }
        }

        int n = numList.get(0);
        int m = numList.get(1);

        List<Integer> edgeA = new ArrayList<Integer>();
        List<Integer> edgeB = new ArrayList<Integer>();

        for(int i=2; i<numList.size(); i++){
            if(i%2==0){edgeA.add(numList.get(i));}
            else if(i%2==1){edgeB.add(numList.get(i));}
        }

        List<List<Integer>> adjLists = new ArrayList<List<Integer>>(n);
        for(int j = 1; j <= adjLists.size(); j++){      //get adjacency lists
            for(int a=1; a <=edgeA.size(); a++){
                if(edgeA.get(a)==j){ (adjLists.get(j)).add(edgeB.get(a));}
                if(edgeB.get(a)==j){ (adjLists.get(j)).add(edgeA.get(a));}
            }
        }

        int[] color = new int[n];
        Arrays.fill(color, 0);
        //0 = uncolored
        //1 = red
        //2 = blue

        int bipart = childColor(n, 1, adjLists, color, 1);
        if (bipart==0){bipartCheck = 0;}

        for(int d = 0; d < n; d++)      //for any disconnected graphs
        {
            if(color[d] == 0){
                bipart = childColor(n, d, adjLists, color, 1);}
            if (bipart==0){bipartCheck = 0;}
        }


        if(bipartCheck == 1){
            System.out.println("Bipartite");
        } else{
            System.out.println("Not a Bipartite");
        }
    }

    public static int childColor(int n, int node, List<List<Integer>> adjLists, int[] color, int nodeColor){
        if(color[node] == nodeColor){
            return 1;}
        int bipart = 1;
        int newColor;
        if(nodeColor == 1){newColor = 2;}
        else{newColor = 1;}
        if(color[node] == newColor)
        {return 0;}
        color[node] = nodeColor;
        for(int k = 0; k < adjLists.get(node).size(); k++){  **//This is the error line**
            bipart = childColor(n, adjLists.get(node).get(k), adjLists, color, newColor);
            if(bipart == 0)
            {return 0;}
        }

        return bipart;
    }
}

Answer 1

当你这样做时：

List<List<Integer>> adjLists = new ArrayList<List<Integer>>(n);

您创建了一个初始容量为 n 的 ArrayList。虽然，但这并不意味着列表的大小为n。事实上，由于列表没有元素，它的大小为 0。假设 1 <= 0 是 false 并且永远不会执行此循环：

for(int j = 1; j <= adjLists.size(); j++){      //get adjacency lists
    for(int a=1; a <=edgeA.size(); a++){
        if(edgeA.get(a)==j){ (adjLists.get(j)).add(edgeB.get(a));}
        if(edgeB.get(a)==j){ (adjLists.get(j)).add(edgeA.get(a));}
    }
}

因此，当您调用 childColor(n, 1, adjLists, color, 1) 时，adjLists 为空 。当您尝试通过执行 adjLists.get(node) 访问索引 1 处的元素时，没有元素，因此 IndexOutOfBoundsException.

另请注意，Java 列表和数组索引从 0 开始，而不是 1。

要解决这个问题，您可以在尝试使用之前初始化所有列表：

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

使用 java 中的列表列表

using a list of lists in java

java

multidimensional-array

arraylist

indexoutofboundsexception