带权图 (d) Prim算法构造左图中带权图的最小生成树的步骤 Prim算法 void prim(raph& G int s,Edge·&MST){∥s是开始顶点,数组MST用于保存最小生成树的边 int MSTtag=0 ∥最小生成树的边计数 MST=new Edge[G Vertices Num0-1]; 为数组MST申请空间 D=new Dist[G VerticesNumoI ∥为数组D申请空间 for(int i=0; i<G VerticesNum(; i++)i ∥初始化Mark数组、D数组 MArk[= UNVISITED DO index DO].length= INFINITE DO-pre=s, Ds).length MArk S= VISITED ∥开始顶点标记为 VISITED Int v=S for(i=0; i<G Vertices Numo-1; 1++)4 if(DIv]=INFINITY)return, ∥非连通,有不可达顶点 ∥因为v的加入,需要刷新与v相邻接的顶点的D值 for(Edge e slEdge(v), GSedge(e); e= GNextEdge(e)) if(MArk[G To Vertex(e)!= Visited &&DIG To Vertex(e)]. length >eweight))i .length=e weight; DIGTo Vertex(e)pre =v min Vertex(G D) ∥在D数组中找最小值记为v SITE ∥标记访问过 Edge edge(DIv]pre,DⅣv]ndex,DIv] length);,∥保存边 Add EdgetoMST(edge, MST. MSTtag++,∥将边edge加到MST中6 v0 v1 v4 v3 v2 v5 v6 1 v0 v1 v4 v3 v2 v5 v6 1 15 v0 v1 v4 v3 v2 v5 v6 1 15 10 v0 v1 v4 v3 v2 v5 v6 1 15 10 2 v0 v1 v4 v3 v2 v5 v6 1 15 10 2 6 v0 v1 v4 v3 v2 v5 v6 1 15 10 2 4 6 (a) (b) (c) (d) (e) (f) Prim 算法构造左图中带权图的最小生成树的步骤 Prim 算法： void Prim(Graph& G, int s, Edge* &MST) { // s 是开始顶点，数组 MST 用于保存最小生成树的边 int MSTtag = 0; // 最小生成树的边计数 MST = new Edge[G.VerticesNum()-1]; // 为数组 MST 申请空间 Dist *D; D = new Dist[G. VerticesNum()]; // 为数组 D 申请空间 for (int i = 0; i < G.VerticesNum(); i++) { // 初始化 Mark 数组、D 数组 G.Mark[i] = UNVISITED; D[i].index = i; D[i].length = INFINITE; D[i].pre = s; } D[s].length = 0; G.Mark[s]= VISITED; // 开始顶点标记为 VISITED int v = s; for (i = 0; i < G.VerticesNum()-1; i++) { if (D[v] == INFINITY) return; // 非连通，有不可达顶点 // 因为 v 的加入，需要刷新与 v 相邻接的顶点的 D 值 for (Edge e = G.FirstEdge(v); G.IsEdge(e);e = G.NextEdge(e)) if (G.Mark[G.ToVertex(e)] != VISITED && (D[G.ToVertex(e)].length > e.weight)) { D[G.ToVertex(e)].length = e.weight; D[G.ToVertex(e)].pre = v; } v = minVertex(G, D); // 在 D 数组中找最小值记为 v G.Mark[v] = VISITED; // 标记访问过 Edge edge(D[v].pre, D[v].index, D[v].length); // 保存边 AddEdgetoMST(edge,MST,MSTtag++); // 将边 edge 加到 MST 中 } 带权图 v0 v1 v4 v3 v2 v5 v6 20 1 2 4 6 8 15 12 10