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

回答

相關問題