数据结构教学课件作者李学刚电子课件源代码单元5图幻灯片.ppt

void Prim (MGraph *G,int u) {//求用邻接矩阵表示的图G的最小生成树的算法 int cc=0,pp[VertexNum*2]; /*pp记录最小生成树中边的下标，最终得到最小生成树的边的序列*/ int k=0,i,j,s1; for(i=0;iG-n;i++) { CloseEdge[i].vex=u; CloseEdge[i].lowcost=G-edges[u][i]; } CloseEdge[u].lowcost=0; for(i=1;iG-n;i++) //求最小生成树的G-n-1条边 { k=MinValue(G-n); s1=CloseEdge[k].vex; //边(s1,k)是一条权值最小的边 CloseEdge[k].lowcost=0; //将顶点k加入到U中 pp[cc++]=s1; pp[cc++]=k; //将最小生成树的一条边(s1,k)记录到数组pp中 for(j=0;jG-n;j++) if(G-edges[k][j]CloseEdge[j].lowcost) {//调整最短路径，并保存下标 CloseEdge[j].lowcost=G-edges[k][j];CloseEdge[j].vex=k; } } printf(公路网建设最经济方案为:\n); for(i=0;i2*(G-n-1);i=i+2) printf(应建公路：%s=%s,费用：%d\n,G-vexs[pp[i]], G-vexs[pp[i+1]],G-edges[pp[i]][pp[i+1]]); } 引例分析与实现 int main() { MGraph G; CreateMGraph(G); Prim (G,0); //0为起始顶点的下标 return 0； } 引例分析与实现 再 见 * void DFSTraverse(MGraph *G) {//广度优先遍历以邻接矩阵表示G int i; for(i=0;iG-n;i++) visited[i]=0; //标志向量初始化 for(i=0;iG-n;i++) if(!visited[i])//vi未访问过 BFSM(G,i); //以vi为源点开始DFSM有哪些信誉好的足球投注网站 } （2）邻接表表示的广度优先遍历算法 int visited[VertexNum]={0}; //定义标志向量 void BFS(ALGraph*G,int k) {// 以vk为源点对用邻接表表示的图G进行广度优先有哪些信誉好的足球投注网站 int i; CirQueue Q;//须将队列定义中DataType改为int EdgeNode *p; InitQueue(Q);//队列初始化 printf(%4c,G-adjlist[k].vertex); //访问源点vk visited[k]=1; EnQueue(Q,k); //vk已访问，将其入队。（实际上是将其序号入队） while(!QueueEmpty(Q)) {//队非空则执行 i=DeQueue(Q); //相当于vi出队 p=G-adjlist[i].firstedge;//取vi的边表头指针 while(p) {//依次有哪些信誉好的足球投注网站vi的邻接点vj(令p-adjvex=j) if(!visited[p-adjvex]) { //若vj未访问过 printf(%4c,G-adjlist[p-adjvex].vertex);//访问vj visited[p-adjvex]=1; EnQueue(Q,p-adjvex);//访问过的vj人队 } p=p-next;//找vi的下一邻接点 } } } 【课堂实践5-4】 已知有向图的邻接表如图5-12所示，写出从顶点A出发，对该图进行广度优先有哪些信誉好的足球投注网站遍历的顶点序列。 做 一 做 图5-12 有向图的邻接表 1 0 ^ 3 ^ 2 ^ 0 1 2 3 4 A B C D E 0 ^ 0 1 ^ 一、生成树 在图论中，通常将一个无回路的连通图定义成树。无回路的连通图叫做自由树（在自由树中选定一顶点作根，则成为一棵通常的树）。 1．生成树（Spanning Tree） 如果连通图G的一个子图是一棵包含G的所有顶点的树，则该子图称为G的生成树。 说明： ①生成树是连通图的包含图中的所有顶点的极小连通子图； ②图的生成树不惟一。从不同的顶点出发进行遍历，可以得到不同的生成树。 5.4 最小生成树 【示例】下面是一个连通图G和它的生成树。