개발조아

그래프 탐색 본문

CS/알고리즘&자료구조

그래프 탐색

개발조아 2021. 10. 19. 18:14
728x90
  • 깊이 우선 탐색(Depth First Search : DFS)
    • 한 정점으로부터 연결된 한 정점으로만 탐색하여 끝까지 탐색하는 방법
    • 한 정점에서 연결된 정점을 찾아 해당 정점으로 이동
    • 만약 연결된 정점이 없다면 이전 정점으로 이동해 다른 정점 탐색
    • 모든 정점에 대해서 탐색이 이루어진다
    • 구현 방법
      • Stack
        • 현재 정점에 연결된 다른 정점을 찾을 시 돌아갈 정점, 즉 현재 정점을 스택에 저장
        • 현재 정점에서 연결할 정점이 없어면 스택에서 다시 정점을 빼서 수행
      • 재귀로도 구현 가능
        • 현재 정점에 연결된 다른 정점이 있다면 다시 재귀 호출
        • 현재 정점에서 연결할 정점이 없다면 해당 재귀 탈출
    • 시간 복잡도
      • O(V+E)
  • 너비 우선 탐색(Breadth First Search : BFS)
    • 한 정점에 연결된 모든 정점을 모두 탐색
    • 트리에서의 레벨순회 처럼 현재 정점을 기준으로 연결된 모든 정점을 탐색
    • 구현방법
      • Queue
        • 탐색할 정점을 순서대로 빼기 위해 큐를 사용 
        • 현재 정점에서 연결된 다른 정점을 큐에 넣는다
        • 현재 정점 탐색이 끝나면 큐에서 다음 정점을 빼서 위의 과정을 반복한다
        • 큐를 활용하여 먼저 탐색한 순서대로 방문을 하기 때문에 가중치가 1인 그래프에서 최단 거리로 이동이 가능
    • 시간 복잡도
      • O(V+E)

'CS > 알고리즘&자료구조' 카테고리의 다른 글

최소 신장 트리(Minimum Spannig Tree)  (0) 2021.10.20
그래프의 최단 경로 탐색  (0) 2021.10.19
그래프(Graph)  (0) 2021.10.19
힙(Heap)  (0) 2021.10.19
이진 탐색 트리(Binary Search Tree)  (0) 2021.10.19
Comments