《图论动画广度优先搜索》由会员分享，可在线阅读，更多相关《图论动画广度优先搜索（24页珍藏版）》请在金锄头文库上搜索。
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
2、next1 211标记结点标记结点 jpred(j) := i2Next := Next + 1order(j) := next把把 j添加到添加到 LIST224如果结点如果结点 i 和一条可进入的弧关联和一条可进入的弧关联 LIST选择一条可进选择一条可进入弧入弧 (i,j)124536978311 next2 311标记结点标记结点 jpred(j) := i2Next := Next + 1order(j) := next把把 j 添加到添加到 LIST225554如果结点如果结点 i 和一条可进入的弧关联和一条可进入的弧关联 LIST选择一条可进选择一条可进入弧入弧 (i,j)124
3、536978311 next2 311标记结点标记结点 jpred(j) := i2Next := Next + 1order(j) := next把把 j 添加到添加到LIST225534364如果结点如果结点 i 和一条可进入的弧关联和一条可进入的弧关联 LIST从从LIST删除结删除结点点i124536978311 next2 31122255343174选择结点选择结点 i LIST在在LIST上的第上的第一个结点变成一个结点变成了结点了结点 i124536978311 next2 3112225534312854如果结点如果结点 i 和一条可进入的弧关联和一条可进入的弧关联 LIST
4、124536978311 next2 31222553432选择一条可进选择一条可进入弧入弧arc (i,j)标记结点标记结点 jpred(j) := iNext := Next + 1order(j) := next把把 j添加到添加到 LIST454954如果结点如果结点 i 和一条可进入的弧关联和一条可进入的弧关联 LIST124536978311 next2 31222553432从从LIST删除结删除结点点 i45421054选择一个结点选择一个结点 LIST124536978311 next2 31222553432454在在LIST上的第上的第一个结点变成一个结点变成了结点了结点
5、 i511654如果结点如果结点 i 和一条可进入的弧关联和一条可进入的弧关联 LIST124536978311 next2 312225534324545选择一条可进选择一条可进入弧入弧 (i,j)标记结点标记结点 jpred(j) := iNext := Next + 1order(j) := next把把 j 添加到添加到 LIST66612654如果结点如果结点 i 和一条可进入的弧关联和一条可进入的弧关联 LIST124536978311 next2 312225534324545666从从LIST 中删除中删除结点结点i513654选择结点选择结点 3 LIST1245369783
6、11 next2 312225534324545666结点结点3不和任何不和任何可进入弧关联可进入弧关联53从从LIST中删除中删除结点结点i314654选择一个结点选择一个结点 LIST124536978311 next2 3122255343454666i : = 44157654如果结点如果结点 i 和一条可进入的弧关联和一条可进入的弧关联 LIST124536978311 next2 31222553434546664选择一条可进选择一条可进入弧入弧 (i,j)标记结点标记结点 jpred(j) := iNext := Next + 1order(j) := next把把 j 添加到添
7、加到 LIST878167654如果结点如果结点 i 和一条可进入的弧关联和一条可进入的弧关联 LIST124536978311 next2 31222553434546664从从LIST删除结删除结点点i8784177654选择结点选择结点 i LIST124536978311 next2 3122255343454666i := 687861887654如果结点如果结点 i 和一条可进入的弧关联和一条可进入的弧关联 LIST124536978311 next2 31222553434546668786选择一条可进选择一条可进入弧入弧 (i,j)标记结点标记结点 jpred(j) := iN
8、ext := Next + 1order(j) := next添加添加j 到到LIST中中78719987654如果结点如果结点 i 和一条可进入的弧关联和一条可进入的弧关联 LIST124536978311 next2 31222553434546668786选择一条可进选择一条可进入弧入弧 (i,j)标记结点标记结点 jpred(j) := iNext := Next + 1order(j) := next添加添加j 到到LIST中中78799920987654如果结点如果结点 i 和一条可进入的弧关联和一条可进入的弧关联 LIST124536978311 next2 31222553434546668786从从LIST删除结删除结点点i787996921987654选择结点选择结点 8 LIST124536978311 next2 31222553434546668786结点结点 8 不和任不和任何可进入弧关何可进入弧关联；从联；从LIST中中删除它删除它78799698 822987654选择结点选择结点 9 LIST124536978311 next2 31222553434546668786结点结点 9 不和可不和可进入弧关联；进入弧关联；从从LIST中删除中删除它它78799699 923结束结束24
