2. 깊이우선탐색(Depth-First Search)

사전 조건

- 각각의 노드로 연결되어 있는 트리구조
- 깊이를 우선으로 탐색한다.
- Stack를 사용

동작 방식

- 시작 노드를 탐색하고 방문처리.
- 시작 노드의 연결을 Stack에 담아준다.
- Stack에 마지막에 넣은 값 중에서 방문하지 않은 노드를 찾아 이동한다.
- 이동한 노드를 시작노드로 잡고 위 작업을 반복해준다,
- 탐색이 완료된 순서대로 출력한다.

예시 소스 결과

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

시간 복잡도

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

python 구현

    '''
    @ Author : bsh0817
    @ Created : 2020. 01. 29
    @ Update : 2020. 01. 29
    @ Description : DFS, Depth-First Search (깊이우선탐색)
    '''

    def fn_depthfirst_search(dict_input, int_start, list_end):
        '''
            @Description: DFS, Depth-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]
                }
        '''
        list_end.append(int_start)
        for int_index in range(len(dict_input[int_start])):
            if dict_input[int_start][int_index] not in list_end:
                fn_depthfirst_search(dict_input, dict_input[int_start][int_index], list_end)
        return list_end


    if __name__ == "__main__":
        list_fn_depthfirst_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_depthfirst_search(list_fn_depthfirst_search_param, 1, []))