当我将边缘添加到图形(树)时，我得到一个空指针

Question

我有一个创建 Kruskal 算法的任务，这很好，网上有一个很好的教程，但我很难尝试使用分配的权重将边缘添加到我的所有节点。这就是我正在做的事情，希望你们能帮助我。

主要功能

 public static void main(String[] args) {
    int maximumVertices = 50;
    Random ran = new Random();

    Graph g = new Graph(maximumVertices);
    for(int i=0; i<maximumVertices-1; i++){
        int weight = ran.nextInt(50);
        int connectedNode = ran.nextInt(10); //the idea here is to create random connections between nodes
        g.addVertex(i);
        g.addBidirectionalEdge(i, connectedNode, weight);
        g.addBidirectionalEdge(i+1, connectedNode, weight);
        System.out.println(Arrays.toString((g.getAdjacentVertexNumbers(i))));
    }
Kruskal k = new Kruskal(g);
    List<Edge> mst = k.getMSTEdges();
    System.out.println ("Minimum Spanning Tree Edges are:");
    ListIterator<Edge> it = mst.listIterator();
    while(it.hasNext()){
        Edge e = (Edge)it.next();
        System.out.println ("v" + e.getFrom().getVertexNo() + " --- v" + e.getTo().getVertexNo());
        }

克鲁斯卡尔级

  public class Kruskal {
private Graph graph;
private int[] sets; //represent set for vertices
public Kruskal(Graph g) {
    this.graph = g;
    this.sets = new int[g.getTotalNumberOfVertices()];
}
private void makeSet(Vertex v){
    this.sets[v.getVertexNo()] = v.getVertexNo(); //simply set the set name to each vertex no
}
private int findSet(Vertex v){
    return this.sets[v.getVertexNo()]; //gets the set name/number of a vertex
}
private void union(Vertex u, Vertex v){
    int findWhat, replaceWith;
    if(u.getVertexNo() < v.getVertexNo()){
        findWhat = this.sets[v.getVertexNo()];
        replaceWith = this.sets[u.getVertexNo()];
    }
    else{
        findWhat = this.sets[u.getVertexNo()];
        replaceWith = this.sets[v.getVertexNo()];
    }
    //make both sets same
    for(int i=0; i<this.sets.length; i++){
        if(this.sets[i] == findWhat){
            this.sets[i] = replaceWith;
        }
    }
}
private void sortEdges(Edge[] edges){
    for(int i=0; i<edges.length-1; i++){
        for(int j=i+1; j<edges.length; j++){
            if(edges[i].getWeight() > edges[j].getWeight()){
                Edge tmp = edges[i];
                edges[i] = edges[j];
                edges[j] = tmp;
            }
        }
    }
}
//runs the main kruskal algorithm
public List<Edge> getMSTEdges(){
    //holds the MST edges
    List<Edge> mstEdges = new ArrayList<Edge>();
    Vertex[] vertices = this.graph.getVertices();
    for(int i=0; i<vertices.length; i++){
        this.makeSet(vertices[i]);
    }
    //get all bi-directional edges
    Edge[] edges = this.graph.getAllBidirectionalEdges();
    //sort the edges w.r.t their weights in non-decreasing order
    this.sortEdges(edges);
    for(int i=0; i<edges.length; i++){
        //for each each, in sorted order
        Edge e = edges[i];          
        if(this.findSet(e.getFrom()) != this.findSet(e.getTo())){
            //if the vertices it connects are not in the same set
            //this edge is an MST edge
            mstEdges.add(e);
            //now, both vertices should have same set
            this.union(e.getFrom(), e.getTo());
        }
    }
    return mstEdges;
}
}

图形类

public class Graph {
private final int DEFAULT_EDGE_COST = 1;
private Vertex[] vertices = null; //list of all vertices in the graph
private int totalVertices = 0; //keeps count of vertices
private int[][] adjMatrix = null; //keeps the edges of the graph using adjacency matrix
private int[] adjacentVertCount = null; //keeps count of adjacent vertices for each vertex
public Graph(int maxVertices) {
    this.vertices = new Vertex[maxVertices]; //initialize vertices array
    this.adjMatrix = new int[maxVertices][maxVertices]; //initialize adjacency matrix
    this.adjacentVertCount = new int[maxVertices]; //initialize adjacent vertices count
    for(int i=0; i<maxVertices; i++){
        this.adjacentVertCount[i] = 0; //set adjacent vertex count to 0 initially
        for(int j=0; j<maxVertices; j++){
            this.adjMatrix[i][j] = -1; //set adjacency list to -1 initially
        }
    }
}

 public Graph(){
    //default Max amount of vertices: 100 [0-99]
    this(100);
}
//add a new vertex with vertexNo and data
public void addVertex(int vertexNo, Object data){
    this.vertices[vertexNo] = new Vertex(vertexNo, data);
    this.totalVertices++;
}
//add a new vertex with vertexNo only
public void addVertex(int vertexNo){
    this.addVertex(vertexNo, null);
}
//add a uni-directional edge with cost
public void addEdge(int fromVertexNo, int toVertexNo, int cost){
    this.adjMatrix[fromVertexNo][toVertexNo] = cost;
    this.adjacentVertCount[fromVertexNo]++;
} 
//add a bi-directional edge with cost
public void addBidirectionalEdge(int vertex1, int vertex2, int cost){
    this.addEdge(vertex1, vertex2, cost);
    this.addEdge(vertex2, vertex1, cost);
}
//add a bi-directional edge with cost
public void addBidirectionalEdge(Vertex v1, Vertex v2, int cost){
    this.addBidirectionalEdge(v1.getVertexNo(), v2.getVertexNo(), cost);
}

//get the total vertices count in the graph
public int getTotalNumberOfVertices(){
    return this.totalVertices;
}

//get adjacent vertex numbers for a given vertexNo
public int[] getAdjacentVertexNumbers(int vertexNo){
    int[] ret = new int[this.adjacentVertCount[vertexNo]];
    int index = 0;
    for(int i=0; i<this.adjMatrix[vertexNo].length; i++){
        if(this.adjMatrix[vertexNo][i] >= 0){
            ret[index++] = i;
        }
    }
    return ret;
}
//get adjacent vertex numbers for a given vertex
public int[] getAdjacentVertexNumbers(Vertex vert){
    return this.getAdjacentVertexNumbers(vert.getVertexNo());
}
//get adjacent vertices for a given vertexNo
public Vertex[] getAdjacentVertices(int vertexNo){
    Vertex[] ret = new Vertex[this.adjacentVertCount[vertexNo]];
    int index = 0;
    for(int i=0; i<this.adjMatrix[vertexNo].length; i++){
        if(this.adjMatrix[vertexNo][i] >= 0){
            ret[index++] = this.vertices[i];
        }
    }
    return ret;
}
//get adjacent vertices for a given vertex
public Vertex[] getAdjacentVertices(Vertex vert){
    return this.getAdjacentVertices(vert.getVertexNo());
}
//gets the edge/path cost from adjacency list for two given vertexNo
public int getEdgeCost(int fromVertNo, int toVertNo){
    return this.adjMatrix[fromVertNo][toVertNo];
}
//gets the edge/path cost from adjacency list for two given vertices
public int getEdgeCost(Vertex fromVert, Vertex toVert){
    return this.getEdgeCost(fromVert.getVertexNo(), toVert.getVertexNo());
}
//gets all vertices
public Vertex[] getVertices(){
    return this.vertices;
}
//returns all the edges of the graph
//needed for edge traversing algorithms
public Edge[] getAllEdges(){
    int totalEdges = 0;
    for(int i=0; i<this.adjacentVertCount.length; i++){
        totalEdges += this.adjacentVertCount[i];
    }
    Edge[] edges = new Edge[totalEdges];
    int index = 0;
    for(int i=0; i<this.vertices.length; i++){
        for(int j=0; j<this.vertices.length; j++){
            if(this.adjMatrix[i][j] >= 0){
                edges[index++] = new Edge(this.vertices[i], this.vertices[j], this.adjMatrix[i][j]);
            }
        }
    }
    return edges;
}
public Edge[] getAllBidirectionalEdges(){
    int totalEdges = 0;
    for(int i=0; i<this.adjacentVertCount.length; i++){
        totalEdges += this.adjacentVertCount[i];
    }
    totalEdges /= 2;
    Edge[] edges = new Edge[totalEdges];
    int index = 0;
    for(int i=0; i<this.vertices.length; i++){
        for(int j=i+1; j<this.vertices.length; j++){
            if(this.adjMatrix[i][j] >= 0){
                edges[index++] = new Edge(this.vertices[i], this.vertices[j], this.adjMatrix[i][j]);
            }
        }
    }
    return edges;
}
}

错误：

Exception in thread "main" java.lang.NullPointerException
at Kruskal.makeSet(Kruskal.java:15)
at Kruskal.getMSTEdges(Kruskal.java:62)
at Main.main(Main.java:51)

我让边缘很好地打印出来，但是当我实现 k.getMSTEdges（） 时，如果给了我空指针并且不喜欢它。但是，当我对它进行硬编码时，例如g.addBidrectionalEdge（0,2,8）等，它可以工作，所以我知道它在这里的主要内容，但我不正确。再次感谢您的帮助！

Answer 1

这似乎是你的问题：

for(int i=0; i<maximumVertices-1; i++)

将其更改为

for(int i=0; i<maximumVertices; i++)

这是您创建图形的位置。

否则，您只创建 49 个顶点，然后当您尝试访问第 50 个顶点时，会出现 NULL 数据。或者至少，我假设顶点将一些数据初始化为 NULL