, используя список списков в java

Question

Я пишу код, который теоретически должен взять текстовое представление файла с числом вершин, ребер и списка ребер и использовать поиск по глубине для определения если он двудольный. Однако я использую Список_массивы списков для хранения списков смежности, и я получаю java.lang.IndexOutOfBoundsException: Индекс: 1, Размер: 0 Ошибки на цикл в методе childColor

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); 

Вы создаете ArrayList с начальной емкостью n. Это не значит, что список имеет размер 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 пуст. Когда вы пытаетесь получить доступ к элементу по индексу 1, делая adjLists.get(node), нет элемента, поэтому IndexOutOfBoundsException.

отметить также, что Java списки и индексы массивов начинаются с 0, а не 1.

Чтобы решить эту проблему, можно инициализировать все списки, прежде чем пытаться использовать их:

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