너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다. OPEN List는 큐를 사용해야만 레벨 순서대로 접근이 가능하다.
defbreadth_first_search(problem):# a FIFO open_setopen_set=Queue()# an empty set to maintain visited nodesclosed_set=set()# a dictionary to maintain meta information (used for path formation)meta=dict()# key -> (parent state, action to reach child)# initializestart=problem.get_start_state()meta[start]=(None,None)open_set.enqueue(start)whilenotopen_set.is_empty():parent_state=open_set.dequeue()ifproblem.is_goal(parent_state):returnconstruct_path(parent_state,meta)for(child_state,action)inproblem.get_successors(parent_state):ifchild_stateinclosed_set:continueifchild_statenotinopen_set:meta[child_state]=(parent_state,action)open_set.enqueue(child_state)closed_set.add(parent_state)defconstruct_path(state,meta):action_list=list()whileTrue:row=meta[state]iflen(row)==2:state=row[0]action=row[1]action_list.append(action)else:breakreturnaction_list.reverse()