第7章图 7.1图的基本概念 7.2图的表示与实现 7.3图的遍历 7.4最小生成树 7.5拓扑排序 7.6关键路径 7.7最短路径 2021/2/11 数据结构及其算法第7章图
第7章 图 •7.1 图的基本概念 •7.2 图的表示与实现 •7.3 图的遍历 •7.4 最小生成树 •7.5 拓扑排序 •7.6 关键路径 •7.7 最短路径 2021/2/11 数据结构及其算法 第7章 图 2
7.1图的基本概念 图( graph):任意两个数据元素之间可以存在关系 的数据结构 线性表:前驱、后继关系 树:双亲、孩子关系 图论( graph theory):数学和计算机科学中研究 图状结构的理论 〔柯尼斯堡七桥问题 图码 欧拉,1736年 的整还 2021/2/11 数据结构及其算法第7章图
7.1 图的基本概念 •图(graph)：任意两个数据元素之间可以存在关系 的数据结构 • 线性表：前驱、后继关系 • 树：双亲、孩子关系 •图论(graph theory)：数学和计算机科学中研究 图状结构的理论 2021/2/11 数据结构及其算法 第7章 图 3 柯尼斯堡七桥问题 欧拉，1736年
范甘迪 麦迪麦蒂尔斯通 叶莉 乌鲁木齐 哈尔滨 呼和浩特 668 图的实例 397 社交网络:微博、人人 674 交通网 计划路线图 1100 639贵 672|675 洗开水壶(1分钟 烧开水(15分钟) 洗荼壶(1分钟 洗荼杯(2分钟) 拿荼叶(1分钟 2021/2/11 数据结构及其算法第7章图
•图的实例 • 社交网络：微博、人人 • 交通网 • 计划路线图 2021/2/11 数据结构及其算法 第7章 图 4
·图的数学模型:G=(V,E) ⅴ:图中数据元素的集合,称顶点(ⅴ ertex)集 E:图中数据之间关系的集合,称边(edge)集 数据之间的关系可以是单向的,也可以是双向的 有向图( digraph):单向数据关系。此时边又称弧 (arc),从弧尾到弧头 无向图( undigraph):双向数据关系 边上可以附带数字,称为权( weight),带权的图 又称网( network) (a)有向图 (b)无向图 (b) 2021/2/11 数据结构及其算法第7章图
•图的数学模型：G=(V,E) • V：图中数据元素的集合，称顶点(vertex)集 • E：图中数据之间关系的集合，称边(edge)集 •数据之间的关系可以是单向的，也可以是双向的 • 有向图(digraph)：单向数据关系。此时边又称弧 (arc)，从弧尾到弧头 • 无向图(undigraph)：双向数据关系 •边上可以附带数字，称为权(weight)，带权的图 又称网(network) 2021/2/11 数据结构及其算法 第7章 图 5 (a) 有向图 (b) 无向图
图的基本操作 创建、销毁 遍历:深度优先、广度优先 对顶点的操作:增加、删除、访间、修改 对边的操作:增加、删除、访问、修改权 ADT Graph(课本PP.215~217) 2021/2/11 数据结构及其算法第7章图
•图的基本操作 •创建、销毁 •遍历：深度优先、广度优先 •对顶点的操作：增加、删除、访问、修改 •对边的操作：增加、删除、访问、修改权 •ADT Graph (课本PP.215~217) 2021/2/11 数据结构及其算法 第7章 图 6