数据结构(C++版).ppt

路径长度： 路径长度： 回路（环）：第一个顶点和最后一个顶点相同的路径。 简单路径：序列中顶点不重复出现的路径。 简单回路（简单环）：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。 template class T MGraph::MGraph(T a[ ], int n, int e) { vertexNum=n; arcNum=e; for (i=0; ivertexNum; i++) vertex[i]=a[i]; for (i=0; ivertexNum; i++) //初始化邻接矩阵 for (j=0; jvertexNum; j++) arc[i][j]=0; for (k=0; karcNum; k++) //依次输入每一条边 { cinij; //边依附的两个顶点的序号 arc[i][j]=1; arc[j][i]=1; //置有边标志 } } for (k=0; kG.vertexNum; k++) ????????for (i=0; iG.vertexNum; i++) ???????? for (j=0; jG.vertexNum; j++) ???????? if (dist[i][k]+dist[k][j]dist[i][j]) { ???????? dist[i][j]=dist[i][k]+dist[k][j]; ???????? path[i][j]=path[i][k]+path[k][j]; } } 首先计算以下与关键活动有关的量： 图的存储结构：带权的邻接矩阵存储结构 数组dist[n][n]：存放在迭代过程中求得的最短路径长度。迭代公式： 数组path[n][n]：存放从vi到vj的最短路径，初始为path[i][j]=vivj。 设计数据结构 dist-1[i][j]=arc[i][j] dist k[i][j]=min{distk-1[i][j], distk-1[i][k]+distk-1[k][j]} 0≤k ≤n-1 应用举例——最短路径 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]!=∞) path[i][j]=G.vertex[i]+G.vertex[j]; ??????? else path[i][j]=; } 应用举例——最短路径 Floyd算法——C++描述 应用举例——最短路径 Floyd算法——C++描述 AOV网：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，称这样的有向图为顶点表示活动的网，简称AOV网。 应用举例——拓扑排序 AOV网 什么是工程？工程有什么共性？ AOV网中出现回路意味着什么？ AOV网：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，称这样的有向图为顶点表示活动的网，简称AOV网。 应用举例——拓扑排序 AOV网 2.AOV网中不能出现回路 。 AOV网特点： 1.AOV网中的弧表示活动之间存在的某种制约关系。 什么是工程？工程有什么共性？ C4，C5，C6 数据库原理 C7 C2，C4 计算机原理 C6 C3，C4 数据结构 C5 C1, C2 程序设计 C4 C1 离散数学 C3 无 计算机导论 C2 无 高等数学 C1 先修课 课程名称 编号 应用举例——拓扑排序 C1 C2 C3 C4 C6 C5 C7 AOV网 拓扑序列：设G=(V，E)是一个具有n个顶点的有向图，V中的顶点序列v1, v2, …, vn称为一个拓扑序列，当且仅当满足下列条件：若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在顶点vj之前。 拓扑排序：对一个有向图构造拓扑序列的过程称为拓扑排序 。 应用举例——拓扑排序 拓扑排序 拓扑序列使得AOV网中所有应存在的前驱和后继关系都能得到满足。 基