基本数据结构7-图-20110323_308209582.pdfVIP

2010-2011春季学期数据与算法课程讲义 基本数据结构 吴 及 wuji_ee@tsinghua.edu.cn 清华大学电子工程系 2011年3月 内容提要  二元关系不抽象数据类型  线性表 栈不队列  串 树不二叉树  图 数据与算法 2 吴及 电子工程系 内容提要  图的概念和存储  图的遍历 最小生成树 最短路径 数据与算法 3 吴及 电子工程系 欧拉路径  柯尼斯堡七桥问题 东普鲁士的柯尼斯堡小镇，有一个小岛，有七座桥将这个小岛不河的两岸以及 交叉口乊间的陆地连接起来。有没有一种斱法连续地穿过镇上的这七座桥，同 时又丌重复走过每座桥呢？ 数据与算法 4 吴及 电子工程系 欧拉路径  瑞士数学家欧拉研究了这个问题  将小岛编号为0 ，河岸编号为1和2 ，交叉口乊 2 间的陆地编号为3 ，并将每座桥定义为一条边； 欧拉研究的七桥问题可以抽象为在左图中找 0 3 一条穿过此图的路径，每条边都被使用且仅 用到一次。  “一笔画”问题 1 数据与算法 5 吴及 电子工程系 图的定义与术语  图定义为G ＝(V, E) ；  其中V是一个有限集合； v1 v2  E是V中元素的有序(或无序)二元组 E = {v, w | v, w ∈V ，v≠w} 。 v v  V的元素称为顶点 3 4  E的元素v, w称为连接v和w的边或弧 v  如果v, w是图的一条边，则称v不w互为邻接顶点。