[알고리즘] DFS & BFS

그래프

---

그래프 기본 개념

• node(정점)와 edge(간선)로 이루어진 자료구조
• edge
  • 단방향 or 양방향
  • 가중치 있는 경우 있음

degree란?

• degree(차수)

  • 무방향 그래프에서 node에 연결된 edge 수

• indegree

  • 방향그래프에서 해당 정점으로 들어오는 edge 수

• outdegree

  • 방향그래프에서 해당 정점으로 나가는 edge 수

• 방향그래프에서 총 degree는 edge(outdegree+indegree) 수

path란?

• 여러개일 수 있음
• cycle
  • 한 node에서 다시 동일한 node로 돌아오는 경로

그래프 구현

---

1. 인접 행렬

• node 사이의 edge가 많은 경우,
  특정 node와 node의 연결관계를 많이 확인해야하는 경우에 사용

  • 두 node간의 연결 관계를 N * N 크기의 행렬로 나타냄 (2차원 배열)
  • 시간 복잡도
    • 두 node간의 연결관계 확인 = O(1)
    • 특정 node와 연결돼있는 모든 node 확인 = O(N)
  • 공간 복잡도
    • O(N^2)
    • node 많아지면 사용 불가 (메모리 초과)

2. 인접 리스트

• node 사이의 edge가 적은 경우,
  연결된 node를 탐색해야하는 경우

  • 각 node에 연결된 node들을 리스트 (1차원 배열)에 보관
  • 시간 복잡도
    • 두 node간 연결관계 확인 = O(min(degree(i), degree(j))
    • 특정 node와 연결돼있는 모든 node 확인 = O(degree(i))
  • 공간 복잡도
    • O(N + E)

그래프 탐색 방법

---

• 모든 node 탐색을 위해 edge라 따라 순회하는것
• 탐색 방법
  • BFS (너비)
    • 자식들부터 순차적으로 탐색
    • 그 후, 다른 정점의 자식 탐색
    • queue로 구현
  • DFS (깊이)
    • 최대한 깊게 탐색
    • stack, 재귀함수로 구현
• 탐색 시, 방문 체크 필요
• 시간복잡도
  • 인접행렬 = O(N^2)
  • 인접리스트 = O(N+E)

팁

---

1. 모든 node 방문 시에는 BFS DFS 상관없음
2. 가중치나 특정경로 탐색시에는 DFS
3. 최단거리는 BFS
4. 단방향인지 양방향인지 주의할것