数据结构与算法实习 数据结构设计技巧之二 北京大学信息科学技术学院 主讲:张铭、郝丹 zhang [at]net. pku. edu. cn http://www.ipk.pkuedu.cn/pkujpk/course/siig/shixil 2011.8 张箱海橙家腾整類划衫耨绫控与赛掌
数据结构与算法实习 ——数据结构设计技巧之二 北京大学信息科学技术学院 主讲:张 铭、郝 丹 mzhang [at] net.pku.edu.cn http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/shixi/ 2011.8 张铭 赵海燕 王腾蛟 宋国杰,《数据结构与算法实验 教程》(国家十一五规划教材),高教社2011年1月
图周游 1234567 ############################# 1# # # # POJ 1164 #####一一-#####一--#一--#####一--# 2## 迷官中一共有多少个“非 ##### #####一一一#####一一-#####一一-# 房间?最大的房间有3###### 多大? #一—-######### ##### #一一-# 4## ## 求无向图的连通分支 ############################# (Figure 1) ■染色法(F|oodf|) 每次从未染过的点出发做DFS,将所有经过的点染 成同一颜色。重复上述过程直到所有点都被染色 DFS和BFS皆可
图周游 ◼ POJ 1164 – 迷宫中一共有多少个 房间?最大的房间有 多大? – 求无向图的连通分支 ◼ 染色法(Floodfill) – 每次从未染过的点出发做DFS,将所有经过的点染 成同一颜色。重复上述过程直到所有点都被染色 – DFS和BFS皆可
图应用1 POJ1376 直径为16的圆形机器人如何 能避过障碍,以最短的时间从 起点到达终点? 移动1格或左转90度或右转90 度都需要一个单位时间 给出起点和终点坐标和初始方 向,求最短时间 问题的本质是? 可达点最短路径
图应用1 ◼ POJ 1376 – 直径为1.6的圆形机器人如何 能避过障碍,以最短的时间从 起点到达终点? – 移动1格或左转90度或右转90 度都需要一个单位时间。 – 给出起点和终点坐标和初始方 向,求最短时间 – 问题的本质是? – 可达点最短路径
图应用2 ■贪吃蛇PoJ1324 不能咬到尾巴撞到墙 (1,1) (1,1) Ba B B2 B Figure 2 Sample Input Figure 3 After ore ste p from figure 2
图应用2 ◼ 贪吃蛇 POJ 1324 – 不能咬到尾巴撞到墙
图应用3 Finding Nemo 由门和墙组成的迷宫 从原点出发找Nemo 最少经过多少门? POJ 2049 Nemo Marla
图应用3 ◼ Finding Nemo – 由门和墙组成的迷宫 – 从原点出发找Nemo – 最少经过多少门? – POJ 2049
图应用4 PoJ1178象棋 -8×8的棋盘上有一个国王 和若干个骑士,他们要集 合到一点 紫装 可能的移动如右图,允许 possible movements of the king 多个人位于同一格。 国王可以骑在骑士的马上 起移动(亦可换马)。 计算总移动步数的最小值。 All possible movements of a knight
图应用4 ◼ POJ 1178 象棋 – 8×8的棋盘上有一个国王 和若干个骑士,他们要集 合到一点。 – 可能的移动如右图,允许 多个人位于同一格。 – 国王可以骑在骑士的马上 一起移动(亦可换马)。 – 计算总移动步数的最小值
拓扑排序 任意有向无环图都有拓扑序列 求拓扑排序的基本方法 反复删除入度为零的顶点 后序深度周游的逆序列
拓扑排序 ◼ 任意有向无环图都有拓扑序列 ◼ 求拓扑排序的基本方法 – 反复删除入度为零的顶点 – 后序深度周游的逆序列