合取警院 第10章图及其应用 HEFEI UNIVERSITY 第10章 图及其应用 m10.1图的概念 10.2图的存储 10.3图的遍历 10.4生成树和最小生成树 10.5最短路径 10.6有向无环图的应用 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(200711一20)
第10章 图及其应用 1 ☞10.1 图的概念 10.2 图的存储 10.3 图的遍历 10.4 生成树和最小生成树 10.5 最短路径 10.6 有向无环图的应用 第10章 图及其应用
⑧合取学院 第10章图及其应用 HEFEI UNIVERSITY 图(Graph):是一种网状数据结构。是顶点集V和 连接这些顶点的弧集（边集）VR所组成的结构记为： G=(V.VR 有向圆：若图中的边是顶点的有序对，则称此图为 有向图。有向边又称为弧，通常用尖括弧表示一条有向 边，〈V,v〉表示从顶点v到v的一段弧，v称为边的始点 回或弧尾)，v称为边的终点回或弧头)，〈V,V〉和〈V,V》 代表两条不同的弧。 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(20071山20)
第10章 图及其应用 2 图(Graph)：是一种网状数据结构。是顶点集V和 连接这些顶点的弧集(边集)VR所组成的结构记为 : G=(V,VR） 有向图：若图中的边是顶点的有序对, 则称此图为 有向图。 有向边又称为弧, 通常用尖括弧表示一条有向 边, 〈 vi , vj〉表示从顶点vi到vj的一段弧, vi称为边的始点 (或弧尾), vj称为边的终点(或弧头), 〈 vi ,vj〉和〈 vj , vi〉 代表两条不同的弧。 1 3 2
⑧合飞学院 第10章图及其应用 HEFEI UNIVERSITY 无向圆：若图中的边是顶点的无序对，则称此图 为无向图。 通常用圆括号表示无向边，(W,v)表示顶点v和v间 相连的边。在无向图中(vV)和W,V)表示同一条边 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(2007-11-20)
第10章 图及其应用 3 无向图：若图中的边是顶点的无序对, 则称此图 为无向图。 通常用圆括号表示无向边, (vi , vj )表示顶点vi和vj间 相连的边。在无向图中(vi , vj )和(vi , vj )表示同一条边. 2 3 4 1
⑧合取学院 第10章图及其应用 HEFEI UNIVERSITY 完全图、稠密图、稀疏图 具有n个顶点，（血-1）/2条边的图，称为完全无向圆 具有n个顶点，(-1)条弧的有向图，称为完全有向图。 完全无向图和完全有向图都称为完全圆。 对于一般无向图，顶点数为n,边数为e,则0< ≤n(m-1)/2 对于一般有向图，顶点数为n,弧数为e,则 0≤e≤n(m-1) 当一个图接近完全图时，则称它为调密图，相反地 当一个图中含有较少的边或弧时，则称它为稀疏圆 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(2007一11一20)
第10章 图及其应用 4 完全图、稠密图、稀疏图 具有n个顶点，n(n-1)/2条边的图，称为完全无向图， 具有n个顶点，n(n-1) 条弧的有向图,称为完全有向图。 完全无向图和完全有向图都称为完全图。 对于一般无向图，顶点数为n，边数为e，则 0≤e ≤n(n-1)/2。 对于一般有向图 ，顶点数为n，弧数为e， 则 0≤e≤n(n-1) 。 当一个图接近完全图时，则称它为稠密图，相反地， 当一个图中含有较少的边或弧时，则称它为稀疏图
⑧合取学院 第10章图及其应用 HEFEI UNIVERSITY 子圄：对于图G=V,VR),G=(V',VR),若有V'V VT二VR,则CG'是G的一个子图。 下图给出了G与其子图G' 6 图G 图G' 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(20071山20)
第10章 图及其应用 5 子图：对于图G=(V, VR),G′=(V′,VR′),若有V′ V, VR′ VR, 则称图G′是G的一个子图。 下图给出了G与其子图G ′。 2 4 3 5 1 6 7 图G 4 3 5 1 6 7 图G ′
⑧合取学院 第10章图及其应用 HEFEI UNIVERSITY 邻接点 对于无向图Gy,VR),如果边(w,v')∈VR,则 称顶点y,v'互为接点即v,如接擒翅项点2v')依 附于顶点v和vO成者说选(V，V网粮点相关联。 对于有向图G=(V,V频言，若弧∈VR, 则称顶点v邻接到联v,项点如機息壶为成煮说 孤与顶点v种v相关联。 ④ 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(2007-1120)
第10章 图及其应用 6 邻接点 对于无向图 G=(V, VR)，如果边(v，v′)∈VR， 则 称顶点v, v′互为邻接点，即v, v′相邻接。边（v, v′）依 附于顶点v和v′ ，或者说边（v， v′）与顶点v和v′相关联。 对于有向图G=(V，VR)而言，若弧∈VR， 则称顶点v邻接到顶点v′ ，顶点v′邻接自顶点v，或者说 弧与顶点v和v′相关联。 2 3 4 1 1 3 2 如：顶点1、2互为邻接点 如：顶点1邻接到顶点2 顶点2邻接自顶点1
⑧ 合取警院 第10章图及其应用 HEFEI UNIVERSITY 权与网 在实际应用中，图的边或弧上往往与具有一定意义 的数有关，即每一条边都有与它相关的数，称为权 我们将这种带权的图叫做赋权图或网，如图所示。 16 6 33 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(2007-1120)
第10章 图及其应用 7 权与网 在实际应用中，图的边或弧上往往与具有一定意义 的数有关，即每一条边都有与它相关的数，称为权， 我们将这种带权的图叫做赋权图或网，如图所示。 1 5 2 4 16 19 6 3 18 33 14 21 11 6 5 6 图 7.3
⑧合雕学院 第10章图及其应用 HEFEI UNIVERSITY 路径和回路 路径：所谓顶点v,到顶点v之间的路径，是指顶点序列 VpV1,V2,,Vim,Vg,其中(VpV1),（V1,V2), (Vm,Vg)分别为图中的边。 路径长度：路径上边的数目称为路径长度 简单路径：序列中顶点不重复出观的路径称为简单路径 回路可或环：如果路径的起点和终点相同（即p=vq),则 称此路径为回路或环 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(20071山20)
第10章 图及其应用 8 路径和回路 路径：所谓顶点vp 到顶点vq之间的路径, 是指顶点序列 vp , vi1 , vi2 , …, vim, vq , 其中（ vp ,vi1）, （ vi1 , vi2）, … （ vim, vq ）分别为图中的边。 路径长度：路径上边的数目称为路径长度。 简单路径：序列中顶点不重复出现的路径称为简单路径。 回路或环：如果路径的起点和终点相同(即vp = vq), 则 称此路径为回路或环
⑧合取些院 第10章图及其应用 HEFEI UNIVERSITY 简单回路：除第一顶点与最后一个顶点之外，其它顶点不 重复出现的回路为简单回路或者简单环。 如图所示的无向图中，顶点v1到顶点v5的路径有两条 分别为y,V2,V3,V4与v1,V5,V4,路径长度分别为3和2。 V,到V:的两条路径都为简 单路径。 3 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(20071120)
第10章 图及其应用 9 如图所示的无向图中, 顶点v1到顶点v5的路径有两条, 分别为v1 , v2 , v3 , v4与v1 , v5 , v4 , 路径长度分别为3和2。 v1到v5的两条路径都为简 单路径。 简单回路：除第一顶点与最后一个顶点之外, 其它顶点不 重复出现的回路为简单回路或者简单环
合取警院 第10章图及其应用 HEFEI UNIVERSITY 连通图和强连通图 在无向图中，若从顶点到顶点有路径，则称顶点 和顶点是连通的。若任意两个顶点都是连通的，则称 此无向图为连通图，否则称为非连通图。 连通图和非连通图示例见图： (a) 连通图 (b)非连通图 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(2007-11-20) 10
第10章 图及其应用 10 连通图和强连通图 在无向图中，若从顶点i到顶点j有路径，则称顶点i 和顶点j是连通的。若任意两个顶点都是连通的，则称 此无向图为连通图，否则称为非连通图。 连通图和非连通图示例见图: 3 1 2 4 1 2 3 5 4 （a） 连通图 (b) 非连通图 图 7-4 连通图和非连通图