数据结构-7 图.pdf

井冈山大学计算机科学系 冷明 井冈山大学计算机科学系 冷明 lengming@jgsu.edu.cn lengming@jgsu.edu.cn 课前思考： 前2-6章我们讲了哪些数据结构? 非线性结构 线性 栈 队列 串 数组 树 表 二叉树 n个元 仅在表尾 一端插入 零个或者 线性表中 素的有 进行插入 另一端删 多个字符 的元素本 分支关系 和删除的 除的线性 组成的序 身也是一 定义的层 限序列 线性表 表 列 种结构 次结构 结点间具有唯一前驱、唯一后继关系 一对多 结点之间是一对一的关系 的关系 非线性结构(树)来描述该家族谱系关系 爷爷 大伯 叔叔 父亲 堂兄 堂姐 哥哥 自己 妹妹 数据元素之间有着明显的层次关系 每一层的数据元素可能和下一层中多个元素相关：每个父亲可以有多个子女 每一层的数据元素只能和上一层中一个元素相关：每个人只有一个父亲 非线性结构(树)来描述该电路？ 非线性结构-图 数据元素之间没有层次关系 数据元素之间的关系可以是任意的：任意两个数据元素之间都可能相关 7.1 图的基本概念 图的定义 图(graph)是由一个非空的顶点集合和一个描述顶点 之间多对多关系的边集合组成的非线性数据结构 G=(V,E) 图G的顶点集合和边集合分别记为V(G)和E(G) V(G)={v|v∈某个数据对象集}:它是顶点的有穷非空集合 E(G)={v,w|v,w∈V且P(v,w)}:它是顶点之间关系的有穷集合，也叫 边集合，其中P(v,w)表示从v到w的一条单向通路 7.1图的定义和术语 7.1图的定义和术语 图的应用举例 例2 电路 顶点:元件 例1 交通图（公路、铁路） 边:连接元件之间的线路 顶点:地点 边:连接地点的公路 例3 通讯线路图 交通图中单行道双行道， 顶点:地点 用有向边、无向边表示 边:地点间的连线 V0 V1 V0 V1 例4 产品的生产流程图 V2 顶点:工序 V3 V4 V2 V3 边:各道工序之间的顺序关系 7.1图的定义和术语 7.1图的定义和术语 有向图 若图G中的每条边都是有方向的，则称G为有向图 在有向图中