第8章 西南科技大学计算机学院 信息教研室 Data structure
Data Structure LXJ 第 8 章 图 西南科技大学 计算机学院 信息教研室
图 图应用最广泛的数据结构。 不同于树的另一种非线性结构 每个顶点可以与多个其他顶点相关联,各顶 点之间的关系是任意的。 简单图没有自身环,两点间至多一条边 a)简单图b)带自身环的图b)多重图 Data structure
Data Structure LXJ 图 图 应用最广泛的数据结构。 不同于树的另一种非线性结构 每个顶点可以与多个其他顶点相关联，各顶 点之间的关系是任意的。 简单图 没有自身环，两点间至多一条边 V5 V1 V2 V3 V4 V1 V2 V3 V4 a）简单图 b）多重图 V5 V1 V2 V3 V4 b）带自身环的图
81图的基本概念 口图( Graph是由顶点集合及顶点间的关系集合组成的一种数 据结构。即:G=V目 1.顶点集V=vV2y 2.边集E 无向图:E=【w,v)lvv∈v 有向图:E=v,v>Mv,v∈v有向边集 其中有向边,v起点弧尾,v终点弧头 a)无向图 b)有向图 Data structure
Data Structure LXJ 8.1 图的基本概念 ❑ 图(Graph)是由顶点集合及顶点间的关系集合组成的一种数 据结构。即：G=(V, E) 1. 顶点集V={v1,v2,······,vn} 2. 边集E • 无向图：E={ (vi, vj) | vi,vj∈V} • 有向图：E={|vi , vj∈V}有向边集 • 其中有向边 ， vi起点弧尾， vj终点弧头 V5 V1 V2 V3 V4 V1 V2 V3 V4 a）无向图 b）有向图
基本概念 度:TDv一个顶点的度,以v为端点的边的数目 oD(v):出度,以v为起点的边的数目 ID(v):入度,以v为终点的边的数目 TD(Vi= OD(Vi+ ID(vi OD=ID, TD=2e, e=1/2*TD TD OD ID为整个图的总度,出度,入度数。 Data structure
Data Structure LXJ 基本概念 度：TD(vi ): 一个顶点的度,以vi为端点的边的数目 OD(vi ): 出度, 以vi为起点的边的数目 ID(vi ): 入度，以vi为终点的边的数目 TD(vi )= OD(vi )+ ID(vi ) OD=ID, TD=2e， e =1/2*TD TD OD ID 为整个图的总度,出度,入度数。 V5 V1 V2 V3 V4 V1 V2 V3 V4
基本概念 权:图的边的附加信息,权可以表示实际问题中从一个问题到另 个问题距离、花费的代价、所需的时间 带权图(网络): 路径vvyp以v为起点v为终点的顶点序列 路径的长:路径上边的数目(不带权的图 路径上各个边权值的总和。(带权的图) 简单路径:顶点都不重复的路径 回路环:首尾相接的路径 wv连通:有路径vry 连通图:任意两点都连通 强连通:vr"v,v"vn 强连通图:任意两点都强连通 Data structure
Data Structure LXJ 基本概念 权：图的边的附加信息，权可以表示实际问题中从一个问题到另一 个问题距离、花费的代价、所需的时间 带权图（网络）： 路径 vi······vj , 以vi为起点vj为终点的顶点序列 路径的长： 路径上边的数目(不带权的图) 路径上各个边权值的总和。（带权的图） 简单路径：顶点都不重复的路径 回路环： 首尾相接的路径 vivj连通： 有路径 vi······vj 连通图： 任意两点都连通 强连通： vi······vj， vj······vi 强连通图：任意两点都强连通。 V5 V1 V2 V3 V4
基本概念 口连通图 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}