第6章讲图 - 副本.ppt

第六章 图;6.1.1 图的定义和基本术语;6.1 图的逻辑结构;6.1 图的逻辑结构;6.1 图的逻辑结构;6.1 图的逻辑结构;6.1 图的逻辑结构;6.1 图的逻辑结构;;6.1 图的逻辑结构;6.1 图的逻辑结构;6.1 图的逻辑结构;6.1 图的逻辑结构;6.1 图的逻辑结构;6.1 图的逻辑结构;6.1 图的逻辑结构;6.1 图的逻辑结构;6.1 图的逻辑结构;6.1 图的逻辑结构;;6.1 图的逻辑结构;;6.2 图的存储结构及实现;6.2 图的存储结构及实现;6.2 图的存储结构及实现;6.2 图的存储结构及实现;6.2 图的存储结构及实现;6.2 图的存储结构及实现;6.2 图的存储结构及实现;6.2 图的存储结构及实现;邻接矩阵中图的基本操作——顶点的增删 ;6.2 图的存储结构及实现;V2;6.2 图的存储结构及实现;邻接矩阵中图的基本操作——广度优先遍历;6.2 图的存储结构及实现;6.2 图的存储结构及实现;6.2 图的存储结构及实现;6.2 图的存储结构及实现;6.2 图的存储结构及实现;6.2 图的存储结构及实现;6.2 图的存储结构及实现;6.2 图的存储结构及实现;6.2 图的存储结构及实现;6.2 图的存储结构及实现;6.2 图的存储结构及实现;6.2 图的存储结构及实现;6.2 图的存储结构及实现;6.2 图的存储结构及实现;6.2 图的存储结构及实现;6.2 图的存储结构及实现;6.2 图的存储结构及实现;6.2 图的存储结构及实现;6.2（补充）无向图的连通性;求解步骤： ;V1;6.3 最小生成树;Prim算法的基本思想:设G=（V，E）是一个具有n个顶点的连通网，T=（U，TE）是G的最小生成树，T的初始状态为U={u0}（u0∈V）,TE={},然后重复执行下述操作：在所有u∈U，v∈V-U的边中找一条代价最小的边(u，v)并入集合TE，同时v并入U，直至U=V为止。此时TE中必有n-1条边，T就是最后得到的最小生成树。 ;U={A} ;6.3 最小生成树;数据结构设计：设置一维数组lowcost[n]:用来保存集合V-U中各顶点与集合U中顶点最短边的权值，lowcost[v]=0表示顶点v已加入最小生成树中;一维数组adjvex[n]：用来保存依附于该边在集合U中的顶点。;i 数组;例：;例：;例：;例：;例：;例：;例：;1. 初始化两个辅助数组lowcost和adjvex； 2. 输出顶点v0，将顶点v0加入集合U中； 3. 重复执行下列操作n-1次 3.1 在lowcost中选取最短边，取adjvex中对应的顶点序号k； 3.2 输出顶点k和对应的权值； 3.3 将顶点k加入集合U中； 3.4 调整数组lowcost和adjvex；;6.3.3.克鲁斯卡尔（Kruskal）算法 ;;1. 初始化：U=V； TE={ }； 2. 循环直到T中的连通分量个数为1 2.1 在E中寻找最短边(u，v); 2.2 如果顶点u、v位于T的两个不同连通分量，则 2.2.1 将边(u，v)并入TE； 2.2.2 将这两个连通分量合为一个； 2.3 在E中标记边(u，v)，使得(u，v)不参加后续最短边的选取；;3. 破回路法;6.4 最短路径;问题描述:给定带权有向图G＝（V，E）和源点v∈V，求从v 到G中其余各顶点的最短路径。 ;;图的存储结构：带权的邻接矩阵存储结构 ;1. 初始化数组dist、path和s； 2. while (s中的元素个数n) 2.1 在dist[n]中求最小值，其下标为k（则vk为正在生成的终点）； 2.2 输出dist[j]和path[j]； 2.3 修改数组dist和path； 2.4 将顶点vk添加到数组s中；;;;;;;6.4.2. 所有对顶点之间的最短路径 ;图的存储结构 :邻接矩阵 辅助数组dist[n][n] :存放在迭代过程中求得的最短路径长度。递推公式： 辅助数组path[n][n]：在迭代中存放从vi到vj的最短路径，初始为path[i][j]=”vivj”。;void Floyd(MGraph G) ??????????? { for (i=0; iG.vertexNum; i++) ?????????? for (j=0; jG.vertexNum; j++) ??????????? { dist[i][j]=G.arc[i][j]; ?????? if (dist[i][j]!=∞) pa