计算机软件基础第七讲.pptVIP

* * 对角线元素全为0。构造最小生成树的过程中，若顶点已包含在生成树里，就把其对应的对角线元素置为“1”；若边(vi,vj)已包含进生成树里，就把A[i,j]或A[j,i]位于下三角的一个置为负值 * * * * * * * * * * * * * * * * Kruskal算法8.10: void Kruskal（EdgeType edges[ ]，int n） /*用Kruskal方法构造有n个顶点的图edges的最小生成树*/ {int father[MAXEDGE]; int i,j,vf1,vf2; for (i=0;in;i++) father[i]=-1; i=0;j=0; while(iMAXEDGE jn-1) { vf1=Find(father,edges[i].v1); vf2=Find(father,edges[i].v2); if (vf1!=vf2) { father[vf2]=vf1; j++; printf(“%3d%3d\n”,edges[i].v1,edges[i].v2); } i++; } } int Find（int father[ ]，int v） /*寻找顶点v所在树的根结点*/ { int t; t=v; while(father[t]=0) t=father[t]; return(t); } 图的应用：最短路径 图的应用：最短路径 源点：路径的开始点 终点：路径的最后一个顶点 最短路径：沿路径的各边权值之和最小 图的应用：最短路径 算法：对有n个顶点的有向连通网络G＝（V，E），首先从V中取出源点u0放入最短路径顶点集合U中，这时的最短路径网络S =({u0},{?})；然后从u∈V－U中找一条代价最小的边（u*,v*)加入到S中去，此时S=({u0,v*},{(u0,v*)})。每往U中增加一个顶点，则要对V－U中的各顶点的权值进行一次修正。若加进v*作为中间顶点，使得从u0到其它属于V－U的权值来代替原(u0,vi)的权值，否则不修改u0到vi的权值。接着再从修正后的V－U中选择最短的边加入S中，如此反复，直到U＝V。 图的应用：最短路径 循环 U k D[0]…D[5] p[0]…p[5] s[0]…s[5] 初始化 {F} 24,5,m,25,m,0 6,6,0,6,0,6 0,0,0,0,0,1 1 {F,B} 1 23,5,12,25,m,0 2,6,2,6,0,6 0,1,0,0,0,1 2 {F,B,C} 2 21,5,12,25,m,0 3,6,2,6,0,6 0,1,1,0,0,1 3 {F,B,C,A} 0 21,5,12,25,m,0 3,6,2,6,0,6 1,1,1,0,0,1 4 {F,B,C,A,D} 3 21,5,12,25,m,0 3,6,2,6,0,6 1,1,1,1,0,1 5 {F,B,C,A,D,E} 4 21,5,12,25,m,0 3,6,2,6,0,6 1,1,1,1,1,1 图的应用：最短路径 void ShortestPath_DIJ(Mgraph G,int v0,Path P,ShortPathTable D){ for(v = 0;vG.vexnum;++v){ s[v] = FALSE;D[v] = G.arcs[v0][v]; if(D[v] INFINITY) P[v] = v0+1; else p[v] = 0 } D[v0] = 0; s[v0] = TRUE; 图的应用：最短路径 for(i=1;iG.vexnum;++i){ min = INFINITY; for(w=0;wG.vexnum;w++) if(!s[w]D[w]min){ v = w;min = D[w];} s[v] = TRUE; for(w=0;wG. vexnum;w++) if(!s[w](D[w]min+G.arcs[v][w])){ D[w] = min + G.arcs[v][w]; P[w] = v+1; } } } 图的应用：关键路径 图的应用：关键路径 顶点表示事件，弧表示活动，权表示活动持续的时间 在正常情况下，网中只有一个开始点（源点）和一个完成点（汇点）。 路径长度最长的路径称为关键路径。 图的应用：关键路径 算法： 输入e条弧j,k,建立AOE网的存储结构 从源点v0出发，令ve[0]=0,按拓扑有序求其余各顶点的最早发生时间ve[i]。如果得到的拓扑有序序列中顶点个数小