计算机软件技术(第7章图)课件及作业.pptVIP

图的广度优先遍历实例（续） * * 图的广度优先遍历实例（续） * * 图的广度优先遍历实例 1 visited[] 1 1 1 1 1 1 1 1 0 1 2 3 4 5 6 7 8 queue 结点8和9的邻接点都已遍历，将其出队 2 1 3 4 5 6 7 8 9 * * 7.4 生成树和最小生成树 生成树：具有n个顶点的连通图有n-1条边，又称为极小连通子图。 在生成树中去掉一条边，则变为非连通图；若增加一条边，则有回路产生。 构造无向图的生成树的方法：给定一个无向连通图G，从G的任意顶点Vi出发，作一次深度优先或广度优先有哪些信誉好的足球投注网站遍历，遍历过程中所经历过的n-1条边就构成了G的生成树，顶点Vi是生成树的根。 深度优先有哪些信誉好的足球投注网站生成树（DFS生成树） 广度优先有哪些信誉好的足球投注网站生成树（BFS生成树） 生成树 * * 例：从顶点A出发的DFS生成树和BFS生成树。 * * 邻接矩阵作为图的存储结构，构造DFS生成树的算法 int visited[n]; // 定义visited为全局变量，n为顶点数 graph*g=(graph*)malloc((sizeof(graph)): //产生图的存储空间 void DFSA( int i ) // 从vi出发，构造*g的DFS生成树 { int j; printf(“node:%c\n”, g-vexs[i]); // 访问出发点vi visited[i]=1; // 标记vi已被访问 for(j=0; jn; j++) // 按顶点序号从小到大依次有哪些信誉好的足球投注网站vi的某个邻接点 if((g-arcs[i][j]= =1)(visited[j]= =0)) { printf(“(%d,%d)\n”,i,j); //输出边（i，j） DFSA(j); }//若vi的邻接点vj未被访问过，则从vj出发进行深度优先有哪些信誉好的足球投注网站遍历 } // DFSA * * 最小生成树：对一个连通网络构造生成树，可以得到一个带权的生成树。我们把生成树各边的权值总和作为生成树的权值，而具有最小权值的生成树就是连通网络的最小生成树。 最小生成树的应用价值：按照最小生成树构建n个城市之间的通信网络，使通信线路的费用最低。 构造准则: 尽可能用网络中权值最小的边； 必须使用且仅使用 n-1 条边来联结网络中的 n 个顶点； 不能使用产生回路的边。 * * 构造最小生成树的两种算法 prim（普里姆）算法 普里姆算法的基本思想：设G(V,E)是有n个顶点的连通网络，T=(U,TE)是要构造的生成树，初始时U={φ}，TE={φ}。首先从V中取出一个顶点u0放入生成树的顶点集U中作为第一个顶点，此时T=({u0},{φ})；然后从u?U，v?V-U的边(u,v)中找一条代价最小的边(u*,v*)放入TE中和将v*放入U中，此时T=({u0,v*} , {(u0,v*)})；继续从u?U，v?V-U的边(u,v)中找一条代价最小的边(u*,v*)放入TE中和将v*放入U中，直到U=V为止。这时T的TE中必有n-1条边，构成所要构造的最小生成树。 * * Prim算法构造最小生成树实例 以下图为例说明构造过程，从顶点0开始 * * Prim算法构造最小生成树实例（续） * * Prim算法构造最小生成树实例（续） * * Prim算法构造最小生成树实例（续） * * Kruskal (克鲁斯卡尔)算法 克鲁斯卡尔算法的基本思想：设G=(V, E)是一个有n个顶点的连通图，则令最小生成树的初值状态为只有n个顶点而无任何边的非连通图T=(V,{?})，此时图中每个顶点自成一个连通分量。按照权值递增的顺序依次选择E中的边，若该边依附于T中两个不同的连通分量，则将此边加入TE中，否则舍去此边而选择下一条代价最小的边，直到T中所有顶点都在同一连通分量上为止。这时的T，便是G的一棵最小生成树。 * * Kruskal构造最小生成树实例 以下图为例 * * Kruskal构造最小生成树实例（续） 由于(2,3)和(1,3)的权值都是6，因此可以加入(2,3)或者(1,3) * * Kruskal构造最小生成树实例（续） * * Kruskal构造最小生成树的另一个结果 * * 7.5 最短路径 最短路径问题：如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。 最短路径问题的研究分为两种情况： 从某个源点到其余各顶点的最短路径； — Dijkstra（迪杰斯特拉）算法 每一对顶点之间的最短路径。 —