图DFS算法NullPointerException [英] Graph DFS Algorithm NullPointerException

问题描述

我只是简单地在java中学习，但是每次都显示eclipse显示错误 NullPointerException 。
我必须编写一个程序，它可以从文件（顶点）读取数据， ，接下来从这些数据中我应该计算图形大小，接下来我必须使用DFS算法来计算一致的组件。
我知道我的代码不好，但我仍然在学习java（和英文：P）。 >

test.txt

  0 1 0 4 
 1 2 1 4 1 5 1 8 1 11 
 2 6 
 3 1 3 7 
 4 8 
 5 2 5 8 
 6 5 6 7 6 9 
 8 4 
 9 5 9 7 
 10 8 10 11 
 11 8 11 9 11 12 
 12 3 12 6 12 9 
  

异常

 线程mainjava.lang中的异常.NullPointerException在Search.DFS上的
（Search.java:17）$在AppClient.main上的
（AppClient.java:25）
  

AppClient.class

  import java.io.BufferedReader; 
 import java.io.FileReader; 
 import java.io.IOError; 
 import java.io.IOException; 
 import java.nio.file.Path; 
 import java.nio.file.Paths; 
 import java.util.ArrayList; 
 import java.util.List; 
 import java.util.Scanner; 
 
 public class AppClient {
 
 private static final String filename =C：\\test.txt; 
 private static List< Integer> sizeGraphList = new ArrayList< Integer>（）; 
 private static List< Integer> numberOfVertex = new ArrayList< Integer>（）; 
 static图形图; 
静态搜索搜索; 
 
 public static void main（String [] args）throws IOException {
 
 graph = new Graph（getGraphSize（））; 
 addVertexToGraph（）; 
 search = new Search（）; 
 int result = search.DFS（）; 
 System.out.println（Składowe：+ result）; 
} 
 
 private static int getGraphSize（）throws IOException {
 String Path = filename; 
 
路径filePath = Paths.get（Path）; 
 Scanner in =新扫描仪（filePath）; （in.hasNext（））{
 if（in.hasNextInt（））{
 sizeGraphList.add（in.nextInt（））; 
 
 while（in.hasNext（）） 
} else {
 in.next（）; 
 
 
 
（Integer x：sizeGraphList）{
 System.out.println（x）; 
} 
 
 int sizeGraph = getSizeOfVertex（sizeGraphList）; 
 System.out.println（Size：+ sizeGraph）; 
返回sizeGraph; 
 
 
 private int int getSizeOfVertex（List< Integer> listOfVertex）{
 
 for（int i = 0; i< listOfVertex.size（）; i ++ ）{
 numberOfVertex.add（listOfVertex.get（i））; （int j = 1; j< numberOfVertex.size（）; i ++）{
} ）; j ++）{
 if（i！= j&&& amp; numberOfVertex.get（i）== numberOfVertex.get（j））{
 numberOfVertex.remove（j）; 
} 
} 
} 
 
 int size = numberOfVertex.size（）; 
返回大小; 
 
 
 private static void addVertexToGraph（）{
 try（BufferedReader br = new BufferedReader（new FileReader（filename）））{
 
 String line = br.readLine（）; 
 
 while（line！= null）{
 // String [] edge = line.trim（）。split（[^ \\d] +）; 
 String [] edge = line.trim（）。split（\\s +）; 
 
 for（int i = 0; i  int v = Integer.parseInt（edge [i]）; 
 int u = Integer.parseInt（edge [i + 1]）; 
 //System.out.println(v +，+ u）; 
 graph.addEdge（v，u）; 
} 
 
 line = br.readLine（）; 
} 
 
} catch（IOException e）{
 System.out.println（File does not exist !!!）; 
} 
} 
} 
  

Graph.class

  import java.util.ArrayList; 
 import java.util.LinkedList; 
 import java.util.List; 
 
 class图{
 
 
 public List< LinkedList< Integer>> graphVertices; 
 public int []处理范围; 
 
 
 
图（int graphSize）{
 
 graphVertices = new ArrayList<>（）; 
 processingRange = new int [graphSize + 1]; （i，new LinkedList< Integer>（））; 
 for（int i = 0; i  graphVertices.add 
} 
} 
 
 void addEdge（int v，int u）{
 LinkedList< Integer> list = graphVertices.get（v）; 
 list.add（u）; 
 graphVertices.set（v，list）; 
} 
} 
  

Search.class

  import java.util.LinkedList; 
 import java.util.List; 
 import java.util.Stack; 
 
 public class Search AppClient {
 
 private Stack< Integer> vertexesStack; 
 private int range; 
 private int scc; 
图形图形; 
 
 public搜索（）{
 
} 
 
 int DFS（）{
布尔值visited [] =新布尔值[graph.graphVertices .size（）+ 1]; 
 for（int i = 0; i< graph.graphVertices.size（）; i ++）
 if（！visited [i]）{
 dfsSearch（i，visited）; 
} 
返回scc; 
 
 
 private void dfsSearch（int v，boolean visited []）{
 graph.processingRange [v] = range ++; 
 visited [v] = true; 
 vertexesStack.push（v）; 
 if（！checkDistance（v，visited））{
 int top; 
 do {
 top = vertexesStack.pop（）; 
 graph.processingRange [top] = graph.graphVertices.size（）; 
} while（top！= v）; 
 scc ++; 
 
 
 
 private布尔型checkDistance（int v，boolean [] visited）{
 int minRange = graph.processingRange [v]; 
 
（int vertex：graph.graphVertices.get（v））{
 
 if（！visited [vertex]）{
 dfsSearch（vertex，visited） ; 
} 
 
 if（graph.processingRange [vertex]< minRange）{
 minRange = graph.processingRange [vertex]; （minRange< graph.processingRange [v]）{
 graph.processingRange [v] = minRange; 
} 
} 
 if 
返回true; 
} 
返回false; 
 
 
 
 $ div $解析方案

你没有在 AppClient.java



<$ p中初始化 search $ p> addVertexToGraph（）;
search = new Search（）; //添加这个
int result = search.DFS（）; //可能在这里添加图作为参数


也初始化 vertexesStack > Search.java ，并删除本地变量图，因为您要引用 c $ c> AppClient.java

  private Stack< Integer> vertexesStack = new Stack<>（）; //添加这个
 private int range; 
 private int scc; 
 //图形图形; //删除这个
  

因为你的代码没有 package xyz; 您可能还需要更改 int DFS（） - > int DFS（图形图表），然后在 AppClient.java 中传递给您对 DFS（）

的调用。

I have simply exercises to school in java but eclipse all time display error NullPointerException.
I must write a program which can read data from file (vertex), next from this data I should count graph size and next I must use DFS algorithm to count consistent components.
I know that my code is not good but I am still learning java (and english :P ).

test.txt

0 1 0 4
1 2 1 4 1 5 1 8 1 11
2 6
3 1 3 7
4 8
5 2 5 8
6 5 6 7 6 9
8 4
9 5 9 7
10 8 10 11
11 8 11 9 11 12
12 3 12 6 12 9

Exception

Exception in thread "main" java.lang.NullPointerException
    at Search.DFS(Search.java:17)
    at AppClient.main(AppClient.java:25)

AppClient.class

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOError;
import java.io.IOException;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class AppClient {

    private static final String filename = "C:\\test.txt";
    private static List<Integer> sizeGraphList = new ArrayList<Integer>();
    private static List<Integer> numberOfVertex = new ArrayList<Integer>();
    static Graph graph;
    static Search search;

    public static void main(String[] args) throws IOException {

        graph = new Graph(getGraphSize());
        addVertexToGraph();
        search = new Search();
        int result = search.DFS();
        System.out.println("Składowe: " + result);
    }

    private static int getGraphSize() throws IOException {
        String Path = filename;

        Path filePath = Paths.get(Path);
        Scanner in = new Scanner(filePath);

        while (in.hasNext()) {
            if (in.hasNextInt()) {
                sizeGraphList.add(in.nextInt());
            } else {
                in.next();
            }
        }

        for (Integer x : sizeGraphList) {
            System.out.println(x);
        }

        int sizeGraph = getSizeOfVertex(sizeGraphList);
        System.out.println("Size: " + sizeGraph);
        return sizeGraph;
    }

    private static int getSizeOfVertex(List<Integer> listOfVertex) {

        for (int i = 0; i < listOfVertex.size(); i++) {
            numberOfVertex.add(listOfVertex.get(i));
        }

        for (int i = 0; i < numberOfVertex.size(); i++) {
            for (int j = 1; j < numberOfVertex.size(); j++) {
                if (i != j && numberOfVertex.get(i) == numberOfVertex.get(j)) {
                    numberOfVertex.remove(j);
                }
            }
        }

        int size = numberOfVertex.size();
        return size;
    }

    private static void addVertexToGraph() {
        try (BufferedReader br = new BufferedReader(new FileReader(filename))) {

            String line = br.readLine();

            while (line != null) {
                // String[] edge = line.trim().split("[^\\d]+");
                String[] edge = line.trim().split("\\s+");

                for (int i = 0; i < edge.length - 1; i += 2) {
                    int v = Integer.parseInt(edge[i]);
                    int u = Integer.parseInt(edge[i + 1]);
                    //System.out.println(v + ", " + u);
                    graph.addEdge(v, u);
                }

                line = br.readLine();
            }

        } catch (IOException e) {
            System.out.println("File does not exist!!!");
        }
    }
}

Graph.class

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

class Graph {


    public List<LinkedList<Integer>> graphVertices;
    public int[] processingRange;



    Graph(int graphSize) {

        graphVertices = new ArrayList<>();
        processingRange = new int[graphSize+1];
        for (int i = 0; i < graphSize; i++) {
            graphVertices.add(i, new LinkedList<Integer>());
        }
    }

    void addEdge(int v, int u) {
        LinkedList<Integer> list = graphVertices.get(v);
        list.add(u);
        graphVertices.set(v, list);
    }
}

Search.class

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class Search extends AppClient{

    private Stack<Integer> vertexesStack;
    private int range;
    private int scc;
    Graph graph;

    public Search() {

    }

    int DFS() {
        boolean visited[] = new boolean[graph.graphVertices.size()+1];
        for (int i = 0; i < graph.graphVertices.size(); i++)
            if (!visited[i]) {
                dfsSearch(i, visited);
            }
        return scc;
    }

    private void dfsSearch(int v, boolean visited[]) {
        graph.processingRange[v] = range++;
        visited[v] = true;
        vertexesStack.push(v);
        if (!checkDistance(v, visited)) {
            int top;
            do {
                top = vertexesStack.pop();
                graph.processingRange[top] = graph.graphVertices.size();
            } while (top != v);
            scc++;
        }
    }

    private boolean checkDistance(int v, boolean[] visited) {
        int minRange = graph.processingRange[v];

        for (int vertex : graph.graphVertices.get(v)) {

            if (!visited[vertex]){
                dfsSearch(vertex, visited);
            }

            if (graph.processingRange[vertex] < minRange) {
                minRange = graph.processingRange[vertex];
            }
        }
        if (minRange < graph.processingRange[v]) {
            graph.processingRange[v] = minRange;
            return true;
        }
        return false;
    }
}

解决方案

You didn't initialize search in AppClient.java

addVertexToGraph();
search = new Search(); // add this
int result = search.DFS(); //possibly add graph as a parameter here

also initialize vertexesStack in Search.java and delete the local variable graph since you want to reference the one in AppClient.java

private Stack<Integer> vertexesStack = new Stack<>(); // add this
private int range;
private int scc;
// Graph graph; // delete this

Since your code didn't have package x.y.z; at the top you may also need to change int DFS() -> int DFS(Graph graph) and then in AppClient.java pass in the graph to your call to DFS()

这篇关于图DFS算法NullPointerException的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！