그래프 종류 및 DFS, BFS

그래프

노드(vertex)와 간선(edge)으로 이루어진 자료구조

종류

1. Undirected (무방향 그래프)
2. Directed (방향 그래프)

무방향 그래프

그래프 간, 방향이 없음 (구현 시, 양방향)

방향 그래프

그래프 간, 방향을 표시

가중 그래프

무방향 그래프, 방향 그래프 간 가중치가 적용된 그래프

표현 방식

1. 인접 행렬
2. 인접 리스트

인접 행렬

주 대각선을 따라 대칭

[
  [0, 1, 0, 0, 1],
  [1, 0, 1, 1, 1],
  [0, 1, 0, 1, 0],
  [0, 1, 1, 0, 1],
  [1, 1, 0, 1, 0]
]

인접 리스트

1. 이중리스트

[
  [],
  [2, 5],
  [1, 5, 3, 4],
  [2, 4],
  [2, 5, 3],
  [4, 1, 2],
]

1. 딕셔너리

{
  'A': [2, 5],
  'B': [1, 5, 3, 4],
  'C': [2, 4],
  'D': [4, 1, 2]
}

BFS (너비우선탐색)

• 큐를 사용
• 최단 거리 보장

루트 s로 부터 도달 할 수 있는 모든 정점을 포함하는 ‘너비우선트리’를 만듦

너비우선트리

그래프 내에서 시작 정점으로부터 각 정점까지 최단 경로를 나탄는 트리 구조

DFS (깊이우선탐색)

• 스택, 재귀
• 최단거리 보장 x

더 깊이 탐색하는 것

깊이우선트리로 구성된 깊이 우선 포리스트를 형성한다.

각 정점에 시간 기록을 할 수 있다.

시간 기록

정점 v를 발견했을 때, v.d / 정점 v에 대한 탐색을 마쳤을 때 v.f

연결 그래프

• 한 붓 그리기 가능 => 사이클 구조

비연결 그래프

• 한 붓 그리기 불가능