基本概念 口连通图 a)弱连通 b)强连通 Data structure
Data Structure LXJ V5 V1 V3 V2 V4 V5 V1 V3 V2 V4 a）弱连通 b）强连通 基本概念 ❑ 连通图
基本概念 口完全图:任意两点间都有边相关联的图 无向完全图共有边(n(n-1)2条 2.有向完全图共有边n(n-1)条 Data structure
Data Structure LXJ 基本概念 ❑ 完全图：任意两点间都有边相关联的图 1. 无向完全图 共有边 (n*(n-1)) /2条 2. 有向完全图 共有边 n(n-1) 条
基本概念 子图: Q G=V, E, GEV, E) 口如果 W=: 口就称G是G的子图。 图 b)子图 Data structure
Data Structure LXJ 基本概念 子图： ❑ G=(V, E), G’=(V’, E’) ❑ 如果 V’ V, E’ E , ❑ 就称 G’是G的子图。 V5 V1 V3 V2 V4 V5 V1 V3 V2 a）图 b）子图
基本概念 口生成树 1.连通图的生成树:含有所有顶点的极小连通图子图,n个 顶点的连通图的生成树有n个定点,有n-1条边 2.非连通图的生成森林:所有k个连通分支的生成树组成生 成森林,共有n-k条边 /③ a)连通图和生成树 b)非连通图和生成森林图 Data structure
Data Structure LXJ 基本概念 ❑ 生成树 1. 连通图的生成树：含有所有顶点的极小连通图子图， n个 顶点的连通图的生成树有n个定点，有n-1条边 2. 非连通图的生成森林：所有k个连通分支的生成树组成生 成森林，共有 条边 V5 V1 V3 V2 V4 V5 V1 V3 V2 V4 V6 V5 V1 V3 V2 V4 V1 V3 V2 V4 V5 V6 a）连通图和生成树 b）非连通图和生成森林图 n-k
82图的邻接矩阵存储结构 1邻接矩阵 用矩阵表示图的顶点之间的相邻关系。 AU, =1 Vi,vIEE =0(vv)不存在 V10 00 V210011 2345 000 0 000 01 00 V=【v1V2V3V4V Data structure
Data Structure LXJ 8.2 图的邻接矩阵存储结构 1.邻接矩阵 用矩阵表示图的顶点之间的相邻关系。 A[i,j] =1 (vi,vj)E =0 (vi,vj)不存在 V5 V1 V2 V3 V4 V1 V2 V3 V4 V5 V1 0 1 1 0 0 V2 1 0 0 1 1 V3 1 0 0 0 1 V4 0 1 0 0 0 V5 0 1 1 0 0 A = V = {V1 V2 V3 V4 V5}