lazy Prim中的一个小小的优化和时间复杂度分析

Question

老师的代码中对于循环结束的情况是当堆中不为空的时候
我的实现:
优化了时间复杂度? 变成了O((V-1)logE), 这个时间复杂度对吗?如果对的话不就是比O(ElogV)还快了吗?毕竟边的个数是一定大于等于顶点的个数的

public class Prim {
	private Graph graph;								// 要获取最小生成树的图
	private PriorityQueue<Edge> minHeap;				// 最小堆, 优先队列, Java自带的优先队列是最小堆实现的
	private ArrayList<Edge> minSpanningTree;			// 最小生成树的所有边
	private boolean[]	visited;						// 顶点是否已经访问过

	public Prim (Graph<? extends Comparable<?>> graph) {
		this.graph = graph;
		this.minHeap = new PriorityQueue<Edge>();
		this.minSpanningTree = new ArrayList<Edge>();
		this.visited = new boolean[graph.getPeak()];
		
		for (int i = 0; i < visited.length; i++) {
			visited[i] = false;
		}
		
		generateMinSpanningTree();
	}
	
	private void generateMinSpanningTree () {
		// 从树的原顶点开始出发查找
		int index = 0;
		
		// 当所有顶点都被遍历之后, 最小生成树也就找到了, 边的数量应该是顶点的数量减一
		while (minSpanningTree.size() < graph.getPeak() - 1) {
			// 对该顶点进行迭代, 将其所有边都压入最小堆中 
			Iterators iterator = graph.iterator(index);
			
			while (!iterator.end()) {
				Edge next = iterator.next();
				// 只将index顶点到一个未访问过的顶点的边压入最小堆
				if (!visited[next.getToPeak()]) {
					minHeap.add(next);
				}
			}
			
			// 设置该顶点为已经访问过的, 这样下次其它顶点在迭代的时候就会忽略那些顶点到index的边
			visited[index] = true;
			
			// 此时取出最小的边, 如果这个最小边的两个顶点都被访问过了, 那么就提取下一个最小边
			// 直到一个被访问一个没被访问则才是横切边, 该边就是最小生成树中的一条边, 并放入最小生成树中
			Edge minEdge;
			while (true) {
				minEdge = minHeap.remove();
				if (visited[minEdge.getFromPeak()] && visited[minEdge.getToPeak()]) {
					continue;
				}
				break;
			}
			
			minSpanningTree.add(minEdge);
			
			// 将index设置为该最小边中没被访问过的顶点
			index = visited[minEdge.getToPeak()] == true ? minEdge.getFromPeak() : minEdge.getToPeak();
		}
	}
	
	public ArrayList<Edge> getMinSpanningTree () {
		return minSpanningTree;
	}
}

下面是边的类

public class Edge<T extends Comparable<T>> implements Comparable<Edge<T>>{
	// 对于from, to来说, 只有在有向图的时候其意义才会不同
	private int from;			//	表示边的第一端
	private int to;				// 表示边的第二端
	private T weight;			// 边的权重, 用泛型表示, 因为可以是整型, 可以是浮点型  
	
	public Edge (int from, int to, T weight) {
		this.from = from;
		this.to = to;
		this.weight = weight;
	}
	
	public void setWeight (T weight) {
		this.weight = weight;
	}
	
	public int getToPeak () {
		return to;
	}
	
	public int getFromPeak () {
		return from;
	}
	
	@Override 
	public String toString () {
		return "{from: "+ from + ", to: "+ to + ", weight: " + weight +"}";
	}

	@Override
	public int compareTo(Edge<T> o) {
		if (o == null) {
			throw new IllegalArgumentException("Edge of o does not exist");
		}
		return weight.compareTo(o.weight);
	}
}

Answer 1

liuyubobobo 2019-04-16 16:33:19

首先，你的算法肯定不是VlogE的。按照你的写法，虽然最外面的while循环确实执行了V次，但每一次循环内部，远超logE的复杂度。因为你的循环内部不是一次简单的一个堆操作而已。还伴随着循环。最差的情况，会有V次循环（某个定点和所有其他定点都相连）。

实际上，你的算法依然是ElogE的。但具体复杂度分析上，要使用均摊复杂度分析。简单地说，你在遍历每一个顶点的时候，要遍历每一个顶点的临边，所以，肯定每一个边都遍历了。在遍历边的过程中，可能涉及堆操作。由于你的堆是存储所有的边，所以时间复杂度上届是logE，整体是ElogE的。

关于图论中的算法复杂度，一个常见的问题可以参考这里：http://coding.imooc.com/learn/questiondetail/101781.html

基本上来讲，一旦你遍历了一个图，复杂度至少是O(E)的：）而且，近乎所有的图论算法，都需要遍历整张图：）

继续加油！：）

• 提问者 慕标8212032 #1

  非常感谢！明白了, 因为存在内层循环的关系, 所以不止一次的堆操作