华中科技大学：《数据结构》课程教学资源（PPT课件讲稿）第七章 图 Graph 7.1 图的定义和术语 7.2 图的存储结构

数结 华中科技大学 计犷机学院(9 9008=8799

2001 -- 12 -- 27/29 华中科技大学 数据结构计算机学院(9)

第七章图( Graph) 7.1图的定义和术语 ●图 图G由顶点集V和关系集E组成,记为 V是顶点(元素)的有穷非空集, E是两个顶点之间的关系的集合。 G1 ●若顶点a,C之间的关系为有序对,∈E, 则称〈a,C>为从a到c的一条弧/有向边; a是的弧尾, C是的弧头; G是有向图 W G1=V1,E1, V1=A, B, C, D, El E1={,,,,}

第七章 图(Graph) 7.1 图的定义和术语 ● 图 图G由顶点集V和关系集E组成,记为 G=(V,E) V是顶点(元素)的有穷非空集， E是两个顶点之间的关系的集合。 A B C E D ● 若顶点a,c之间的关系为有序对,∈E, 则称为从a到c的一条弧/有向边； a是的弧尾， c是的弧头； G是有向图。 例 G1={V1,E1}, V1={A,B,C,D,E} E1={,,,,} G1

●若顶点a,b之间的关系为无序对(a,b) 则称(a,b)为无向边(边),G是无向图。 无向图可简称为图 (a,b)依附于a和b,(a,b)与a和b相关联 例G2={V2,E2}, V2={1,2,3,4,5,6}, G2 E2={(1,3),(1,5),(3,5),(4,6)} ●完全图有n个顶点和n(n-1)/2条边的无向图 B G2 G4 e=1(1-1)/2e=2(2-1)/2e=3(3-1)/2e=4(4-1)/2e=5(5-1)/2 0 10

1 2 5 6 3 G2 ● 若顶点a,b之间的关系为无序对(a,b), 则称(a,b)为无向边(边）,G是无向图。 无向图可简称为图。 (a,b)依附于a和b, (a,b)与a和b相关联 例 G2={V2,E2}, V2={1,2,3,4,5,6}, E2={(1,3),(1,5),(3,5),(4,6)} 4 v1 A v2 C v3 G1 G2 G3 G4 G5 v1 v1 B v2 D A C B D E ● 完全图----有n个顶点和n(n-1)/2条边的无向图 e=1(1-1)/2 =0 e=2(2-1)/2 =1 e=3(3-1)/2 =3 e=4(4-1)/2 =6 e=5(5-1)/2 =10

●有向完全图一有n个顶点和n(n-1)条弧的有向图 G1 G2 e=1(1-1)e=2(2-1) e=3(3-1) 0 ●网( Network)-边(弧)上加权( weight)的图 4 B 无向网G1 有向网G2

● 有向完全图----有n个顶点和n(n-1)条弧的有向图。 ● 网(Network)----边(弧)上加权(weight)的图。 1 2 3 G1 G2 G3 1 1 2 1 2 3 无向网G1 4 A B C 4 15 5 9 9 4 3 有向网G2 e=1(1-1) =0 e=2(2-1) =2 e=3(3-1) =6

●对图G=(V,E)和G=(V,E'), 若VcV且E≌E,则称G是G的一个子图 3)(4 G G1 G2 ②2③④4 G3 G4 G1,G2,G3是G的子图 G4不是G的子图

● 对图 G=(V,E)和G'=(V',E')， 若V' V 且 E' E，则称G'是G的一个子图 1 2 3 G 4 1 2 G1 3 4 1 G2 3 4 1 G4 1 2 3 G3 4 G1,G2,G3是G的子图 G4不是G的子图 2

●与顶点x相关联的边(x,y)的数目, 称为x的度,记作T(x)或D(x), TD(1)=1 ①(2③3 TD(2)=3 ⑤(4 TD(3)=0 GI ,, ●以顶点x为弧尾的弧的数目, 称为x的出度,记作OD(x) A OD(A=1 OD(B)=2 OD(C)=0 以顶点x为弧头的弧的数目, G2 称为x的入度,记作ID(x) ID (A)=1 ID (B)=1 ID (C=1 TD(A=OD (A)ID(A)=2 TD(B)=OD(B)+ID (B)=3

● 与顶点 x相关联的边 (x,y)的数目 , 称为 x 的 度，记作TD(x) 或D(x) ， TD(1)=1 TD(2)=3 TD(3)=0 ● 以顶点 x为弧尾的弧 的数目 , 称为 x 的出度，记作OD(x) 。 OD(A)=1 OD(B)=2 OD(C)=0 ● 以顶点 x为弧头的弧 的数目 , 称为 x 的入度，记作ID(x) 。 ID(A)=1 ID(B)=1 ID(C)=1 TD(A)=OD(A)+ID(A)=2 TD(B)=OD(B)+ID(B)=3 A B C G22 5 4 1 3 G1

对无向图G 若从顶点ⅵ到vj有路径,则称v和ⅴ是连通的 若图G中任意两顶点是连通的,则称G是连通图 2)3(4 G ●若图G是G的一个极大连通子图,则称G是G的一个连通分量。 A FE G1 G2 G3 G有三个连通分量

对无向图G： ● 若从顶点vi到vj有路径,则称vi和vj是连通的。 ● 若图G中任意两顶点是连通的,则称G是连通图。 1 2 3 4 5 6 A F E C B G G D A F E C B G1 D G2 G3 ● 若图G'是G的一个极大连通子图,则称G'是G的一个连通分量。 G G G有三个连通分量

对有向图G ●若在图G中,每对顶点v和vj之间,从ⅵ到vj,且从ⅴj 到ⅵ都存在路径,则称G是强连通图 ●若图G是G的一个极大强连通子图,则称G是G的一个 强连通分量。(强连通图的强连通分量是自身) BC G11 G12 是G1的强连通分量不是G1的强连通分量 B G2 G21 G22 G2有两个强连通分量

对有向图G ● 若在图G中,每对顶点vi和vj之间, 从vi到vj,且从vj 到vi都存在路径,则称G是强连通图。 ● 若图G'是G的一个极大强连通子图,则称G'是G的一个 强连通分量。(强连通图的强连通分量是自身) B C G1 A D B C G11 是G1的强连通分量 A D B C G12 不是G1的强连通分量 A D B C G2 A D B C G21 A D G22 G2有两个强连通分量

●设G=(V,E),G=(V,E'),V=V,若G是连通图, G是G的一个极小连通子图,则G是G的一棵生成树。 B E G T1 (ED T2 T4 G的多棵生成树

● 设G=(V,E),G'=(V',E'),V=V',若G是连通图, G'是G的一个极小连通子图, 则G'是G的一棵生成树。 E D G B A C E D T1 A B C E D T4 B A C E D T3 B A C E D T2 B A C G的多棵生成树

●若有向图G有且仅有一个顶点的入度为0,其余顶点的入度 为1,则G是一棵有向树。 B T1 T2 A ⑥oo T6 T3 T1,T2,T3,T是有向树 T5,T6不是有向树

● 若有向图G有且仅有一个顶点的入度为0，其余顶点的入度 为1,则G是一棵有向树。 E D T1 B C A E D T2 B C A E B T3 A C E E D T4 B A C E D T5 B C A E D T6 A B C T1,T2,T3,T4是有向树 T5,T6不是有向树