深度优先搜索

null15.082 和 6.855J15.082 和 6.855J 深度优先搜索 初始化 初始化 LIST取消在N中的所有结点的标记; 标记结点 spred(1) = 0 next := 1 order(next) = 1 LIST:= {1}11在LIST中选择结点i在LIST中选择结点i LIST在深度优先搜索中， i 是LIST中的最后结点1111如果结点 i 和一条可进入的弧关联… 如果结点 i 和一条可进入的弧关联… LIST选择一条可进入弧 (i,j)12453697811 next1211标记结点 j pred(j) := i 2Next := Next + 1 order(j) := next 把 j 添加到 LIST22选择在LIST上的最后的结点选择在LIST上的最后的结点 LIST12453697811 next121122212结点 2 被选择如果结点 i 和一条可进入的弧关联…3如果结点 i 和一条可进入的弧关联… LIST12453697811 next121122212选择一条可进入弧 (i,j)标记结点 j pred(j) := i Next := Next + 1 order(j) := next 把 j 添加到 LIST434选择 3选择 LIST12453697811 next121122212选择在LIST上的最后结点43424如果结点 i 和一条可进入的弧关联…3如果结点 i 和一条可进入的弧关联… LIST12453697811 next12112221243424选择一条可进入弧 (i,j)标记结点 j pred(j) := i Next := Next + 1 order(j) := next 把 j 添加到 LIST8448选择3选择 LIST12453697811 next12112221234248448选择在LIST上的最后的结点48如果结点 i 不和可进入的弧关联…3如果结点 i 不和可进入的弧关联… LIST12453697811 next1211222123424844848从LIST中删除i8选择3选择 LIST12453697811 next1211222123424844848选择在LIST上的最后的结点84如果结点 i 和一条可进入的弧关联…53如果结点 i 和一条可进入的弧关联… LIST12453697811 next121122212342484484884选择一条可进入弧 (i,j)标记结点 j pred(j) := i Next := Next + 1 order(j) := next 把 j 添加到 LIST555选择53选择 LIST12453697811 next121122212342484484884555选择在LIST上的最后的结点45如果结点 i 和一条可进入的弧关联…53如果结点 i 和一条可进入的弧关联… LIST12453697811 next12112221234248448488455545选择一条可进入弧 (i,j)标记结点 j pred(j) := i Next := Next + 1 order(j) := next 把 j 添加到 LIST6666选择在LIST上的最后的结点53选择在LIST上的最后的结点 LIST12453697811 next12112221234248448488455545选择结点6666656如果结点 i 和一条可进入的弧关联…753如果结点 i 和一条可进入的弧关联… LIST12453697811 next12112221234248448488455545666656选择一条可进入弧 (i,j)标记结点 j pred(j) := i Next := Next + 1 order(j) := next 把 j 添加到 LIST979选择在LIST上的最后的结点753选择在LIST上的最后的结点 LIST12453697811 next12112221234248448488455545666656选择结点 997969如果结点 i 和一条可进入的弧关联…8753如果结点 i 和一条可进入的弧关联… LIST12453697811 next1211222123424844848845554566665697969选择一条可进入弧 (i,j)标记结点 j pred(j) := i Next := Next + 1 order(j) := next 把 j 添加到 LIST787选择在LIST上的最后的结点8753选择在LIST上的最后的结点 LIST12453697811 next1211222123424844848845554566665697969选择结点 778797如果结点 i 不和可进入的弧关联…8753如果结点 i 不和可进入的弧关联… LIST12453697811 next1211222123424844848845554566665697969从LIST中删除结点 7787977选择结点 98753选择结点 9 LIST12453697811 next1211222123424844848845554566665697969但是结点 9 不和可进入的弧关联7879779从LIST中删除结点 9 9选择结点 68753选择结点 6 LIST12453697811 next1211222123424844848845554566665697969但是结点 6 不和一条可进入弧关联7879779从LIST中删除结点 6 966选择结点 58753选择结点 5 LIST12453697811 next1211222123424844848845554566665697969但是结点 5 不和可进入弧关联。7879779从LIST中删除结点5 96655选择结点 48753选择结点 4 LIST12453697811 next1211222123424844848845554566665697969但是结点 4 不和一条可进入弧关联.7879779从LIST删除结点 4 9665544选择结点 28753选择结点 2 LIST12453697811 next1211222123424844848845554566665697969但是结点2 不不和可进入弧相邻.7879779从LIST中删除结点 2 966554422选择结点 198753选择结点 1 LIST12453697811 next121122212342484484884555456666569796978797799665544221选择一条可进入弧 (i,j)标记结点 j pred(j) := i Next := Next + 1 order(j) := next把j 添加到 LIST中393选择结点398753选择结点3 LIST12453697811 next121122212342484484884555456666569796978797799665544221但是结点3 不和可进入的弧关联.39313从LIST中删除结点 3 3选择结点 198753选择结点 1 LIST12453697811 next121122212342484484884555456666569796978797799665544221但是结点1 不和可进入的弧关联.39313从LIST中删除结点1 311LIST空了98753LIST空了 LIST12453697811 next121122212342484484884555456666569796978797799665544221算法结束！39313311深度优先搜索树深度优先搜索树注意每个推导出的子树有连续标号的结点。