0467.cC
海量文库 文档专家
当前位置:首页 >> >>

第6章数据结构-图-jy-PPT精选文档_图文

教学目标 1. 掌握图的基本概念及相关术语和性质 2. 熟练掌握图的邻接矩阵和邻接表两种存储表示方法 3. 熟练掌握图的两种遍历方法DFS和BFS 4. 熟练掌握最短路算法(Dijkstra算法、Floyd 算法) 5. 掌握最小生成树的两种算法 6. 掌握拓扑排序算法的思想 7. 了解关键路径有关概念及求解过程 6.1 图的定义的定义和术语 6.1.1 图的定义 图(Graph)的定义: 图G由两个集合V和E组成,记为G=(V,E),其中, V是顶点(数据元素)的有穷非空集合,E是V中顶点偶 对的有穷集合,这些顶点偶对称为边 。 无向图:每条边都是无方向的图。 在无向图G中,顶点对(x, y) 是无序 的, (x, y) 与(y ,x) 是同一条边。 有向图:每条边都是有方向的图。 在有向图G中,顶点对<x, y>是有序 的, <x, y>与<y ,x>不是同一条边。 在有向图G中,边也称为弧。 无向图G1 V1 V3 V4 V5 V2 有向图G2 V1 V2 V3 V4 6.1.2 图的基本术语 (1) 子图:设有两个图G=(V,E) 和G?=(V?,E?), 且 V??V, E??E, 则称 G? 为 G 的子图。 A B E C 图G F A E C F 图G的子图G3 B C 图G的子图G1 B 图G的子图G2 6.1.2 图的基本术语 (2) 无向完全图和有向完全图: 假设图中有 n 个顶点,e 条边。 对于无向图,含有 e=n(n-1)/2 条边, 则称为无向完全图。 对于有向图,含有 e=n(n-1) 条边, 则称为有向完全图。 (3) 稀疏图和稠密图: 边或弧的个数 e<nlogn的图称为稀 疏图,否则称作稠密图。 有向完全图 无向完全图 6.1.2 图的基本术语 (4) 权和网: 图中的边可标上具有某种含义的数值,该数值称为 边上的权。 权可表示为从一个顶点到另一顶点的距离或耗费。 这种边带权的图称网(网络)。 15 A 11 21 9 B 3 7 E C 2 网络 F (5) 邻接点: 在无向图G中,假若边(v , w) ∈G,则称顶 点v 和w 互为邻接点。而边(v , w) 与顶点v和 w相关联。 B A F E C D (6) 度、入度和出度: 顶点v的度:是和顶点v 关联的边的数目。记为TD(v)。 例如: TD(A) = 2 TD(B) = 3 A F E B C D 对有向图, 由于弧有方向性,有入度和出度之分。 入度: 以顶点v为头的弧的数目。记为ID(v)。 出度: 以顶点v为尾的弧的数目。记为D(v)。 TD(v)=ID(v)+OD(v) 例如: ID(B) = 2 OD(B) = 1 TD(B) = 3 假设图中有n个顶点e条边,则: 1 n e ? ? TD(v ) i 2 i ?1 B C F A E (7) 路径和路径长度: 设图 G=(V,E) 中有一个顶点序列 { u=vi,0,vi,1, …, vi,m=w},其中(vi,j-1,vi,j)?E, 1≤j≤m, 则 称从顶点u 到顶点w 之间存在一条路径。 路径上边或弧的数目称作路径长度。 A E C F B 如:从 A 到 F的路径 {A,B,C,F}长度为 3 。 (8) 回路或环: 第一个顶点和最后一个顶点 相同的路径称为回路或环。 A B C F E 如:路径 {A,B,C,F,A}。 (9) 简单路径、简单回路: 简单路径:指序列中顶点不重复出现的路径。 如:从 A 到 F 的路径 {A,B,C,F}。 简单回路:指序列中第一个顶 点和最后一个顶点相同的简单 路径。 A E C F B (10) 连通、连通图、连通分量: 在无向图G中,如果顶点v到顶点w有路径, 则称v和w是连通的。 在无向图G中,如果任意两个顶点之间都有 路径,则称此图为连通图。 H G L K I J A F E B C D 若无向图为非连通图,则图中各个极大连通 子图称作此图的连通分量。 (11) 强连通图、强连通分量: 对有向图, 若任意两个顶点之间都存在一条 有向路径,则称此有向图为强连通图。 否则,其各个强连通子图称作它的强连通分 量。 A B C 强连通图 A E F B C F 非强连通图 E (12) 连通图的生成树: 假设一个连通图有 n 个顶点和 e 条边,其中 n-1 条边和 n 个顶点构成一个极小连通子图, 称该极小连通子图为此连通图的生成树。 对非连通图,称由各个连 通分量的生成树的集合为此 非连通图的生成森林。 B A F G C D E B A F C D E (13)有向树和生成森林: 有一个顶点的入度为0,其余顶点的入度均为 1的有向图称为有向树。 A B E C F 有向树 一个有向图的生成森林由若干棵有向树组 成,含有图中全部顶点,但只有足以构成若 干棵有向树的弧。 (14) 有根图: 在一个有向图中,若存在一个顶点v,从该 顶点有路径可以到达图中其它所有顶点,则称 此有向图为有根图,v称作图的根。 1 2 3 有向图G 6.2 图的存储表示 一、图的数组(邻接矩阵)存储表示 二、图的邻接表存储表示 6.2.1 邻接矩阵 设G(V,E)是具有n个顶点的图,则G的邻接矩 阵A可定义为: A[i][j]= 0 (i,j)?E 1 (i,j)?E { B C A F E 无向图图G D A B C D E F 无向图的邻接矩阵为 对称矩阵。 0 1 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 0 0 0 0 1 1 0 0 图G的邻接矩阵 A B C D E A B 顶点表 C D E 有向图图G 0 0 0 1 0 1 0 0 1 0 0 1 0

网站首页 | 网站地图
All rights reserved Powered by 0467资源网 0467.cc
copyright ©right 2014-2019。
文档资料库内容来自网络,如有侵犯请联系客服。liunxqq@126.com