ch7图wu2.ppt

史忠植 高级人工智能 最小生成树的PRIM方法 Void Prim(MGraph G) { for (i=1;iG.vertexNum;i++) { lowcost[i]=G.arc[0][i]; adjvex[i]=0; } //初始化两个辅助数组lowcost、adjvex lowcost[0]=0;//将顶点0加入集合U中 for （i=1；iG.vertextNum；i++) { k=MinEdge(lowcost,G.vertexNum); //在lowcost中寻找最短便的顶点k cout“(“kadjvex[k]“)” lowcost[k];//输出加入TE中的边 lowcost[k]=0; for(j=i; jG.vertexNum; j++)//调整lowcost和adjvex if (G.arc[k][j]lowcost[j]) { lowcost[j]=G.arc[k][j]; adjvex[j]=k; } } } MinEdge(lowcost,G.vertexNum); int MinEdge(lowcost[],int N); { k=-1;min=MAX;//MAX为较大的数 for (i=1;iN;i++) if( lowcost[i]!=0lowcost[i]min) { k=i; min=lowcost[i];} return k; } PRIM算法的复杂性分析 设连通网有n个顶点，则 1）第一个初始化，循环n-1次。 2）第二个初始化，循环n-1次，内嵌两个循环，其一在长度为n-1的 数组中求最小值，需n-1次，其二时调整辅助数组，需n-1次，所以总的时间复杂度为O（n2）。 与网中的边数无关。适宜于求密网的求最小生成树。 typedef float ADJ[VN+1][VN+1]； minispantree_prim(ADJ gn, int u0) /* 从u0出发构造网gn的最小生成树， 按普里姆算法输出生成树上各条边 */ { struct node { int vex； float lowcost； } closedge[VN+1]； for (v＝1； v=VN； v++) if ( v !＝ u0 ) { closedge[v].vex ＝ u0； closedge[v].lowcost ＝ gn[u0][v]； } closedge[u0].lowcost＝0； /* 辅助数组初始化 */ for ( i＝1；i＝VN-1； i++ ) /* 只需N-1条边 */ { k ＝ minimun(closedge)； /* 代码为： k=0; val=MAX; for(v=1;v=VN;v++) if (closedge[v].lowcost0 closedge[v].lowcostval) { k=v; val= closedge[v].lowcost;} */ printf (“％d ，％d”，closedge[k].vex,k)； /* 输出生成树的边 */ closedge[k].lowcost＝0； /* 顶点k并入U集 */ for (v＝1； v= VN； v++) if ( (closedge[v].lowcost!=0) (gn[k][v] closedge[v].lowcost ) { closedge[v].lowcost＝gn[k][v]； closedge[v].vex＝k; } /* 调整*/ } } Kruskal算法 问题： 1）如何判断欲加入的一条边是否与生成树中已保留的边形成回路？ 可将顶点划分为子集，每个子集是一个无回路的连通分量。初始时，n个顶点分属n个集合。 2）如何选边？ 将边集数组按权值大小由小到大预排序。当从边集数组中按次序选取一条边时，若它的两个端点分属不同的集合，则表明此边连通了两个不同的连通分量，且不