第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>,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>|vi , vj∈V}有向边集 • 其中有向边 <vi, vj> ， 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