《图论动画深度优先搜索》由会员分享，可在线阅读，更多相关《图论动画深度优先搜索（29页珍藏版）》请在金锄头文库上搜索。
1、15.082 和和 6.855J深度优先搜索深度优先搜索初始化初始化 LIST取消在取消在N中的中的所有结点的标所有结点的标记记;标记结点标记结点 s1245369781pred(1) = 0next := 1order(next) = 1LIST:= 1 next1124536978112在在LIST中选择结点中选择结点i LIST在深度优先搜在深度优先搜索中，索中， i 是是LIST中的最后中的最后结点结点12453697811 next1113如果结点如果结点 i 和一条可进入的弧关联和一条可进入的弧关联 LIST选择一条可进选择一条可进入弧入弧 (i,j)12453697811 nex
2、t1 211标记结点标记结点 jpred(j) := i2Next := Next + 1order(j) := next把把 j 添加到添加到 LIST224选择在选择在LIST上的最后的结点上的最后的结点 LIST12453697811 next1 21122212结点结点 2 被选被选择择53如果结点如果结点 i 和一条可进入的弧关联和一条可进入的弧关联 LIST12453697811 next1 21122212选择一条可进选择一条可进入弧入弧 (i,j)标记结点标记结点 jpred(j) := iNext := Next + 1order(j) := next把把 j 添加到添加到
3、LIST43463选择选择 LIST12453697811 next1 21122212选择在选择在LIST上上的最后结点的最后结点4342473如果结点如果结点 i 和一条可进入的弧关联和一条可进入的弧关联 LIST12453697811 next1 2112221243424选择一条可进选择一条可进入弧入弧 (i,j)标记结点标记结点 jpred(j) := iNext := Next + 1order(j) := next把把 j 添加到添加到 LIST844883选择选择 LIST12453697811 next1 2112221234248448选择在选择在LIST上上的最后的结点的
4、最后的结点4893如果结点如果结点 i 不和可进入的弧关联不和可进入的弧关联 LIST12453697811 next1 211222123424844848从从LIST中删除中删除i8103选择选择 LIST12453697811 next1 211222123424844848选择在选择在LIST上上的最后的结点的最后的结点841153如果结点如果结点 i 和一条可进入的弧关联和一条可进入的弧关联 LIST12453697811 next1 211222123424844848 84选择一条可进选择一条可进入弧入弧 (i,j)标记结点标记结点 jpred(j) := iNext := Ne
5、xt + 1order(j) := next把把 j 添加到添加到 LIST5551253选择选择 LIST12453697811 next1 211222123424844848 84555选择在选择在LIST上上的最后的结点的最后的结点451353如果结点如果结点 i 和一条可进入的弧关联和一条可进入的弧关联 LIST12453697811 next1 211222123424844848 8455545选择一条可进选择一条可进入弧入弧 (i,j)标记结点标记结点 jpred(j) := iNext := Next + 1order(j) := next把把 j 添加到添加到 LIST66
6、661453选择在选择在LIST上的最后的结点上的最后的结点 LIST12453697811 next1 211222123424844848 8455545选择结点选择结点666665615753如果结点如果结点 i 和一条可进入的弧关联和一条可进入的弧关联 LIST12453697811 next1 211222123424844848 8455545666656选择一条可进选择一条可进入弧入弧 (i,j)标记结点标记结点 jpred(j) := iNext := Next + 1order(j) := next把把 j 添加到添加到 LIST97916753选择在选择在LIST上的最后的
7、结点上的最后的结点 LIST12453697811 next1 211222123424844848 8455545666656选择结点选择结点 997969178753如果结点如果结点 i 和一条可进入的弧关联和一条可进入的弧关联 LIST12453697811 next1 211222123424844848 845554566665697969选择一条可进选择一条可进入弧入弧 (i,j)标记结点标记结点 jpred(j) := iNext := Next + 1order(j) := next把把 j 添加到添加到 LIST787188753选择在选择在LIST上的最后的结点上的最后的结
8、点 LIST12453697811 next1 211222123424844848 845554566665697969选择结点选择结点 778797198753如果结点如果结点 i 不和可进入的弧关联不和可进入的弧关联 LIST12453697811 next1 211222123424844848 845554566665697969从从LIST中删除中删除结点结点 778797 7208753选择结点选择结点 9 LIST12453697811 next1 211222123424844848 845554566665697969但是结点但是结点 9 不不和可进入的弧和可进入的弧关联关
9、联78797 79从从LIST中删除中删除结点结点 99218753选择结点选择结点 6 LIST12453697811 next1 211222123424844848 845554566665697969但是结点但是结点 6 不不和一条可进入和一条可进入弧关联弧关联78797 79从从LIST中删除中删除结点结点 696 6228753选择结点选择结点 5 LIST12453697811 next1 211222123424844848 845554566665697969但是结点但是结点 5 不不和可进入弧关和可进入弧关联。联。78797 79从从LIST中删除中删除结点结点596 65
10、 5238753选择结点选择结点 4 LIST12453697811 next1 211222123424844848 845554566665697969但是结点但是结点 4 不不和一条可进入和一条可进入弧关联弧关联.78797 79从从LIST删除结删除结点点 496 65 54 4248753选择结点选择结点 2 LIST12453697811 next1 211222123424844848 845554566665697969但是结点但是结点2 不不不和可进入弧不和可进入弧相邻相邻.78797 79从从LIST中删除中删除结点结点 296 65 54 42 22598753选择结点选
11、择结点 1 LIST12453697811 next1 211222123424844848 84555456666569796978797 79 96 65 54 42 21选择一条可进选择一条可进入弧入弧 (i,j)标记结点标记结点 jpred(j) := iNext := Next + 1order(j) := next把把j 添加到添加到 LIST中中3932698753选择结点选择结点3 LIST12453697811 next1 211222123424844848 84555456666569796978797 79 96 65 54 42 21但是结点但是结点3 不不和可进入的弧和可进入的弧关联关联.39313从从LIST中删除中删除结点结点 332798753LIST空了空了 LIST12453697811 next1 211222123424844848 84555456666569796978797 79 96 65 54 42 21算法结束！算法结束！39313 31 128132987548679654231深度优先搜索树深度优先搜索树注意每个推导出注意每个推导出的子树有连续标的子树有连续标号的结点。号的结点。29
