图应用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