数据结构课件第5章12.pptVIP

第五 章 图 §5.1 图的基本概念 §5.1 图的基本概念 §5.1 图的基本概念 §7.1 图的基本概念 §5.1 图的基本概念 §5.1 图的基本概念 §5.1 图的基本概念 四 图的基本操作 P156 第五 章 图 § 5.2 图的存储结构 § 5.2 图的存储结构 § 5.2 图的存储结构 § 5.2 图的存储结构 § 5.2 图的存储结构 § 5.2 图的存储结构 § 5.2 图的存储结构 § 5.2 图的存储结构 § 5.2 图的存储结构 § 5.2 图的存储结构 § 5.2 图的存储结构 § 5.2 图的存储结构 §5.3 图的遍历 §5.3 图的遍历 §5.3 图的遍历 §5.3 图的遍历 §5.3 图的遍历 §5.3 图的遍历 §5.3 图的遍历 §5.3 图的遍历 §5.3 图的遍历 void BFS (struct Lnode *adjlist, int V0) { iniqueue(q); adjlist[V0].VEX=1; printf(“…”,v0); enqueue(q,v0); while (not empty(q)) { v0=dlqueue(q) ; p= adjlist[v0].link; while(p!=null) { if(adjlist[p-vex].vex==0) { adjlist[p-vex].vex=1; printf(“…”,p-vex); enqueue(q, p-vex); } p=p-link; } }// not empty } §5.3 图的遍历 §5.4 生成树 §5.4 最小的生成树 §5.4 最小的生成树 §5.4 最小的生成树 §5.5 最短路径 第五 章 图 §5.6 有向无环图的应用 §5.6 有向无环图的应用 §5.6 有向无环图的应用 §5.6 有向无环图的应用 §5.6 有向无环图的应用 §5.6 有向无环图的应用 §5.6 有向无环图的应用 §5.5 有向无环图及应用 §5.5 最短路径 §5.6 最短路径 §5.6 最短路径 §5.6 最短路径 §5.6 最短路径 §5.6 有向无环图的应用 §5.6 有向无环图的应用 §5.6 有向无环图的应用 §5.6 有向无环图的应用 §5.6 有向无环图的应用 §5.6 有向无环图的应用 §5.6 有向无环图的应用 §5.6 有向无环图的应用 §5.3 图的遍历 §5.3 图的遍历 Dijkstra算法的基本思想 按路径长度递增顺序求最短路径算法 。与求最小生成树的普里姆算法类似 1 迪杰斯特拉算法（Dijkstra） Dijkstra 算法的基本步骤 设V0是起始源点，U = 已求得最短路径终点集合。V-U = 未确定最短路径的顶点的集合 初始时 U ={V0} 1）长度最短的最短路径是边数为1的长度最小的路径。 2）下一条长度最短的路径： ① Vi ? V - U ，先求出V0 到Vi 中间只经 U 中结点的最短路径； ② 上述最短路径中长度最小者即为下一条长度最短的路径； ③ 将所求最短路径的终点加入U 中； 3）重复2）直到求出所有的最短路径 §5.5 最短路径 100 60 10 10 5 30 50 20 V5 V4 V0 V1 V2 V3 始点 终点 最短路径 路径长度 V0 V1 无 V2 （V0，V2） 10 V3 （V0，V4，V3） 50 V4 （V0，V4） 30 V5 （V0，V4，V3，V5） 60 ?有关数据的存储结构 ? 有向连通网络: G ，采用带权邻接矩阵cost[ ][ ]存储 ?具体步骤： （1）初始U={v0}, 用辅助数组 dist[N]。对已经找到最短路径终点的顶点 vi ( i ? U )，vi 所对应的数组分量dist[i]的值为负数；对从v0出发