#dfs
노트 3개
Algorithm › Graph
단절점과 단절선지우면 그래프가 끊어지는 정점(단절점)과 간선(단절선)을 DFS 방문 순서와 low 값으로 O(V + E)에 찾는 방법.
Algorithm › Graph
오일러 경로와 오일러 회로모든 간선을 정확히 한 번씩 지나는 경로·회로의 존재 조건(차수의 짝홀)과, 히어홀저 알고리즘으로 O(V + E)에 회로를 구하는 방법. 다중 간선에서 이미 쓴 간선을 다시 훑지 않는 요령을 함께 정리한다.
Algorithm › Search
깊이 우선 탐색 (DFS)한 갈래를 갈 수 있는 데까지 파고든 뒤 되돌아오는 그래프 탐색으로, 스택이나 재귀로 구현한다.