大连理工大学：《数据结构》课程教学课件（PPT讲稿）第六章 图

第六章图 §6.1图的定义和术语 图(Graph)一图G是由两个集合V(G)和E(G)组成的， 记为G=(V,E) 其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对或有序对 有向图— 有向图G是由两个集合V(G)和E(G)组成的 其中：V(G)是顶点的非空有限集 E(G)是有向边（也称孤）的有限集合，弧是顶点的有序 对，记为,V,W是顶点，V为弧尾，W为弧头 无向图一无向图G是由两个集合V(G)和E(G)组成的 其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对，记为(V,W) 或(w,V),并且(V,W=(W,)

第六章 图 §6.1 图的定义和术语 ❖图(Graph)——图G是由两个集合V(G)和E(G)组成的, 记为G=(V,E) 其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对或有序对 ❖有向图——有向图G是由两个集合V(G)和E(G)组成的 其中：V(G)是顶点的非空有限集 E(G)是有向边（也称弧）的有限集合，弧是顶点的有序 对，记为，v,w是顶点，v为弧尾，w为弧头 ❖无向图——无向图G是由两个集合V(G)和E(G)组成的 其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对，记为（v,w） 或（w,v)，并且（v,w)=(w,v)

例 G1 图G1中：V(G1)={1,2,3,4,5,6} E(G1)={,,,,,,} 例 6 G2 图G2中：V(G2)={1,2,3,4,5,6,7} E(G1)={(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)}

例 2 4 5 1 3 6 G1 图G1中：V(G1)={1,2,3,4,5,6} E(G1)={, , , , , , } 例 1 5 7 3 2 4 G2 6 图G2中：V(G2)={1,2,3,4,5,6,7} E(G1)={(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7)}

必有向完备图一n个顶点的有向图最大边数是n(n-) 无向完备图一n个顶点的无向图最大边数是n(n-1)/2 权一与图的边或弧相关的数叫~ 冬网一带权的图叫 子图一如果图G(V,日)和图G‘(V',E),满足： ●VsV ●E'cE 则称G为G的子图 ?顶点的度 ●无向图中，顶点的度为与每个顶点相连的边数 ●有向图中，顶点的度分成入度与出度 ◆入度：以该顶点为头的弧的数目 ◆出度：以该顶点为尾的弧的数目 路径—路径是顶点的序列V=Vio,Vi1,.Vn, 满足 （V-1,V∈E或∈E,（1

❖有向完备图——n个顶点的有向图最大边数是n(n-1) ❖无向完备图——n个顶点的无向图最大边数是n(n-1)/2 ❖权——与图的边或弧相关的数叫~ ❖网——带权的图叫~ ❖子图——如果图G(V,E)和图G‘(V’,E‘),满足： ⚫V’V ⚫E’E 则称G‘为G的子图 ❖顶点的度 ⚫无向图中，顶点的度为与每个顶点相连的边数 ⚫有向图中，顶点的度分成入度与出度 ◆入度：以该顶点为头的弧的数目 ◆出度：以该顶点为尾的弧的数目 ❖路径——路径是顶点的序列V={Vi0,Vi1,.Vin}，满足 (Vij-1,Vij)E 或 E,(1<jn)

路径长度一沿路径边的数目或沿路径各边权值之和 冬回路一第一个顶点和最后一个顶点相同的路径叫~ 冬简单路径—一—序列中顶点不重复出现的路径叫~ 冬简单回路—除了第一个顶点和最后一个顶点外，其 余顶点不重复出现的回路叫~ 连通一从顶点V到顶点W有一条路径，则说V和W是 连通的 连通图一 图中任意两个顶点都是连通的叫~ 必连通分量一一非连通图的每一个连通部分叫~ 强连通图一有向图中，如果对每一对V,VV,V≠V 从V到V和从V到V都存在路径，则称G是~

❖路径长度——沿路径边的数目或沿路径各边权值之和 ❖回路——第一个顶点和最后一个顶点相同的路径叫~ ❖简单路径——序列中顶点不重复出现的路径叫~ ❖简单回路——除了第一个顶点和最后一个顶点外，其 余顶点不重复出现的回路叫~ ❖连通——从顶点V到顶点W有一条路径，则说V和W是 连通的 ❖连通图——图中任意两个顶点都是连通的叫~ ❖连通分量——非连通图的每一个连通部分叫~ ❖强连通图——有向图中，如果对每一对Vi,VjV, ViVj, 从Vi到Vj 和从Vj到Vi都存在路径，则称G是~

例 3 有向完备图 无向完备图 例 3 6 3 6 图与子图 例 例 5 7 2 4 6 G1 G2 顶点2入度：1出度：3 顶点5的度：3 顶点4入度：1出度：0 顶点2的度：4

例 2 1 3 2 1 3 有向完备图 无向完备图 3 5 6 例 2 4 5 1 3 6 图与子图 例 2 4 5 1 3 6 G1 顶点2入度：1 出度：3 顶点4入度：1 出度：0 例 1 5 7 3 2 4 G2 6 顶点5的度：3 顶点2的度：4

路径：1,2,3,5,6,3 例 路径长度：5 简单路径：1,2,3,5 ▣路：1,2,3,5,6,3,1 3 6 简单回路：3,5,6,3 G1 例 5 7 路径：1,2,5,7,6,5,2,3 路径长度：7 简单路径：1,2,5,7,6 4 6 回路：1,2,5,7,6,5,2,1 G2 简单回路：1,2,3,1

例 1 5 7 3 2 4 G2 6 例 2 4 5 1 3 6 G1 路径：1，2，3，5，6，3 路径长度：5 简单路径：1，2，3，5 回路：1，2，3，5，6，3，1 简单回路：3，5，6，3 路径：1，2，5，7，6，5，2，3 路径长度：7 简单路径：1，2，5，7，6 回路：1，2，5，7，6，5，2，1 简单回路：1，2，3，1

例 4 5 连通图 3 6 例 5 强连通图 6 例 5 非连通图 连通分量 3 6

连通图 例 2 4 5 1 3 6 强连通图 3 5 6 例 非连通图 连通分量 例 2 4 5 1 3 6

§6.2图的存储结构 ★多重链表 例 V4☑ V2 3 4 V3 G1 例 2 G2 Vs

§6.2 图的存储结构 多重链表 例 G1 2 4 1 3 例 1 5 3 2 4 G2 V1 V4 ^ V2 ^ ^ V3 ^ ^ V1 V2 V4 ^ V5 ^ V3

★邻接矩阵一表示顶点间相联关系的矩阵 定义：设G=(N,E)是有≥1个顶点的图，G的邻接矩阵A是具有 以下性质的n阶方阵 1,若(N,V)减∈E(G) A,]= 0,其它 ①②③ ④ ①「0 11 0 例 2 ② 0 0 0 0 ③ 0 0 01 ④L1 00 0 GI ①②③④ ⑤ 例 2 ①「01 01 0 ②10 1 01 ③ 0 1 011 5 ④101 0 0 G2 ⑤011 0 0

邻接矩阵——表示顶点间相联关系的矩阵 ❖定义：设G=(V,E)是有n1个顶点的图，G的邻接矩阵A是具有 以下性质的n阶方阵       = 0，其它 1,若(v , v )或 v , v E(G) [ , ] i j i j A i j 例 G1 2 4 1 3 例 1 5 3 2 4 G2                   0 1 1 0 0 1 0 1 0 0 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0                         1 0 0 0 0 0 0 1 0 0 0 0  0 1 1 0       

冬特点： ●无向图的邻接矩阵对称，可压缩存储；有个顶点的无向图 需存储空间为n(n+1)/2 ●有向图邻接矩阵不一定对称；有个顶点的有向图需存储空 间为n2 ●无向图中顶点V的度TDV)是邻接矩阵A中第i行元素之和 ●有向图中， ◆顶点V的出度是A中第行元素之和 ◆顶点V的入度是A中第列元素之和 ●网络的邻接矩阵可定义为： 0,若(V,V)或∈E(G) A[i,刀= 0,其它

❖特点： ⚫无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图 需存储空间为n(n+1)/2 ⚫有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空 间为n² ⚫无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和 ⚫有向图中， ◆顶点Vi的出度是A中第i行元素之和 ◆顶点Vi的入度是A中第i列元素之和 ⚫网络的邻接矩阵可定义为：       = 0，其它 ,若(v , v )或 v , v E(G) [ , ] i j i j i j A i j 