[알고리즘]Graph, BFS와 DFS

Graph란

• $V$ : Vertices( or Nodes)
• $E$ : edges (connect vertex and vertex)

위와 같이 $V, E, e_k$의 집합으로 표현할 수 있음

지하철 노선도와 최단거리 계산은 그래프 알고리즘이 적용된 하나의 예시입니다.

기본 개념

• edge는 vertice의 쌍으로 표현됨 (a,b)
• edge는 방향 또는 weight를 가질 수 있음
• degree 는 vertice에 개입된 edge의 수를 표현
  - loop : 같은 vertice에 연결된 edge
  

Adjacency Matrix( 인접행렬)

• 그래프간 edge관계를 행렬로 나타낸 것
• 방향이 없는 그래프에서는 대칭행렬의 꼴을 보임

Graph Traversal(Search)

Breadth-first Search

• 너비우선 탐색
• queue의 자료구조 활용
  - 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용함
  - 즉 선입선출(FIFO) 원칙으로 탐색
• 최단경로 문제에 적합

Depth-first Search

• 깊이 우선 탐색
• stack 자료구조 또는 Recursive algorithm으로 구현
• 경로의 특징을 저장해둬야 하는 문제에 적합

기타

• 그래프의 모든 정점을 방문하는 것이 주요한 문제라면 어느 것을 쓰든 노상관
• 검색 대상 그래프가 정말 크다면 DFS를 고려
• 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS

Reference

• 고려대학교 뇌영상분석연구실 생체데이터과학 수업자료.
• BFS와 DFS : https://devuna.tistory.com/32