Java - NullPointerException в Graph.java

Question

Я пытаюсь создать неориентированный граф, который читается из текстового файла. Однако я продолжаю получать исключение NullPointerException. Это мой Graph класс:

Graph.java:

package testalgo; 

    import java.io.File; 
    import java.util.ArrayList; 
    import java.util.HashMap; 
    import java.util.LinkedList; 
    import java.util.List; 
    import java.util.Scanner; 


    public class Graph 

    { 


      ArrayList<Integer> vertices = new ArrayList<Integer>(); 
      HashMap<Integer, LinkedList<Integer>> adj; 
      static Scanner sc; 
      public Graph(ArrayList<Integer> verts){ 

        adj =new HashMap<Integer, LinkedList<Integer>>(); 
      } 

      public static void main(String[] args) { 

       try{ 
       sc = new Scanner(new File("graph1.txt")); 
       } 
       catch(Exception e){ 

        System.out.println(e); 
       } 

       while(sc.hasNext()){ 

        int a = Integer.parseInt(sc.next()); 
        int b = Integer.parseInt(sc.next()); 
        Graph g = new Graph(new ArrayList<Integer>()); 
        g.addVertex(a); 
        g.addeEgde(a, b); // this is line 46 
        g.addeEgde(b, a); 


       } 

       sc.close(); 
      } 

      public void addVertex(int v){ 


       for (int i = 1; i < vertices.size(); ++i) { 
       adj.put(i, new LinkedList<Integer>());} 

      } 

      public void addeEgde(int v1, int v2) { 

       adj.get(v1).add(v2); // this is line 68 
      } 

      public List<Integer> getNeighbors(int v) { 
       return adj.get(v); 
     } 
    } 

И это сообщение об ошибке, что я получаю:

Exception in thread "main" java.lang.NullPointerException 
    at testalgo.Graph.addeEgde(Graph.java:68) 
    at testalgo.Graph.main(Graph.java:46) 

Спасибо за вашу помощь!

Answer 1

Я не вижу нигде в вашем коде, где вы заполняете карту adj с помощью v в качестве ключа. Следовательно, adj.get(v1) вернет null. Вы только объявили adj; вам также нужно заполнить его.

Все, что я вижу:

for (int i = 1; i < vertices.size(); ++i) { 
    adj.put(i, new LinkedList<Integer>()); 
} 

Поскольку vertices пуст, чтобы начать с того, что вы не будете вставлять что-либо в вашей карте.

вы имели в виду:

adj.put(v, new LinkedList<Integer>()); 

вместо этого?

В ответ на ваш комментарий: вам нужно добавить еще одну запись для b в списке смежности:

g.addVertex(a); 
g.addVertex(b); // <--- you need this as well 
g.addeEgde(a, b); 
g.addeEgde(b, a); // <--- otherwise you'll get a NPE here 

Answer 2

Вы, вероятно, вызывается addeEdge без добавив любой vertex как

for (int i = 1; i < vertices.size(); ++i) 
{ 
    adj.put(i, new LinkedList<Integer>()); 
} 

Will не поставить LinkedList экземпляр в adj (vertices.size() is 0).

Поэтому

adj.get(v1).add(v2); 

кинет NullPointerException как adj.get(v1) возвратит null и вы вызываете add на null.

Try объявляя:

private static int count = 0; 

В теле класса, а затем, в addVertex:

adj.put(count++, new LinkedList<Integer>()); 

Это один поставит новый LinkedList в вашем Map каждый раз, когда addVertex вызывается.

В качестве альтернативы, для индекса карты:

public void addVertex(int vertexIndex) 
{ 
    adj.put(vertexIndex, new LinkedList<Integer>()); 
} 

Кроме того, убедитесь, что adj.get(v1) не будет аннулирована, сделав нулевое сравнение перед обращением add на него:

LinkedList<Integer> vertex = adj.get(v1); 
if(vertex != null) 
{ 
    vertex.add(v2); 
} 

Кроме того, cosider что g.addeEgde (b, a); применяется к вершине, которая не существует, и будет также источником NullPointerException.

UPDATE: В случае, если вы пытаетесь вставить значения в последовательности (последовательный индекс), используя Map для вершин не в основном эффективный способ сделать это (требуется O(logn) время сложность индексации). Я полагаю, что вы используете ArrayList вместо:

ArrayList<LinkedList<Integer>> adj; 

И в вашем AddVertex:

adj.add(new LinkedList<Integer>()); 

И при индексировании:

adj.get(yourIndex); 

Это один будет гораздо более эффективным (занимает O(1) сложность время в индексировании).

ОБНОВЛЕНИЕ 2: Если ваш случай представляет собой список смежности, который, вероятно, лучше, то Map лучше использовать, чем ArrayList, так как у вас нет последовательной индексации. Имейте в виду, что вы должны добавить вершины по значению смежности и НЕ последовательную индексацию, как Vivin Paliath.

Answer 3

Это больше обзора комментария кода, но:

1. Форматирование - ваш IDE может это сделать (если вы используете один ..).
2. Использование списка, а не ArrayList, и карта, а не Hashmap, так HashMap<Integer, LinkedList<Integer>> adj; становится Map<Integer, List<Integer>>
3. Имя метода addeEgde - c'mon!
4. Вы фактически не используете ArrayList<Integer>, который вы передаете конструктору Graph - вам это действительно нужно?

Из опыта реализации (слишком много) объектов графа вы можете подумать о том, как вы могли бы использовать фиксированную матрицу int вместо подхода списка смежности. Обе реализации могут быть полезны, но в разных обстоятельствах.