ABOUT ME

Today
Yesterday
Total
  • 깊이우선탐색(DFS, Depth-First Search)
    Algorithm/Algorithm_Theory 2022. 11. 23. 23:55

    DFS(Depth-First Search) 

    - '깊이'를 우선적으로 탐색하는 알고리즘

    - DFS를 구현하는 방식은 재귀(recursive) 방식과 스택(stack) 방식이 있다

    # 재귀 dfs는 해당 노드의 주변 노드를 탐색할때 첫번째 노드부터 탐색 
    # stack dfs는 해당 노드의 주변 노드를 탐색할때 맨 뒤 부터 노드부터 탐색

     

    (1) 시작 노드인 노드 1을 스택에 삽입하고 방문 처리

     

    (2) 스택 내 최상단 노드인 노드 1에 인접한 노드는 2, 3이 있습니다. 번호가 낮은 노드 2를 스택에 삽입하고 방문 처리

     

    (3) 스택 내 최상단 노드인 노드 2에 인접한 노드 8을 스택에 삽입하고 방문 처리

    (4) 스택 내 최상단 노드인 노드 8에 인접한 노드는 6과 7이 있으며, 번호가 낮은 노드 6을 스택에 삽입하고 방문 처리

    (5) 스택 내 최상단 노드인 노드 6에 인접하며 방문하지 않은 노드 7을 스택에 삽입하고 방문 처리

     

    (6) 최상단 노드인 노드 7에 인접하며 방문하지 않은 노드가 없으므로 스택에서 노드 7를 꺼냄

     

    (7) 최상단 노드인 노드 6에 인접하며 방문하지 않은 노드가 없으므로 스택에서 노드 6을 꺼냄 

    (8) 최상단 노드인 노드 8에도 인접하며 방문하지 않은 노드가 없으므로 스택에서 노드 8을 꺼냄

    (9) 최상단 노드인 노드 2에 인접하며 방문하지 않은 노드가 없으므로 스택에서 노드 2를 꺼냄 

    (10) 노드 1에 인접하면서 방문 이력이 없는 노드 3을 스택에 삽입하고 방문 처리

    (11) 노드 3에 인접하면서 방문하지 않은 노드는 노드 4와 5가 있지만, 번호가 낮은 노드 4를 스택에 삽입하고 방문 처리

    (10) 노드 4에 인접한 노드 5를 스택에 넣고 방문 처리

     (11) 이제 방문하지 않은 노드가 없기 때문에 스택에서 모든 노드를 차례대로 꺼냄

     


    DFS 노드의 탐색 순서, 스택에서 꺼낸 순서

    1 -> 2 -> 8 -> 6 -> 7 -> 3 -> 4 -> 5

     

     

     

    # DFS 메서드 정의
    def dfs (graph, node, visited):
        # 해당 노드를 방문 처리
        visited[node] = True
        # 탐색 순서 출력
        print(node, end = ' ')
        # 한 노드로부터 인접한 다른 노드를 재귀적으로 방문 처리
        for i in graph[node]:
            if not visited[i]:
                dfs(graph, i, visited)
                
    graph = [
        [],
        [2, 3],
        [1, 8],
        [1, 4, 5],
        [3, 5],
        [3, 4],
        [7, 8],
        [6, 8],
        [2, 6, 7]
    ]
    
    # 노드별로 방문 정보를 리스트로 표현
    visited = [False] * 9
    
    # 정의한 DFS 메서드 호출(노드 1을 탐색 시작 노드로 설정)
    dfs(graph, 1, visited)

    출처: https://heytech.tistory.com/55

     

    'Algorithm > Algorithm_Theory' 카테고리의 다른 글

    재귀(Recursive)  (0) 2022.12.11
    그래프(Graph)  (0) 2022.11.30
    너비우선탐색(BFS, Breadh-Frist Search)  (0) 2022.11.23
    스택(Stack)  (0) 2022.11.14
    큐(Queue)  (1) 2022.11.13

    댓글

Designed by Tistory.