第7章图.pptVIP

第7章 图 [教学目标] 　 图是一种重要的非线性结构，在系统工程，控制论，人工智能，编译系统等领域中有广泛的应用，熟练掌握其逻辑结构、存储结构各种运算。 。 [重点、难点] 图的抽象数据类型定义，图的实现（邻接矩阵、邻接表、十字链表），图的遍历，图的应用（用普里姆算法求最小生成树、拓扑排序、关键路径、用迪杰斯特拉算法求最短路径）。 [教学方法] 采用讲授、提问、论证上机等方法 实现。 图g中所有顶点偶对vi、vj间的最短路径长度对应一个n阶方阵D。在上述n+1步中，D的值不断变化，对应一个n阶方阵序列。 定义： n阶方阵序列：D-1, D0, D1, D2, …DN-1 其中 : D-1[i][j]= g.arcs[i][j].adj Dk[i][j]=Min{Dk-1[i][j], Dk-1[i][k]+ Dk-1[k][j]} 0≤k≤n-1 显然，DN-1中为所有顶点偶对vi、vj间的最终最短路径长度。 7.5总结与提高 7.5.1 主要知识点 基本概念： 图中顶点间的关系可以任意的，因此图是最复杂的非线性结构，它的表达力强。 图具有有向图、无向图、连通图、强连通图、完全图、赋权图等多种类型。 图的存储结构： 图的存储方式一般有两类，用边的集合方式有邻接矩阵，链接方式有邻接表、十字链表、邻接多重表。 邻接矩阵和邻接表是两种常用的存储结构，适用于有向图（网）和无向图（网）表示与处理。 图的基本操作： 由于图中结点间可以是多对多的关系，为实现图的遍历必须设置访问标志数组，以防止走回路或未访问到。 图的遍历规律有两种：深度优先遍历DFS和广度优先遍历BFS。可用用邻接矩阵和邻接表实现深度优先遍历和广度优先遍历算法。 深度优先遍历算法是以递归技术为支持，而广度优先遍历算法是以队列技术为支持。 图的应用： 图的遍历算法是图应用的重要基础。求解生成树、最小生成树、连通分量，拓扑排序、关键路径、单源最短路径及所有顶点之间的最短路径的重要算法应用。 7.5.2 典型题例 例7.1 求距离顶点v0的路径长度为k的所有顶点 已知无向图g，设计算法求距离顶点v0的最短路径长度为K的所有顶点，要求尽可能节省时间。 【问题分析】由于题目要求找出路径长度为k的所有顶点，故从顶点v0开始进行广度优先有哪些信誉好的足球投注网站，将一步可达的、两步可达的…直至k步可达的所有顶点记录下来，同时用一个队列记录每个结点的层号，输出第K+1层的所有结点即为所求。 【算法描述】 void bfsKLevel(Graph g, int v0, int K) { InitQueue( Q1); /* Q1是存放已访问顶点的队列 */ InitQueue( Q2); /* Q2是存放已访问顶点层号的队列 */ for ( i=0; i g .vexnum; i++) visited[i]=FALSE; /* 初始化访问标志数组 */ visited[v0]=TRUE; Level=1; EnterQueue( Q1, v0); EnterQueue( Q2, Level); while (! IsEmpty( Q1) LevelK+1) { v=DeleteQueue( Q1); /* 取出已访问的顶点号 */ Level=DeleteQueue( Q2); /* 取出已访问顶点的层号 */ w=FirstAdjVertex(g, v); /* 找第一个邻接点 */ while ( w!=-1 ) { if (! visited[w] ) { if (Level==K) printf(“%d”, w); /* 输出符合条件的结点 */ visited[w]=TRUE; EnterQueue( Q1, w); EnterQueue( Q2, Level+1); } w=NextAdjVertex(g, v, w); /* 找下一个邻接点 */ } } } 例7.3 求图的中心顶点 假设有一个公司在某个地区有n个产品销售点，现根据业务需要打算在其中某个销售点上建立一个中心仓库，负责向其它销售点提供产品。由于运输线路不同，运输费用也不同。假定每天需要向每个销售点运输一次产品，那么应将中心仓库建在哪个销售点上，才能使运输费用达到最低。 【问题分析】这是一个求图的中心顶点的问题：即在一个带权图G中，求出这样一个顶点v，使得v到其余顶点的最短路径长度之和最小。首先用弗罗伊德算法求出各个顶点之间的最短路径长度，然后再求出每个顶点到其余各顶点的最短路径长度之和，从中选