实例化私有类->空指针异常

Question

嗨，很棒的人！

我有一个问题...当我的测试用例到达 connectNodes 方法中的 allEdges.add(newEdge); 时，我收到 NullPointerException。

我认为这与之前相同方法中的 Edge newEdge = new Edge( n1, n2, Weight ); 有关。

问题是我在 Edge 类中使用泛型还是类似的问题？ 我之前在 Edge newEdge = new Edge( n1, n2, Weight ); 行中收到错误提示，提示类似“未找到类”之类的内容。但现在我似乎在 allEdges.add(newEdge); 处得到了 NullPointerException 而没有更改任何内容。

非常感谢您的每一点帮助！

import java.util.*;

public class MyMiniGraph<T extends Comparable<? super T>> implements MiniGraph<T>
{
      // The Graph containing all the nodes and their edges
    private Map< T, HashSet<Edge> > theGraph = new HashMap< T, HashSet<Edge> >( );
      // Keeps track of theGraphs current size
    private int currentSize = 0;
      // Keeps track of the current Edge quantity
    private int numEdges;
      // TreeSet containing all edges
    private TreeSet<Edge> allEdges;
      // edge representing class with its associated nodes and weight
    private class Edge implements Comparable<Edge>
    {
        public int cost;
        public T n1;
        public T n2;
        public Edge(T n1, T n2 , int cost)
        {
            this.n1 = n1;
            this.n2 = n2;
            this.cost = cost;
        }

    public int compareTo(Edge e)
    {
          // returns 0 if edges are equal
        if(e.cost == cost)
            return 0;
          // returns 1 if edge is greater than other edge,
          // -1 if edge is smaller than other edge
        return e.cost < cost ? 1 : -1; 
    }

}

/** 
 *  Method for adding a node to the graph.
 *  Silently ignores any duplicates
 *
 *  @param n    The node to add to the graph.
 */
public void addNode(T n)
{
    if(n == null)
        throw new IllegalStateException("Invalid Node");
    if(!theGraph.containsKey(n))
    {   
        theGraph.put(n,new HashSet<Edge>());
        ++currentSize;
    }
}

/**
 *  Method for removing a node from the graph. 
 *  Before the node is removed, all edges associated with the node
 *  must be removed.
 *  Silently ignores any nodes not already in the graph.
 */
public void removeNode(T n)
{
    if(theGraph.containsKey(n))
    {
      // If node n has edges, remove all those edges. 
      // Firstly, remove the edges connecting to this 
      // node from other nodes, then, remove this node  
      // and its edges with it.
        if( !theGraph.get(n).isEmpty() )
        {
              //iterator to iterate over the edges of node n
            Iterator<Edge> edgeIt = theGraph.get(n).iterator();

              // remove this node from all its connecting nodes edge lists
            Edge localEdge;
            /**Edge foreignEdge;*/
            while(edgeIt.hasNext())
            {
                localEdge = edgeIt.next();
                T foreignNode = localEdge.n2 == n ? localEdge.n1 : localEdge.n2;
                  // iterator to iterate over the edges of adjacent node of n (foreignNode)
                /**Iterator<Edge> forEdgeIt = 
                    theGraph.get(foreignNode).iterator();

                while(forEdgeIt.hasNext())
                {
                    foreignEdge = forEdgeIt.next();
                    if( foreignEdge.equals( localEdge ) )
                        forEdgeIt.remove();
                }*/
                  // removes all edges occurring in n from all foreign nodes
                theGraph.get(foreignNode).remove(localEdge);
                allEdges.remove(localEdge);
                --numEdges;
            }
        }
          //remove the node itself thereby also removing its local edge list
        theGraph.remove(n);
        --currentSize;
    }
}

/**
 *  Method for creating an unidirectional edge between two nodes. 
 *
 *  @param  n1  The first node to create an edge between
 *  @param  n2  The second node to create an edge between
 *  @param  weight  The cost for traversing the edge
 */
public void connectNodes(T n1, T n2, int weight)
{
    if(!contains(n1) || !contains(n2))
        throw new IllegalStateException("node not in graph");

    if(!edgeExistsBetween(n1,n2))
    {
        Edge newEdge = new Edge( n1, n2, weight );
        theGraph.get(n1).add( newEdge );
        theGraph.get(n2).add( newEdge );

        allEdges.add(newEdge);
        ++numEdges;
    }
}

/**
 *  Method for removing an edge between two nodes.
 *
 *  @param  n1  The first node that identifies the edge.
 *  @param  n2  The second node that identifies the edge.
 */
public void disconnectNodes(T n1, T n2)
{
    if(!contains(n1) || !contains(n2))
        throw new IllegalStateException("node not in graph");

    boolean n1n2EdgeExists = true;

  // iterates over n1, removing all edges containing n2 from n2
    Iterator<Edge> edgeIt = theGraph.get(n1).iterator();

    Edge deadEdge = null;
    while(edgeIt.hasNext())
    {
        deadEdge = edgeIt.next();

        if( deadEdge.n1.equals(n1) )
            theGraph.get(n2).remove(deadEdge);

        else if( deadEdge.n2.equals(n1) )
            theGraph.get(n1).remove(deadEdge);

        else
            n1n2EdgeExists = false;
    }
    if(n1n2EdgeExists){
          // removes the n1-n2 edge from n1
        theGraph.get(n1).remove(deadEdge);

        allEdges.remove(deadEdge);
        --numEdges;
    }

}

/**
 *  Method for searching the graph for a certain node.
 *  If the node is present in the graph, the method returns 
 *  true, otherwise, it returns false.
 * 
 *  @return boolean     true if the graph contains n, otherwise false. 
 */
public boolean contains(T n)
{
    return theGraph.containsKey(n);
}

/**
 *  Method for finding the number of nodes in the graph.
 * 
 *  @returns int    The number of nodes in the graph.
 */
public int size()
{
    return currentSize;
}

/**
 * Checks if there exists and edge between nodes n1 and n2.
 * Used for testing purposes.
 * 
 * @param n1    The first node that identifies the edge.
 * @param n2    The second node that identifies the edge.
 * @return true if and edge exists between n1 and n2, otherwise false.
 */
public boolean edgeExistsBetween(T n1, T n2)
{
    if(contains(n1))
    {
        boolean n1ContainsN2 = false;

        Iterator<Edge> edgeIt = theGraph.get(n1).iterator();

        Edge adjToN1;
        while(edgeIt.hasNext())
        {
            adjToN1 = edgeIt.next();
            if( adjToN1.n1.equals(n2) )
                n1ContainsN2 = true;
            else if( adjToN1.n2.equals(n2) )
                n1ContainsN2 = true;
            else
                ;
        }// while n1 has next edge
        return n1ContainsN2;
    }// if n1 in graph
    return false;
}

/**
 * Gets the number of edges in the graph.
 * Used for testing purposes.
 * 
 * @return the number of edges in the graph.
 */
public int getNumberOfEdges()
{
    return numEdges;
}

/**
 *  Method for calculating a minimum spanning tree for the graph.
 *  The method is supposed to returning a String representing the
 *  minimum spanning tree. The method is not allowed to modify the
 *  graph during the calculation, ie. the original graph must be
 *  identical to how the graph looked before the invocation of
 *  the method.
 *
 *  The minimum spanning tree is calculated using Kruskal's algorithm.
 *
 *  @return Graph A new instance of the Graph class, representing a
 *      minimal spanning tree.
 */
public MyMiniGraph<T> generateMinimumSpanningTree()
{
    int edgesAccepted = 0;
      //give all nodes to a class representing disjoint sets
    DisjSet<T> ds = new DisjSet<T>( theGraph.keySet() );

      //set up a new graph to represent the minimum spanning tree
    MyMiniGraph<T> minSpanTree = new MyMiniGraph<T>();
      //initialize minSpanTree with all theGraphs nodes
    Iterator<T> nodeIter = theGraph.keySet().iterator();
    while(nodeIter.hasNext())
        minSpanTree.addNode(nodeIter.next());

      //order all edges in theGraph in a priority queue
    PriorityQueue<Edge> pq = new PriorityQueue<Edge>(allEdges);
    Edge e;

      // Kruskals algorithm. Accepts the smallest edges in order
      // if they are not part of the same set which would cause a cycle. 
    while(edgesAccepted < currentSize -1)
    {
        e = pq.poll( );
        T uset = ds.find( e.n1 );
        T vset = ds.find( e.n2 );

        if(uset != vset)
        {
            // Accept the edge
            edgesAccepted++;
            ds.union(uset, vset);

             //if the edge is accepted, add it to minSpanTree
            minSpanTree.connectNodes(e.n1, e.n2, e.cost);
        }
    }
    return minSpanTree;
}

}

Answer 1

我没有找到任何将成员 allEdges 初始化为有效 TreeSet 对象的地方。尝试初始化（正确的位置似乎就是您定义它的位置）