幅優先によるPythonリストの検索

Question

私は、あるノードから別のノードへの最適なパスを見つけるアルゴリズムをコーディングしようとしています。幅優先検索でfです。私は、次のコードを発見し、私はほとんどそれをすべて理解し、私は彼らがこのラインで何をしている得ることはありません：

while frontier: ... 

私の質問は、グラフ上の意味は何フロンティア

• ですか？
• 条件が満たされている間にどれくらい時間がかかりますか？

ここでは、コードです：Pythonで

Graph_Adjs={'s':['a','x'],'a':['s','z'],'x':['s','d','c'],'z':['a'],'d':['x','c','f'], 'c':['d','x','f','v'],'f':['d','c','v'],'v':['f','c'] } 

def BFS (Graph_Adjs,s='s'): 
    level = {'s':0} 
    father = {'s':None} 
    i = 1 
    frontier = [s] 

    while frontier: 
     next = [] 
     for u in frontier: 
      for v in Graph_Adjs[u]: 
       if v not in level: 
        level[v] = i 
        father[v] = u 
        next.append(v) 
     frontier = next 
     i+=1 
return father 

if __name__=='__main__': 
    father = BFS (Graph_Adjs,s='s') 
    f = 'f' 
    path = [] 
    while f !=None: 
     path.append(f) 
     f = father[f] 
    path.reverse() 
    print (path) 

Answer 1

、それはそれ以外の場合は非空ではFalseだ場合、リストの真理値がTrueであるが。この条件は、訪問先ノードを記録する方法を効果的に実装しているため、繰り返し繰り返されることはありません。