数据结构之图课件.ppt

数据结构 第7章 图 第7章 图 知 识 点 图的逻辑结构特征及图的基本术语 邻接矩阵和邻接表两种图的存储结构的特点及适用范围 深度优先搜索和广度优先搜索两种遍历算法的特点和执行过程 生成树和最小生成树的概念及构造最小生成树的prim和kruskal算法 最短路径的含义及求最短路径的算法 拓扑排序的基本思想和步骤 关键路径法及其在管理科学中的作用 难 点 图的遍历、最小生成树、最短路径、拓朴排序算法的理解 关键路径法求关键活动和关键路径的方法 要 求 熟练掌握以下内容： 图的存储结构 图的遍历算法 了解以下内容： 图的最小生成树和求最小生成树算法的基本思想 带权有向图的最短路径问题 利用AOV网络的拓朴排序问题 利用AOE网络的关键路径法 7.1 图的定义和基本术语 图是一个二元组 G=（V，E） 其中 V={x | x?data object} 点的集合 E={x,y | p(x,y) ? x, y ? V} 边的集合 P(x,y)表示从x到y的一条边 无向图：对于一个图G，若边集合E（G）为无向边的集合，则称该图为无向图。 有向图：对于一个图G，若边集合E（G）为有向边的集合，则称该图为有向图。 图7.1 有向图与无向图 无向图G1 完全图：在一个有n个顶点的无向图中，若每个顶点到其它（n-1）个顶点都连有一条边，这种图称为完全图。完全图中共有n(n-1)/2条边，（Complete graph，也称完备图）。 权和网络：有些图， 对应每条边有一相应的数值，这个数值叫做该边的权(Weight)。边上带权的图称为带权图，也称为网络(Network)。 子图：设有两个图G =(V,E)和G’=(V’,E’)，若V(G’)?V(G)，E(G’)? E(G)，则称G’是G的子图(Subgraph)。 例如图6.3所示的图是图6.1中G1的一些子图。 图7.3 子图 顶点的度：图中与每个顶点相连的边数，叫该顶点的度(Degree)，记作TD（V）。 入度、出度：对于有向图，顶点的度分为入度和出度，入度是以该顶点为终点的入边数目；出度是以该顶点为起点的出边数目，该顶点的度等于其入度和出度之和。分别记作 ID（V），OD（V）。 路径（回路）：若从某顶点Vp出发，沿一些边经过顶点V1,V2,…,Vm到达，Vq，则称顶点序列(Vp, V1,V2,…,Vm, Vq)为从Vp到Vq的路径(Path)。 若其中间顶点不重复，则称简单路径；若第1个顶点和最后一个顶点相同，则称为回路。 路径长度：对于无权的图，路径长度指的是沿此路径上边的数目；对于有权图，一般是取沿路径各边的权之和作为此路径的长度。 连通、连通图：在无向图中，如果从顶点Vi到顶点Vj之间有路径，则称这两个顶点是连通的。如果图中任意一对顶点都是连通的，则称此图是连通图(Connected graph)。 连通分量：非连通图的每一个极大连通子图叫连通分量(Connected Component)。 图7.4 非连通图G 强连通图和强连通分量：在有向图G中，如果从顶点Vi到顶点Vj和从顶点Vj到顶点Vi之间都有路径，则称这两个顶点是强连通的。如果图中任何一对顶点都是强连通的，则此图叫做强连通图。非强连通图的每一个极大强连通子图叫做强连通分量。 生成树：有n个顶点，n-1条边的树，且 V=V， E?E。 图7.5 图G2的强连通分量 7.2 图的存储结构 1。邻接矩阵表示法 邻接矩阵是表示顶点之间相邻关系的矩阵。所谓两顶点的相邻关系即它们之间有边相连。 若图有n个结点数，邻接矩阵是一个（n×n）阶方阵。 对无权图， 图7.6 无向图的邻接矩阵 图7.7 有向图的邻接矩阵 可以看出: 无向图的邻接矩阵是对称的， 即若A[i，j]=1，必有A[j，i]=1。所以，只存储其上三角阵元素即可. 2. 对无向图, 结点Vi的度, 是邻接矩阵中,第i行1的个数. 对有向图, 邻接矩阵一般是不对称的，A[i，j]不一定等于A[j，i]。 结点Vi的出度OD(Vi), 是邻接矩阵中,第i行1的个数. 结点Vi的入度ID(Vi), 是邻接矩阵中,第i列1的个数. 对于有权图(网） 例： 邻接矩阵用二维数组即可存储，定义如下： int adjmatrix ARRAY[n][n]; 产生无向图邻接矩阵算法 void creatgraph (int adjarray[ ][ ]) { int i, j, v1, v2, num; scanf (“%d”,num