컴퓨터알고리즘#15

LeeMir, 19 May 2021

그래프 순회

그래프 순회
  • 모든 정점과 간선을 검사함으로써 그래프를 탐험하는 체계적인 절차
  • 주요 전략 : 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)
깊이 우선 탐색
  • 그래프를 순회하기 위한 일반적 기법
  • 그래프의 모든 정점과 간선을 방문
  • 그래프가 연결 그래프인지 결정
  • 그래프의 연결 요소들을 계산
  • 그래프의 신장 숲을 계산
  • 그래프 내 싸이클 찾기
  • 이진트리의 선위 순회와 유사
  • 정점과 간선의 라벨을 읽고 쓰는데 O(1)의 시간 소요
  • 각 정점은 두 번 라벨
    • 한 번은 Fresh로, 또 한 번은 Visited로
  • 각 간선은 두 번 라벨
    • 한 번은 Fresh로, 또 한 번은 Tree 또는 Back으로
  • 그래프가 인접리스트 구조로 표현된 경우, DFS는 O(n+m) 시간에 수행
너비 우선 탐색
  • 그래프를 순회하기 위한 일반적 기법
  • 그래프의 모든 정점과 간선을 방문
  • 그래프가 연결 그래프인지 결정
  • 그래프의 연결 요소들을 계산
  • 그래프의 신장 숲을 계산
  • 그래프 내 단순싸이클 찾기
  • 이진트리의 레벨 순회와 유사