prim.cpp

用C++实现的最小生成树的算法

//Prim 算法
//注释见书

void Prim(Graph& G, int s) {
	int *D, *V;
	D = new int [G.n()];
	V = new int [G.n()];
	for (int i=0; i<G.n(); i++)    
		D[i] = INFINITY;
	D[s] = 0;
	for (i=0; i<G.n(); i++) {       
		int v = minVertex(G, D);
		G.Mark[v] = VISITED;
		if (v != s) AddEdgetoMST(V[v], v); 
		if (D[v] == INFINITY) return; 
		for (Edge w = G.first(v); G.isEdge(w); w = G.next(w))
			if (D[G.v2(w)] > G.weight(w)) {
				D[G.v2(w)] = G.weight(w);    
				V[G.v2(w)] = v;   
			}
	}
}

int minVertex(Graph& G, int* D) {
	int v;
	for (int i=0; i<G.n(); i++)
		if (G.Mark[i] == UNVISITED) { 
			v = i;
			break; 
		}
		for (i=0; i<G.n(); i++)
			if ((G.Mark[i] == UNVISITED) && (D[i] < D[v]))
				v = i;
			return v;
}