路径:1,2,3,5,6,3 例 路径长度:5 简单路径:1,2,3,5 回路:1,2,3,5,6,3,1 简单回路:3,5,6,3 GI 例 路径:1,2,5,7,6,5,2,3 路径长度:7 简单路径:1,2,5,7,6 回路:1,2,5,7,6,5,2, G2 简单回路:1,2,3
例 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
例 连通图 例 强连通图 非连通图 连通分量
连通图 例 2 4 5 1 3 6 强连通图 3 5 6 例 非连通图 连通分量 例 2 4 5 1 3 6
§62图的存储结构 ★多重链表 例①2 V2|^ GI 例① G2 V4
§6.2 图的存储结构 多重链表 例 G1 2 4 1 3 例 1 5 3 2 4 G2 V1 V4 ^ V2 ^ ^ V3 ^ ^ V1 V2 V4 ^ V5 ^ V3
★邻接矩阵—表示顶点间相联关系的矩阵 ☆定义:设G=(V,E)是有n≥1个顶点的图,G的邻接矩阵A是具有 人下性质的n阶方阵 4/≈J1,若(v,v,减或<v,v>∈FG) 0,其它 ①②③④ ①「01 例 ②0000 000 ④L1000 ①②③④⑤ 例 ①「01010 ②10101 ③01011 ④10100 G2 100
邻接矩阵——表示顶点间相联关系的矩阵 ❖定义：设G=(V,E)是有n1个顶点的图，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(n+1)/2 有向图邻接矩阵不一定对称:有η个顶点的有向图需存储空 间为n2 ●无向图中顶点的度1D()是邻接矩阵A中第行元素之和 ●有向图中, ◆顶点Ⅵ的出度是A中第行元素之和 ◆顶点Ⅵ的入度是A中第列元素之和 网络的邻接矩阵可定义为: 4n-0,若N,)成 <V ∈E(G) 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