그래프와 탐색

그래프란??

자료 구조로써 그래프 = 정점 + 간선의 형태를 그래프라고 한다.

간선 => (무방향 / 방향) + 가중치

무방향 = 양방향 이라고도 함

정점의 차수(Degree)와 성질

모든 정점의 차수의 합 = 간선의 개수의 2배이다.

 

그래프를 저장하는 대표적인 두가지 방법

1. 인접 행렬

2. 인접 리스트

 

탐색이란??

시작점에서 간선을 0개 이상 사용해서 갈 수 있는 정점들은?

1. 깊이 우선 탐색 (DFS)

2. 너비 우선 탐색 (BFS)

상황에 따라서 어떤 것을 사용해야 할지 결정해야한다.