1. 너비우선 탐색 (Breadth-First Search)

사전 조건

- 각각의 노드로 연결되어 있는 트리구조
- 시작점과 가까운것 위주의 탐색 기법
- 최단 경로 찾기, 미로 찾기에서 사용
 -Queue를 사용

동작 방식

- 시작 노드를 탐색하고 방문처리.
- 시작 노드의 연결을 Queue에 담아준다.
- Queue에서 하나씩 꺼낸 값을 시작노드로 설정하고 위 작업을 반복해준다.
- 작업을 반복할 때 이미 탐색한 노드는 탐색하지 않는다.
- 탐색이 완료된 순서대로 출력한다.

동작 순서 예시

[1]
[1, 2]
[1, 2, 3]
[1, 2, 3, 4]
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5, 7]
[1, 2, 3, 4, 5, 7, 9]
[1, 2, 3, 4, 5, 7, 9, 6]
[1, 2, 3, 4, 5, 7, 9, 6, 8]

시간 복잡도

O(V + E)
    - 인접 리스트 인경우
    - 모든 정점에 대해 존재하는 간선만 탐색
    - 정점의 수(Vertex) + 간선의 수(Edge)

python 구현

    '''
    @ Author : bsh0817
    @ Created : 2020. 01. 29
    @ Update : 2020. 01. 29
    @ Description : BFS, Breadth-First Search (너비우선탐색)
    '''
    import queue


    def fn_breadthfirst_search(dict_input):
        '''
            @Description: BFS, Breadth-First Search (너비우선 탐색)

            @Arguments Example
                # 0~10 사이의 정수라 가정
                dict_input = {
                    1:[2, 3],
                    2:[1, 4, 5, 7],
                    3:[1, 5, 9],
                    4:[2, 6],
                    5:[2, 3, 7, 8],
                    6:[4],
                    7:[5, 2],
                    8:[5],
                    9:[3]
                }
        '''
        responce = []
        list_end = [1]
        queue_list = queue.Queue()
        queue_list.put(1)

        while queue_list.qsize() >= 1:
            int_value = queue_list.get()
            for int_resource_index in range(len(dict_input[int_value])):
                if dict_input[int_value][int_resource_index] not in list_end:
                    queue_list.put(dict_input[int_value][int_resource_index])
                    list_end.append(dict_input[int_value][int_resource_index])
            responce.append(int_value)
            print(responce)

    if __name__ == "__main__":
        list_fn_breadthfirst_search_param={
            1:[2, 3],
            2:[1, 4, 5, 7],
            3:[1, 5, 9],
            4:[2, 6],
            5:[2, 3, 7, 8],
            6:[4],
            7:[5, 2],
            8:[5],
            9:[3]
        }
        print(fn_breadthfirst_search(list_fn_breadthfirst_search_param))