KruskMST算法对有向图是否适用？
来源：8-6 Krusk算法
想不出来叫什么
2018-04-16
KrushMST的Java代码中有这样一句：
MinHeap<Edge<Weight>> pq = new MinHeap<Edge<Weight>>( graph.E() );
for( int i = 0 ; i < graph.V() ; i ++ )
for( Object item : graph.adj(i) ){
Edge<Weight> e = (Edge<Weight>)item;
if( e.v() <= e.w() )
pq.insert(e);
}其中有一个判断if(e.v() = e.w())，加了这个判断之后，是不是就不能用于有向图了？谢谢！
写回答
1回答
-
最小生成树这个问题本身一般都是定义在无向有权图上的。
这句话只是为了保证不将重复边放入优先队列。恰恰是因为整个图是无向图，所以(v, w)和(w, v)都在图的边中存储着。我们只取v的序号小于等于w的序号的边，保证不会(v, w)和(w, v)都放入优先队列。
012018-04-16
相似问题