<jupyter_start><jupyter_text>너비 우선 탐색(BFS)- 새로운 추상 자료구조인 그래프를 사용해 네트워크를 모형화하는 방법- 너비 우선 탐색은 "X로 가는 최단 경로는 무엇일까?"와 같은 문제에 답을 함- 방향 그래프(directed graph)와 무방향 그래프(undirected graph)- 각 정점(node)간의 의존성을 표현하는 정렬 알고리즘의 일종인 위상 정렬을 공부---- 너비 우선 탐색을 사용할 수 있는 경우    - 체커 게임에서 가장 적은 수로 승리할 수 있는 방법을 계산    - 맞춤법 검사기 (실제 단어에서 가장 적은 개수의 글자를 고쳐서 올바른 단어를 만드는 방법)    - 네트워크에서 가장 가까운 의사 선생님 찾기- 그래프    - 연결의 집합을 모형화    - 정점과 간선    - 이어진 정점은 이웃- 큐    - 삽입(enqueue), push    - 제거(dequeue), pop    - 선입 선출, FIFO<jupyter_code>graph = {}
graph["you"] = ["alice", "bob", "claire"]
graph["bob"] = ["anuj", "peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom", "jonny"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []
from collections import deque
search_queue = deque()
search_queue += graph["you"]
search_queue
def person_is_seller(name):
    '''
    m으로 끝나면 망고 판매상
    '''
    return name[-1] == 'm'
def search(name):
    search_queue = deque()
    search_queue += graph[name]
    searched = []
    
    while search_queue:
        person = search_queue.popleft()
        if not person in searched:
            if person_is_seller(person):
                print(person + " is a mango seller!")
                return True
            else:
                search_queue += graph[person]
                searched.append(person)
    return False
search("you")<jupyter_output>thom is a mango seller!
{'fraction_non_alphanumeric': 0.13636363636363635, 'fraction_numerical': 0.0007102272727272727, 'mean_word_length': 2.5943877551020407, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '545524', 'license': 'MIT', 'n_tokens_mistral': 730, 'n_tokens_neox': 897, 'n_words': 162, 'path': 'Grokking-Algorithms/06.breadth-first-search.ipynb', 'repo_name': 'zzsza/Algorithm-Training', 'size': '1408'}