0

我一直盯着这个，它让我发疯。

不知何故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)
4

3 回答 3

1

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

于 2011-02-27T21:14:53.707 回答
0

尚未测试您的代码，但如果队列为空，至少 PriorityQueue.poll() 返回 null 。

怎么改：

while(edgesAccepted < currentSize-1)

到

while(edgesAccepted < currentSize-1 && pq.size() > 0)
于 2011-02-27T21:17:16.847 回答
0

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

如果您添加我在另一个答案中给出的测试，您将获得连接子图的 MST - 但（显然）不可能为整个图构建 MST。

于 2011-02-27T21:39:56.167 回答