트리의 첫 번째 탐색, 파이썬

Question

트리의 깊이 우선 탐색을 계산했습니다.

def _dfs(tree, res): 
    if tree: 
     res += [tree.key] 
     _dfs(tree.left, res) 
     _dfs(tree.right, res) 
    return res 

나는 퍼스트 퍼스트 서치에 대한 해결책을 찾지 못하는 것 같습니다. 대기열이나 스택을 사용해야합니까?

감사합니다.

Answer 1

예, 확인했지만 아직 재귀 적으로 처리하지 않은 노드를 보유하려면 대기열을 사용해야합니다.

큐에서 루트 노드로 시작한 다음 [노드를 하나씩 팝하고 각 하위 노드에 대해 필요한 동작 (예 : res += [tree.key])을 수행하고 큐에 밀어 넣기]를 반복합니다.

Answer 2

너와 함께 할 수있다. 이것은 Magnus Lie Hetland의 bfs (FIFO 대기열 사용)의 고전적인 구현입니다.

from collections import deque 

def bfs(G, s): 
    P, Q = {s: None}, deque([s]) 
    while Q: 
     u = Q.popleft() 
     for v in G[u]: 
      if v in P: continue 
      P[v] = u 
      Q.append(v) 
    return P