kruskel.cpp

来自「是各种常用算法的集合」· C++ 代码 · 共 24 行

//kruskel算法
//注释见书

Kruskel(Graph& G) {
	Gentree A(G.n()); 
	Edge E[G.e()];   
	int edgecnt = 0;
	for (int i=0; i<G.n(); i++) 
		for (Edge w = G.first(i); G.isEdge(w); w = G.next(w))
			E[edgecnt++] = w;
	heap H(E, edgecnt, edgecnt); 
	int numMST = G.n();
	for (i=0; numMST>1; i++) {  
		Edge w = H.removemin();    
		int v = G.v1(w);
		int u = G.v2(w);
		if (A.differ(v, u)) {     
			A.UNION(v, u);         
			AddEdgetoMST(G.v1(w), G.v2(w));  
			numMST--;        
		}
	}
}