ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • DFS & BFS
    알고리즘 2020. 3. 16. 16:50

    들어가기 전, 

    그래프의 탐색이란? 어떤 정점에서 출발하여 그래프의 모든 정점을 방문하는 것

                              깊이를 우선으로 하는 깊이 우선 탐색과 너비를 우선으로 하는 너비 우선 탐색이 있다.

     

    1. DFS (Depth First Search) 깊이 우선 탐색

    • 개념? 현재 정점에서 이동할 수 있는 점들까지 들어가면서 탐색하는 방법
    • 모든 정점(혹은 노드라고도 부름)를 방문하고자 하는 경우에 사용
    • 다른 정점으로 이동할 수 없을때, 이전 정점으로 돌아가야하므로 거쳐온 정점들을 모두 저장해 주어야 한다.
    • 구현 방법? 스택 또는 재귀함수로 구현, 즉 후입선출(LIFO) 원칙으로 탐색
    • 어떤 정점을 방문했는지의 여부를 반드시 검사해야한다. *검사안할 경우 무한루프에 빠질 수 있다.*

    (ex)

    dfs 

     

    2. BFS (Breadth Frist Search) 너비 우선 탐색

    • 개념? 현재 정점에서 가까운 정점부터 순서대로 탐색하는 방법
    • 두 정점 사이의 최단 경로 혹은 임의의 경로를 찾고자 하는 경우에 사용
    • 구현 방법? 로 구현, 즉 선입선출(FIFO) 원칙으로 탐색
    • DFS와 마찬가지로, 어떤 정점을 방문했는지의 여부를 반드시 검사해야한다.

    (ex)

    bfs

     

    마지막으로 dfs와 bfs를 비교해보자면,

    간단함 검색속도
    DFS 가 BFS 보다 구현이 간단하다. DFS 가 BFS에 비해서 느리다
    DFS는 모든 정점을 방문할때, BFS는 정점들 사이의 최단거리를 구할때 사용한다는 것을 다시 한번더 기억하자.

     

    '알고리즘' 카테고리의 다른 글

    Greedy Algorithm  (0) 2020.03.17
    Floyd-Warshall  (0) 2020.03.17
    Dijkstra  (0) 2020.03.17
    Binary Serach  (0) 2020.03.16
    DP  (0) 2020.03.16

    댓글

Designed by Tistory.