minimumSpanningTree引发NullPointerException

-1

我瞪大了眼睛，盯着看，这让我很生气。minimumSpanningTree引发NullPointerException

不知何故e = pq.poll();在大型最小生成树的测试用例中使e值为null。一个微小的最小生成树工作。

我非常感谢这个问题的所有提示，以及如何解决这些问题，因为我觉得我在这里超出了我的头。

谢谢你的帮助！

编辑：它似乎我的优先队列是空的莫名其妙。/

EDIT2：虽然想不通这是为什么我在这里添加了DisjSet类额外的洞察力

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

类的声明和一些成员：

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 = 0; 
     // TreeSet containing all edges 
    private TreeSet<Edge> allEdges = new TreeSet<Edge>(); 
     // edge representing class with its associated nodes and weight

DisjSet等级：

import java.util.*; 

public class DisjSet<K extends Comparable<? super K>> 
{ 
    //HashMap containing 1. K itself, 2. Ks parent. K no.2 is null if K has no parent 
private HashMap<K,K> sets = new HashMap<K,K>(); 

public DisjSet(Set<K> s) 
{ 
    if(s.isEmpty()) 
     throw new IllegalStateException("Empty DisjSet argument"); 

    Iterator<K> nodes_iter = s.iterator(); 

    while(nodes_iter.hasNext()) 
     sets.put(nodes_iter.next(), null); 
} 
    // recursive method to find o_nodes sets root node 
public K find(K o_node) 
{ 
    if(sets.get(o_node) == null) 
     return o_node; 
    else 
     return find(sets.get(o_node)); 
} 
/** 
* connects set 2 to set 1 
* @param root1  root of set 1 
* @param root2  root of set 2 
*/ 
public void union(K root1, K root2) 
{ 
    sets.put(root2, root1); 
} 
}

故障跟踪是否有帮助？：

java.lang.NullPointerException 
at MyMiniGraph.generateMinimumSpanningTree(MyMiniGraph.java:274) 
at MyMiniGraphTest.testGenerateMinimumSpanningTreeLarge(MyMiniGraphTest.java:401) 
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method) 
at sun.reflect.NativeMethodAccessorImpl.invoke(Unknown Source) 
at sun.reflect.DelegatingMethodAccessorImpl.invoke(Unknown Source) 
at java.lang.reflect.Method.invoke(Unknown Source) 
at org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.java:44) 
at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:15) 
at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:41) 
at org.junit.internal.runners.statements.InvokeMethod.evaluate(InvokeMethod.java:20) 
at org.junit.internal.runners.statements.RunBefores.evaluate(RunBefores.java:28) 
at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:76) 
at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:50) 
at org.junit.runners.ParentRunner$3.run(ParentRunner.java:193) 
at org.junit.runners.ParentRunner$1.schedule(ParentRunner.java:52) 
at org.junit.runners.ParentRunner.runChildren(ParentRunner.java:191) 
at org.junit.runners.ParentRunner.access$000(ParentRunner.java:42) 
at org.junit.runners.ParentRunner$2.evaluate(ParentRunner.java:184) 
at org.junit.runners.ParentRunner.run(ParentRunner.java:236) 
at org.eclipse.jdt.internal.junit4.runner.JUnit4TestReference.run(JUnit4TestReference.java:49) 
at org.eclipse.jdt.internal.junit.runner.TestExecution.run(TestExecution.java:38) 
at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.runTests(RemoteTestRunner.java:467) 
at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.runTests(RemoteTestRunner.java:683) 
at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.run(RemoteTestRunner.java:390) 
at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.main(RemoteTestRunner.java:197)

来源

2011-02-27 Alexander E

如何比较边缘？看起来好像你的边缘比较被打破了，那么你会得到这种行为。 – templatetypedef 2011-02-27 22:23:35

请问您测试集包含的连通图？如果没有，它会失败...

如果你在另一个答案中添加了我给出的测试，你会得到一个连接子图的MST - 但是显然不可能为整个图建立一个MST。

来源

2011-02-27 21:39:56 Arve

是'//包含所有节点及其边缘的图私人地图> theGraph = new HashMap >（）; '边缘对象具有对两个连接节点的引用和成本 – 2011-02-27 21:43:05

@Alexander：但是，是否存在将所有节点连接成一（1）个连通图的边？ – Arve 2011-02-27 21:44:38

@Alexander E：Connected =“有从任何点到图中任何其他点的路径” – Arve 2011-02-27 21:51:12

尝试调用pq.take()，而不是pq.poll()。轮询将在空队列上返回null，take将会阻塞，直到有可用的元素。

来源

2011-02-27 21:14:53

以某种方式采取似乎并不存在我+我注意到优先队列似乎是空的某种方式 – 2011-02-27 21:22:23

这就是要点：采取将阻止，直到它有一个元素。 – 2011-02-27 21:24:21

我的不好：PriorityQueue http://download.oracle.com/javase/6/docs/api/java/util/PriorityQueue.html没有它，但PriorityBlockingQueue http://download.oracle.com/javase/ 6/docs/api/java/util/concurrent/PriorityBlockingQueue.html。你可能想要使用它。 – 2011-02-27 21:27:33

未测试您的代码，但至少PriorityQueue.poll（）在队列为空时返回null。

如何改变：

while(edgesAccepted < currentSize-1)

到

while(edgesAccepted < currentSize-1 && pq.size() > 0)

来源

2011-02-27 21:17:16 Arve

是的，测试失败。似乎我的优先队列是空的 – 2011-02-27 21:23:58

minimumSpanningTree引发NullPointerException

回答

相关问题