数据结构与算法实习 数据结构设计技巧之二 北京大学信息科学技术学院 主讲:张铭、郝丹 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月
图+算法优化 图搜索和应用 算法优化:全1矩阵
图 + 算法优化 ◼图搜索和应用 ◼算法优化：全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的棋盘上有一个国王 和若干个骑士，他们要集 合到一点。 – 可能的移动如右图，允许 多个人位于同一格。 – 国王可以骑在骑士的马上 一起移动（亦可换马）。 – 计算总移动步数的最小值
拓扑排序 任意有向无环图都有拓扑序列 求拓扑排序的基本方法 反复删除入度为零的顶点 后序深度周游的逆序列
拓扑排序 ◼ 任意有向无环图都有拓扑序列 ◼ 求拓扑排序的基本方法 – 反复删除入度为零的顶点 – 后序深度周游的逆序列
拓扑排序 后序深度周游的逆序列 60 对该DAG进行后序DFs 记录DFS的结点访问向量 10 10 逆序该向量,即为拓扑排丿∞ 结果 DFS: V5V3,V2.V4,VO.V1
拓扑排序 ◼ 后序深度周游的逆序列 – 对该DAG进行后序DFS – 记录DFS的结点访问向量 – 逆序该向量，即为拓扑排序 结果 – DFS: V5,V3,V2,V4,V0,V1
针对有回路的拓扑排序 解决的方法: 将标志位设为三种情况:Unvs,vst和 pushed(表明已放入结果数组) 当遇到一个结点,从它所能邻接到的结点中 若有已被标志为s但不是 pushed的时, 表明出现了环,即打印“存在环”即可
针对有回路的拓扑排序 ◼ 解决的方法： – 将标志位设为三种情况：unvisit,visit和 pushed(表明已放入结果数组) – 当遇到一个结点，从它所能邻接到的结点中 若有已被标志为visit但不是pushed 的时， 表明出现了环，即打印“存在环”即可 A C B