清华大学：《数据结构》课程教材PPT教学课件（C语言版）第七章 图（7.1-7.3）

第七章图 图的定义 图的存储结构 图的遍历 图的应用

第七章 图 • 图的定义 • 图的存储结构 • 图的遍历 • 图的应用

7.1图的定义和术语 1.图 有向图( Digragh) 无向图( Undigraph) 图也是一种非线性地数据结构 其抽象数据类型见书P156

7.1 图的定义和术语 1. 图 有向图（Digragh） 无向图（Undigraph） 图也是一种非线性地数据结构 其抽象数据类型见书P156

7.1图的定义和术语 ·有向图( Digragh) G=(V,{A}) 其中,V为顶点的有穷非空集合 A}.为顶点之间的关系集合 a.dl② G1=(V,{A}) V={v1,v2,v3,v4} A={,,,} ④其中表示从x到y的一条弧(arc),A为弧集合,x为弧 尾(tai),y为弧头(head)

7.1 图的定义和术语 • 有向图（Digragh） G=（V，{A}） 其中，V为顶点的有穷非空集合 {A}为顶点之间的关系集合 G1=（V，{A}） V={v1, v2, v3, v4} A={, , , } 其中表示从x到y的一条弧（arc），A为弧集合，x为弧 尾（tail），y为弧头（head) ① ② ③ ④ G1

7.1图的定义和术语 无向图( Undigraph) G=(V,{E}) 其中,V同有向图,{E为顶点之间的关系集合, E为边集合 ①G2②G2=(V,{4}) V={v1,v2,v3,v4,v5} E={(v1,v2),(v1,v4),(v2,v3),(3,v4),(v2,v5),(v3,v5)} 其中,(x,y)表示x与y之间的一条连线,称为边(edge

7.1 图的定义和术语 • 无向图（Undigraph） G=(V,{E}) 其中，V同有向图，{E}为顶点之间的关系集合， E为边集合 G2=（V，{A}） V={v1, v2, v3, v4, v5} E={(v1, v2), (v1, v4), (v2, v3), (v3, v4), (v2,v5), (v3,v5)} 其中，(x, y)表示x与y之间的一条连线，称为边（edge） ① G2 ② ③ ④ ⑤

7.1图的定义和术语 设m为顶点数,c为边或弧的条数 对无向图有:0<=e<=n(m-1)2 有向图有:0<=e<=m(n-1) 证明:每个顶点至多有n-1条边与其它的n-1个顶点相 连,则m个顶点至多有n(m-1)条边。但每条边连 接2个顶点,故最多为n(n-1)/2

7.1 图的定义和术语 设n为顶点数，e为边或弧的条数 对无向图有：0<=e<=n(n-1)/2 有向图有：0<=e<=n(n-1) 证明：每个顶点至多有n-1条边与其它的n-1个顶点相 连，则n个顶点至多有n(n-1)条边。但每条边连 接2个顶点，故最多为n(n-1)/2

7.1图的定义和术语 2.完全图 边达到最大的图 无向完全图:边数为n(n-1)2的无向图 有向完全图:弧数为n(n-1)的有向图 权:与图的边或弧相关的数 网:边或弧上带有权值的图

7.1 图的定义和术语 2. 完全图 边达到最大的图 • 无向完全图：边数为n(n-1)/2的无向图 • 有向完全图：弧数为n(n-1)的有向图 权：与图的边或弧相关的数 网：边或弧上带有权值的图

7.1图的定义和术语 3.顶点的度TD(v) 无向图:为依附于顶点V的边数 有向图无向图的度数为依附于顶点v为V的入度,记 的边数;有向图的度数等于以的弧数(称为v 顶点v为弧头的弧数与以顶点v即: 结论:为弧尾的弧数之和 无向图 有向图 e=1/2(∑TD(v) ∑ID(v)=∑0D(v)

7.1 图的定义和术语 3. 顶点的度TD（V） 无向图：为依附于顶点V的边数 有向图：等于以顶点V为弧头的弧数（称为V的入度，记 为ID（V））与以顶点V为弧尾的弧数（称为V 的出度，记为OD（V））之和。即： TD（V）=ID（V）+OD（V） • 无向图 n e= 1/2（∑TD(vi)） i=1 结论： • 有向图 n n e= ∑ID(vi)=∑OD(vi) i=1 i=1 无向图的度数为依附于顶点v 的边数；有向图的度数等于以 顶点v 为弧头的弧数与以顶点v 为弧尾的弧数之和

7.1图的定义和术语 4.路径 无向图:顶点v到v的路径是一个顶点序列(v=VaV,,vmrv) 其中,(w,v)∈E,1<j=m 有向图:顶点v到v的路径是有向的顶点序列(v=vmVm,,iwm=y) 其中,(v、)∈A,1<=j<=m 几个概念: 路径长度:路径上边或弧的数目 回路或环:首尾顶点相同的路径,称为回路或环。即: (v=v0,vil,… 简单路径:路径中不含相同顶点的路径 简单回路:除首尾顶点外,路径中不含相同顶点的回路

7.1 图的定义和术语 4. 路径 无向图：顶点v到v’的路径是一个顶点序列（v=vi0, vi1, … , vim=v’） 其中，（vij-1,vij）∈E, 1<=j<=m 有向图： 顶点v 到v’的路径是有向的顶点序列（v=vi0, vi1, … , vim=v’） 其中，（vij-1,vij）∈A, 1<=j<=m 几个概念： 路径长度：路径上边或弧的数目 回路或环：首尾顶点相同的路径，称为回路或环。即： （v=vi0, vi1, … , vim=v’=v） 简单路径：路径中不含相同顶点的路径 简单回路：除首尾顶点外，路径中不含相同顶点的回路

7.1图的定义和术语 5.连通 顶点连通:若顶点v到顶点v有路径,则称顶点v与v是连通的 连通图:包括无向连通图和有向连通图 无向图:若图中任意两个顶点ⅵv都是连通的,则称该图 是连通图v∞vj) 有向图:若图中任意两个顶点ⅵ,都存在从v到v和从 ⅵ到v的路径,则称该有向图为强连通图<vj) 连通分量: 无向图:无向图中极大连通子图,称为连通分量 有向图:有向图中极大强连通子图,称为强连通分量

7.1 图的定义和术语 5. 连通 顶点连通：若顶点v到顶点v’有路径，则称顶点v与v’是连通的 连 通 图 ：包括无向连通图和有向连通图 无向图：若图中任意两个顶点vi,vj都是连通的，则称该图 是连通图(vi<>vj) 有向图：若图中任意两个顶点vi,vj，都存在从vi到vj和从 vj到vi的路径，则称该有向图为强连通图(vi<>vj) 连通分量： 无向图：无向图中极大连通子图，称为连通分量 有向图：有向图中极大强连通子图，称为强连通分量

7.1图的定义和术语 5.连通 连通分量: ② G1有两个强连通分量

7.1 图的定义和术语 5. 连通 连通分量： ① ② ③ ④ G1有两个强连通分量 ① ② ③ ④ G1