java - 图 DFS 算法 NullPointerException

Question

我在java中进行了简单的练习，但是eclipse总是显示错误NullPointerException。
我必须编写一个可以从文件(顶点)读取数据的程序，接下来从这个数据我应该计算图形大小，接下来我必须使用 DFS 算法来计算一致的组件。
我知道我的代码不好，但我仍在学习 java(和英语:P)。

测试.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 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!!!");
        }
    }
}

图.类

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

搜索.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;
    }
}

Answer 1

您没有在AppClient.java中初始化搜索

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

还要初始化 Search.java 中的 vertexesStack 并删除局部变量 graph，因为您想引用 AppClient 中的变量。 java

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

由于您的代码顶部没有 package x.y.z;，您可能还需要更改 int DFS() -> int DFS(Graph graph )，然后在 AppClient.java 中将图表传递给您对 DFS()

的调用