링크 된 데이터 구조에 대한 먼저 검색 알고리즘을 작성할 수 있습니까?

Question

대기열을 사용하고 모든 노드를 표시하여 BFS를 수행 할 수 있습니다. 그래프가 인접 행렬에 저장되어 있으면 노드가 얼마나 많은 지 쉽게 알 수 있고 마커 배열을 만들 수 있습니다.

TreeNode 정의가있는 경우 어떻게해야합니까? (예 : 정의주기, 나는 트리에있는 노드 수를 알 수 없습니다.)

# Definition for a binary tree node 
class TreeNode: 
    def __init__(self, x): 
     self.val = x 
     self.left = None 
     self.right = None 

Answer 1

는 당신이 필요로하는 모든 시작 위치와 모든 표시된 노드를 저장하는 세트와 함께 노드를 저장하는 큐입니다 :

from collections import deque 
class TreeNode: 
    def __init__(self, x): 
     self.val = x 
     self.left = None 
     self.right = None 
     self.children = [self.left, self.right] #for easier transversing 

root_node = TreeNode(1) 
... #node declarations follow below 
d = deque([root_node]) 
target = 5 
flag = False 
marked = {root_node.val} 
while d: 
    current_node = d.popleft() 
    marked.add(current_node.val) 
    d.extend([i for i in current_node.children if i and i.val not in marked]) 
    if current_node == target: 
     flag = True 
     break 

print('found' if flag else "not found") 

이 코드는 위의 폭 첫 번째 검색에 대한 일반적인 단계를 따릅니다

1. 추가 루트 큐에 노드와 마크를 방문한다.
2. 큐가 비어 함 아니지만 :
   1. 큐에서 첫 번째 요소를 팝업이 목표 값과 동일한 지 확인. 그렇다면 휴식하십시오. 그렇지 않으면 2로 이동하십시오.
   2. 표시되지 않은 첫 번째 요소의 모든 하위 노드 (큐가 1에서 팝 됨)로 큐를 확장하십시오.
   3. 첫 번째 요소를 가로로 표시하십시오.