数据与算法课程讲义（吴及）基础数据结构7-图.pdf

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