深度优先搜索.ppt

《深度优先搜索.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、15.082和6.855J深度优先搜索初始化LIST取消在N中的所有结点的标记;标记结点s1245369781pred(1)=0next:=1order(next)=1LIST:={1}next1124536978112在LIST中选择结点iLIST在深度优先搜索中，i是LIST中的最后结点12453697811next1113如果结点i和一条可进入的弧关联…LIST选择一条可进入弧(i,j)12453697811next1211标记结点jpred(j):=i2Next:=Next+1order(j):=next把j添

2、加到LIST224选择在LIST上的最后的结点LIST12453697811next121122212结点2被选择53如果结点i和一条可进入的弧关联…LIST12453697811next121122212选择一条可进入弧(i,j)标记结点jpred(j):=iNext:=Next+1order(j):=next把j添加到LIST43463选择LIST12453697811next121122212选择在LIST上的最后结点4342473如果结点i和一条可进入的弧关联…LIST12453697811next1211222

3、1243424选择一条可进入弧(i,j)标记结点jpred(j):=iNext:=Next+1order(j):=next把j添加到LIST844883选择LIST12453697811next12112221234248448选择在LIST上的最后的结点4893如果结点i不和可进入的弧关联…LIST12453697811next1211222123424844848从LIST中删除i8103选择LIST12453697811next1211222123424844848选择在LIST上的最后的结点841153如果结点i

4、和一条可进入的弧关联…LIST12453697811next121122212342484484884选择一条可进入弧(i,j)标记结点jpred(j):=iNext:=Next+1order(j):=next把j添加到LIST5551253选择LIST12453697811next121122212342484484884555选择在LIST上的最后的结点451353如果结点i和一条可进入的弧关联…LIST12453697811next12112221234248448488455545选择一条可进入弧(i,j)标记结

5、点jpred(j):=iNext:=Next+1order(j):=next把j添加到LIST66661453选择在LIST上的最后的结点LIST12453697811next12112221234248448488455545选择结点666665615753如果结点i和一条可进入的弧关联…LIST12453697811next12112221234248448488455545666656选择一条可进入弧(i,j)标记结点jpred(j):=iNext:=Next+1order(j):=next把j添加到LIST97

6、916753选择在LIST上的最后的结点LIST12453697811next12112221234248448488455545666656选择结点997969178753如果结点i和一条可进入的弧关联…LIST12453697811next1211222123424844848845554566665697969选择一条可进入弧(i,j)标记结点jpred(j):=iNext:=Next+1order(j):=next把j添加到LIST787188753选择在LIST上的最后的结点LIST12453697811nex

7、t1211222123424844848845554566665697969选择结点778797198753如果结点i不和可进入的弧关联…LIST12453697811next1211222123424844848845554566665697969从LIST中删除结点7787977208753选择结点9LIST12453697811next1211222123424844848845554566665697969但是结点9不和可进入的弧关联7879779从LIST中删除结点99218753选择结点6LIST1245369

8、7811next1211222123424844848845554566665697969但是结点6不和一条可进入弧关联7879779从LIST中删除结点6966228753选择结点5LIST12453697811next1211222123424844848845554566665697969但是结点