그래프 탐색 - BFS, DFSPermalink

BFS, DFSPermalink

• BFS (너비우선탐색) : 자식 탐색 완료 후 자식의 자식 탐색 …
• DFS (깊이우선탐색) : 자식과 자식의 자식 … 탐색 후 다른 자식, 자식의 자식 … 순서로 탐색

BFSPermalink

• 원리 : 시작점에 연결된 Vertex를 찾고 Queue에 저장. Queue의 가장 먼저 것 뽑아서 반복
• 시간복잡도 : O(V+E)

DFSPermalink

• 구현 방법 : 재귀함수 (-> 백트래킹), stack
• 원리 : 시작점에 연결된 Vertex를 찾고, 더 이상 연결된 Vertex가 없을 때까지 연결된 계속 찾음(재귀함수). 더 이상 연결된 Vertex가 없으면 다음 노드 탐색
• 시간복잡도 : O(V+E)

재귀함수Permalink

• 자기 자신을 다시 호출하는 함수
• 주의
  • 재귀함수 종료 시점 명시
  • 재귀함수 깊이 너무 깊어지면 Stack Overflow
    • Stack Overflow : 메모리에 함수를 호출. 호출된 함수는 아래부터 쌓임(stack) 이 스택이 넘치면(메모리 초과) Stack Overflow
• DFS, 백트래킹

참고 자료

• 코딩테스트 알고리즘 - 1. BFS
• 코딩테스트 알고리즘 - 2. DFS