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

第6章数据结构-图-jy_图文

教学目标 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 V2 V3 V4 V5 有向图G2 V1 V2 V3 V4 6.1.2 图的基本术语 (1) 子图:设有两个图G=(V,E) 和G=(V,E), 且 VV, EE, 则称 G 为 G 的子图。 A B E CF 图G B C 图G的子图G1 B 图G的子图G2 A E CF 图G的子图G3 6.1.2 图的基本术语 (2) 无向完全图和有向完全图: 假设图中有 n 个顶点,e 条边。 对于无向图,含有 e=n(n-1)/2 条边, 则称为无向完全图。 对于有向图,含有 e=n(n-1) 条边, 则称为有向完全图。 (3) 稀疏图和稠密图: 边或弧的个数 e<nlogn的图称为稀 疏图,否则称作稠密图。 无向完全图 有向完全图 6.1.2 图的基本术语 (4) 权和网: 图中的边可标上具有某种含义的数值,该数值称为 边上的权。 权可表示为从一个顶点到另一顶点的距离或耗费。 这种边带权的图称网(网络)。 15 B7 3 A 9 11 E 21 C2 F 网络 (5) 邻接点: 在无向图G中,假若边(v , w) ∈G,则称顶 点v 和w 互为邻接点。而边(v , w) 与顶点v和 w相关联。 B C A D F E (6) 度、入度和出度: 顶点v的度:是和顶点v 关联的边的数目。记为TD(v)。 例如: TD(A) = 2 TD(B) = 3 B C 对有向图, A D 由于弧有方向性,有入度和出度之分。 F E 入度: 以顶点v为头的弧的数目。记为ID(v)。 出度: 以顶点v为尾的弧的数目。记为D(v)。 A TD(v)=ID(v)+OD(v) B E 例如: ID(B) = 2 OD(B) = 1 TD(B) = 3 C F 假设图中有n个顶点e条边,则: e 1 2 i n TD( 1 vi ) (7) 路径和路径长度: 设图 G=(V,E) 中有一个顶点序列 { u=vi,0,vi,1, …, vi,m=w},其中(vi,j-1,vi,j)E, 1≤j≤m, 则 称从顶点u 到顶点w 之间存在一条路径。 路径上边或弧的数目称作路径长度。 A B E CF 如:从 A 到 F的路径 {A,B,C,F}长度为 3 。 (8) 回路或环: A 第一个顶点和最后一个顶点 相同的路径称为回路或环。 如:路径 {A,B,C,F,A}。 B C E F (9) 简单路径、简单回路: 简单路径:指序列中顶点不重复出现的路径。 如:从 A 到 F 的路径 {A,B,C,F}。 A 简单回路:指序列中第一个顶 点和最后一个顶点相同的简单 路径。 B C E F (10) 连通、连通图、连通分量: 在无向图G中,如果顶点v到顶点w有路径, 则称v和w是连通的。 在无向图G中,如果任意两个顶点之间都有 路径,则称此图为连通图。 H I B C G JA D L K F E 若无向图为非连通图,则图中各个极大连通 子图称作此图的连通分量。 (11) 强连通图、强连通分量: 对有向图, 若任意两个顶点之间都存在一条 有向路径,则称此有向图为强连通图。 否则,其各个强连通子图称作它的强连通分 量。 A A B EB E CF 强连通图 CF 非强连通图 (12) 连通图的生成树: 假设一个连通图有 n 个顶点和 e 条边,其中 n-1 条边和 n 个顶点构成一个极小连通子图, 称该极小连通子图为此连通图的生成树。 对非连通图,称由各个连 B 通分量的生成树的集合为此 A 非连通图的生成森林。 B C E F C D E A D F G (13)有向树和生成森林: 有一个顶点的入度为0,其余顶点的入度均为 1的有向图称为有向树。 A B E C F 有向树 一个有向图的生成森林由若干棵有向树组 成,含有图中全部顶点,但只有足以构成若 干棵有向树的弧。 (14) 有根图: 在一个有向图中,若存在一个顶点v,从该 顶点有路径可以到达图中其它所有顶点,则称 此有向图为有根图,v称作图的根。 1 2 3 有向图G 6.2 图的存储表示 一、图的数组(邻接矩阵)存储表示 二、图的邻接表存储表示 A B E CD 有向图图G 有向图的邻接矩阵 为非对称矩阵。 顶点表 A 01001 B 00100 C 00010 D 11000 E 00100 图G的邻 接矩阵 建立无向网络邻接矩阵算法 CREATGRAPH(AMGraph &G) { cin>>G.vexnum>>G.arcnum; for(i=0;i< G.vexnum ;i++) cin>> G.vexs[i];//读入顶点信息 typ执ed行ef时s间trOuc(nt

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