数据结构7-图.

1、第七章 图(Graph) 图的定义 图的存储结构 图的遍历 最小生成树课堂讨论课堂讨论 设设Hash函数为函数为H(X)=i/2,其中其中i为第一个字为第一个字母在字母表中的序号。试在地址空间母在字母表中的序号。试在地址空间0 13的散列区中，输入关键字序列的散列区中，输入关键字序列:(Jan,Feb,Mar,Apr,Mar,June,July,Aug,Sep,Oct,Nov,Dec)用线性探测开放定址法处理冲突，构造用线性探测开放定址法处理冲突，构造哈希哈希表，并计算查找成功和查找不成功的平均查表，并计算查找成功和查找不成功的平均查找长度找长度ASL。解：H(Jan)=10/2=5 H(Fe

2、b)=6/2=3 H(Mar)=13/2=6 H(Apr)=1/2=0 H(May)=13/2=6 H1=7 H(June)=5 H1=6 H2=7 H3=8 AprFebJanMarMayJune 0 1 2 3 4 5 6 7 8 9 10 11 12 13AprFebJanMar0 1 2 3 4 5 6 7 8 9 10 11 12 13解：H(Jan)=10/2=5 H(July)=5H(Feb)=6/2=3 H1=6,H2,H3,H4=9H(Mar)=13/2=6 H(Aug)=0H(Apr)=1/2=0 H1=1H(May)=13/2=6 H(Sep)=9H1=7 H1=10H(

3、June)=5 H(Oct)=7H1=6 H1=8,H2,H3,H4=11H2=7 H(Nov)=7H3=8 H1=8 H5=12 H(Dec)=2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 AprAugDecFebJanMarMayJuneJulySepOctNov查找成功 ASL=1/12(1*5+2*3+4*1+5*2+6*1) =31/12查找不成功 ASL=(5+4+3+2+1+9+8+7+6+5+4+3+2+1)/14 =60/14 第七章 图(Graph) 图的定义 图的存储结构 图的遍历 最小生成树7.1 7.1 图的定义和术语图的定义和术语 图图 图G由

4、顶点集V和关系集E组成,记为 G=(V,E) V是顶点(元素)的有穷非空集， E是两个顶点之间的关系的集合。ABCED 若顶点a,c之间的关系为有序对有序对,E, 则称为从a到c的一条弧弧/ /有向边有向边； a是的弧尾弧尾， c是的弧头弧头； G是有向图有向图。例 G1=V1,E1, V1=A,B,C,D,E E1=, G112563G2 若顶点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,

5、3),(1,5),(3,5),(4,6)4v1Av2Cv3G1 G2 G3 G4 G5 Bv1v1v2DACBDE 完全图完全图-有n个顶点和n(n-1)/2n(n-1)/2条边的无向图e=1(1-1)/2 =0e=2(2-1)/2 =1e=3(3-1)/2 =3e=4(4-1)/2 =6e=5(5-1)/2 =10 有向完全图有向完全图- -有n个顶点和n(n-1)条弧的有向图。 网网(Network)-边(弧)上加权权(weight)的图。123G1 G2 G3112123无向网G14ABC41559943有向网G2e=1(1-1) =0e=2(2-1) =2e=3(3-1) =6 对图

6、G=(V,E)和G=(V,E)， 若VV且 EE，则称G是G的一个子图子图 123G412G1341G2341G4123G34G1,G2,G3是G的子图 G4不是G的子图2 与顶点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

7、)=3ABCG225413G1 对无向图G： 若从顶点vi到vj有路径,则称vi和vj是连通连通的。 若图G中任意两顶点是连通的,则称G是连通图连通图。123456AFECBGGDAFECBG1DG2G3 若图G是G的一个极大极大连通连通子图子图,则称G是G的一个连通分量连通分量。GGG有三个连通分量有三个连通分量 对有向图G 若在图G中,每对顶点vi和vj之间, 从vi到vj,且从vj 到vi都存在路径,则称G是强连通图强连通图。 若图G是G的一个极大强连通子图极大强连通子图,则称G是G的一个 强连通分量强连通分量。BCG1ADBC G11 是是G1的强连通分量强连通分量ADBC G12不是

8、不是G1的强连通分量强连通分量ADBCG2ADBCG21ADG22G2有两个强连通分量有两个强连通分量 设G=(V,E),G=(V,E),V=V,若G是连通图, G是G的一个极小极小连通连通子图子图, , 则G是G的一棵生成树生成树。EDGBCAEDT1BCAEDT4BCAEDT3BCAEDT2BCAG的多棵生成树 若有向图G有且仅有一个顶点的入度为0，其余顶点的入度 为1,则G是一棵有向树有向树。EDT1BCAEDT2BCAEBT3ACEEDT4BCAEDT5BCAEDT6BCAT1,T2,T3,T4是有向树有向树T5,T6不是有向树有向树 有向图的生成树/生成森林。EDGBCAEBF2AD

9、FFCEDT1BCAFEDF1BCAFEAT2BFDC？EBT3ADFC 图的操作 生成/消除一个图 加入一个顶点/边(弧) 遍历图 求生成树 .7.2 图的存储结构7.2.1 数组表示法数组表示法/ /邻接矩阵邻接矩阵 顶点数组顶点数组-用一维数组存储顶点(元素) 邻接矩阵邻接矩阵-用二维数组存储顶点(元素)之间的关系(边或弧) 143G2 1 2 3 41 0 0 1 12 0 0 0 03 1 0 0 14 1 0 1 0 M=例1邻接矩阵邻接矩阵 1 2 3 41 2 3 4顶点数组顶点数组V1.4例2ADCGB A B C DA 0 0 1 1B 0 0 0 0C 1 0 0 1D

10、1 0 1 0 M=邻接矩阵邻接矩阵 A B C D1 2 3 4顶点数组顶点数组V1.4顶点vi的 TDTD(vi)=M中第i行行元素之和 n = Mij j=1 顶点vi的 TDTD(vi)=M中第i列列元素之和 n = Mji j=1例3312 1 2 31 0 0 12 1 0 0 3 1 1 0M=邻接矩阵顶点vi的 IDID(vi)=M中第i列列元素之和 n = Mji j=1 顶点vi的 ODOD(vi)=M中第i行行元素之和 n = Mij j=1 例4132网G46545810714 1 2 3 4 5 61 4 5 2 4 8 3 5 8 10 74 5 10 146 7

11、14 思考题： 1.如何求每个顶点的度 D(vi)D(vi)? 1in 2.如何求每个顶点的出度 OD(vi)OD(vi)? 1in 3.如何求每个顶点的入度 ID(vi)ID(vi)? 1in M=邻接矩阵7.2.2 邻接表、逆邻接表邻接表、逆邻接表 - - 链式存储结构。 无向图的邻接表邻接表 - - 为图G的每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边。 若无向图G有n个顶点和e条边，则G的邻接表需n个表头结点和2e个表结点。 无向图G的邻接表，顶点vi的度为第i个单链表的长度。v4v5v6v3v1v2v1v2v3v4v5v64 1 2 3 4 5 62645561

12、图G图G邻接表序号 头结点头结点数组 表结点表结点单链表有向图的邻接表邻接表 -第i个单链表中的表结点，表示 以顶点vi为尾的弧(vi,vj)的弧头。 若有向图G有n个顶点和e条弧，则G的邻接表需n个表头结点 和e个表结点。 有向图G的邻接表，顶点vi的出度为第i个单链表的长度。CEFBAD A B C D E F 1 2 3 4 5 6462有向图G图G的邻接表邻接表262序号 头结点头结点数组 表结点表结点单链表5有向图的逆邻接逆邻接表表 -第i个单链表中的表结点，表示 以顶点vi为尾的弧(vi,vj)的弧头。 若有向图G有n个顶点e条弧，则G的逆邻接表需n个表头结点 和e个表结点。 有向

13、图G的逆邻接表，顶点vi的入度为第i个单链表的长度。CEFBAD A B C D E F 1 2 3 4 5 653序号 头结点数组 表结点单链表1有向图G图G的逆邻接表逆邻接表1343有向图的十字链表十字链表- 将邻接表和逆邻接表 合并而成的链接表。 CBADABCD 1 2 3 41 GG的逆邻接表逆邻接表134 ABCD 1 2 3 44 3 G的邻接表邻接表2 2ABCD1234G的十字链表十字链表3 21 24 2 14 4 3 24 4 1 1 4 7.2.4 邻接多重邻接多重表表-另一种链式存储结构EDFBACGABCDEF012023013024034056序号序号 data

14、data firstedgefirstedge(A,B)(A,C)(B,C)(B,D)(C,D)(E,F)隐含的链接表：隐含的链接表： A (1,2) (1,3) B (1,2) (2,3) (2,4) C (1,3) (2,3) (3,4) D (2,4) (3,4) E (5,6) F (5,6)ma vi ma vi vj vil vjlvj vil vjl123456 图的一条边或弧用一个“头结点头结点”表示，其中： markmark-标志域，可用以标记该条边是否被搜索过； vivi和和vjvj-该条边依附的两个顶点在图中的位置； vilinkvilink-指向下一条依附于顶点vi的边

15、； vjlinkvjlink-指向下一条依附于顶点vj的边。 0 1 2mark vi mark vi vj vilink vjlinkvj vilink vjlinkdata data firstedgefirstedgeA表示顶点A的头结点头结点表示边或弧(v1,v2)的表结点表结点 图的一个顶点用一个“头结点头结点”表示，其中： datadata域域存储和该顶点相关的信息， firstedgefirstedge域域存储第一条依附于该顶点的边。表结点表结点7.3 图的遍历- 从图G的某定点vi出发，访问 G的每个顶点且每个顶点仅被访问一次。7. .3.1 图的深度优先搜索深度优先搜索 DF

16、SDFS-Depth First Search 设图G的所有顶点未被某访问：（1）访问指定的起始顶点V,然后选取与V邻接的未被访问的顶点W,以W为起始顶点进行深度优先搜索，直到图中所有与V邻接的顶点都被访问到；（2）如图G中还有顶点未被访问，则另选一个未被访问的顶点为起始顶点，转（1）；否则结束。FDBCAGHE假定从 A A 出发遍历图G，深度优先搜索结果： A,B,C,D,E,G,F,HA,B,C,D,E,G,F,H宽度优先搜索结果： A,B,E,F,C,D,G,H A,B,E,F,C,D,G,HABCDEF112图G邻接表12345678GH2565764438177238 67. .3

17、.2 图的广广( (宽宽) )度优先搜索度优先搜索 BFSBFS- -Breadth First Search设图G的所有顶点未被某访问：（1)任选图G中未被访问的顶点V开始搜索,然后依次 访问V的各个未被访问的邻接Vj1,Vj2,Vjp；（2）分别从Vj1,Vj2,Vjp开始广(宽)度优先搜索；（3）如图G中还有顶点未被访问的顶点，则转（1）； 否则结束。7. .3.2 图的广广( (宽宽) )度优先搜索度优先搜索 BFSBFS- -Breadth First SearchFDBCAGHE假定从 A A 出发遍历图G： A,E,F,B,G,H,I,D,CA,E,F,B,G,H,I,D,C A

18、,B,F,E,D,C,I,H,GA,B,F,E,D,C,I,H,G A,F,E,G,H,I,B,D,C A,F,E,G,H,I,B,D,C ？ A,F,B,E,G,H,I,C,D A,F,B,E,G,H,I,C,D ？ A,E,B,F,I,H,G,D,C A,E,B,F,I,H,G,D,C ？假定从 G G 出发遍历G： G,F,E,H,A,I,B,C,DG,F,E,H,A,I,B,C,D G,H,F,E,I,A,B,C,D G,H,F,E,I,A,B,C,D G,E,F,H,I,A,B,C,D G,E,F,H,I,A,B,C,D ？I图G7.4 图的连通性问题7.4.1 DFS生成树假定从A

19、 A出发DFSDFS遍历图G：FDBCAGHEI图GABABABADCDFDBCAFDBCAIFDBCAIG7.4 图的连通性问题7.4.1 DFS生成树DFS生成树T1FDBCAGHEI图GFDBCAIGHFDBCAIGHEFDBCAIGHEDFS生成树T2ECBDAIGFH7.4.2 BFSBFS生成树生成树FDBCAGHEI图G假定从A A出发BFSBFS遍历图G：AABABFABEFABEFCABEFCDABEFCDI7.4.2 BFSBFS生成树生成树FDBCAGHEI图G假定从A A出发BFSBFS遍历图G：ABEFCDIHGABEFCDIHABEFCDIHGABEFCDIHGBF

20、S生成树T1BFS生成树T27.4.3 DFSDFS生成森林生成森林CKIJADEBFGH从A A出发，得树T1：T2CADEBF图GT3T1从G G出发,得树T2：CADEBFT1GHT2CADEBFT1GHKIJ从I I出发,得树T3：7.4.4 BFSBFS生成森林生成森林CKIJADEBFGH从A A出发，得树T1：T2图GT3T1从G G出发,得树T2：AT1GHT2T1GHKIJ从I I出发,得树T3：CDEBFACDEBFACDEBF7.4.5 网的最小生成树- 在网G的各生成树中，其中各边的权之和最小的生成树称为G的最小生成树最小生成树. . 普里姆普里姆( (prim)prim)算法 设N=(V,E)是连通网，TE是N上最小的生成树中边的集合。令U=u。(u。V),TE= ,重复以下操作： 在所有uV，v V-U的边(u,v) E中找一条代价最小的边(u。, v 。)并入集合TE, v 。并入U,直到 U=V为止。 例：求例：求G G的最小生成树的最小生成树 CADEBF图G3718745561.普里姆普里姆( (prim)prim)算法 以选顶点为主以选顶点为主DTCD5TCAD15CADB3156CADEB3156TTT图G的最小生成树 CADEBF图G3718745561.普里姆普里姆( (prim)prim)算法 以选顶点为主以