广度优先搜索

15.082和6.855J广度优先搜索初始化

LIST取消在N中结点的所有标记;标记结点s1245369781pred(1)=0next:=1

order(next)=1LIST:={1}

next1124536978112在LIST中选择结点i

LIST在广度优先搜索中，i是在LIST中的第一个结点12453697811

next1113如果结点i和一条可进入弧关联…

LIST选择一条可进入弧(i,j)12453697811

next1211标记结点jpred(j):=i2Next:=

Next+1order(j):=next把j添加到LIST224如果结点i和一条可进入的弧关联…

LIST选择一条可进入弧(i,j)124536978311

next2311标记结点jpred(j):=i2Next:=

Next+1order(j):=next把j添加到LIST225554如果结点i和一条可进入的弧关联…

LIST选择一条可进入弧(i,j)124536978311

next2311标记结点jpred(j):=i2Next:=

Next+1order(j):=next把j添加到LIST225534364如果结点i和一条可进入的弧关联…

LIST从LIST删除结点i124536978311

next231122255343174选择结点i

LIST在LIST上的第一个结点变成了结点i124536978311

next23112225534312854如果结点i和一条可进入的弧关联…

LIST124536978311

next231222553432选择一条可进入弧arc(i,j)标记结点jpred(j):=iNext:=

Next+1order(j):=next把j添加到LIST454954如果结点i和一条可进入的弧关联…

LIST124536978311

next231222553432从LIST删除结点i45421054选择一个结点

LIST124536978311

next231222553432454在LIST上的第一个结点变成了结点i511654如果结点i和一条可进入的弧关联…

LIST124536978311

next2312225534324545选择一条可进入弧(i,j)标记结点jpred(j):=iNext:=

Next+1order(j):=next把j添加到LIST66612654如果结点i和一条可进入的弧关联…

LIST124536978311

next2312225534324545666从LIST中删除结点i513654选择结点3

LIST124536978311

next2312225534324545666结点3不和任何可进入弧关联53从LIST中删除结点i314654选择一个结点

LIST124536978311

next23122255343454666i:=44157654如果结点i和一条可进入的弧关联…

LIST124536978311

next231222553434546664选择一条可进入弧(i,j)标记结点jpred(j):=iNext:=

Next+1order(j):=next把j添加到LIST878167654如果结点i和一条可进入的弧关联…

LIST124536978311

next231222553434546664从LIST删除结点i8784177654选择结点i

LIST124536978311

next23122255343454666i:=687861887654如果结点i和一条可进入的弧关联…

LIST124536978311

next231222553434546668786选择一条可进入弧(i,j)标记结点jpred(j):=iNext:=

Next+1order(j):=next添加j到LIST中78719987654如果结点i和一条可进入的弧关联…

LIST124536978311

next231222553434546668786选择一条可进入弧(i,j)标记结点jpred(j):=iNext:=

Next+1order(j):=next添加j到LIST中78799920987654如果结点i和一条可进入的弧关联…

LIST124536978311

next231222553434546668786从LIST删除结点i787996921987654选择结点8

LIST124536978311

next231222553434546668786结点8不和任何可进入弧关联；从LIST中删除它787996