그래프

 

 

 

자료구조에서 그래프는 정점 + 간선

방향의 유무 / 가중치의 유무에 따라 그래프의 종류가 나뉜다.

 

차수 (deg) : 정점에 연결된 간선의 수 / 모든 정점들의 차수 합 = 간선 수 * 2 (시간복잡도 계산에 사용됨)

 

 

그래프 문제를 풀기 위해 컴퓨터에게 그래프 자료구조를 저장하는 방법을 알아야 한다.

 

 

1. 인접 행렬

 

 

 

 

그래프가 연결된 상태를 이차원 배열으로 표현한다.

가중치가 있는 경우는 1이 아니고 가중치로 표현 할 수 있다.

 

구현하기는 쉽지만, 메모리를 효과적으로 사용하기 힘들다.

 

 

 

2. 인접 리스트

 

 

 

 

List자료구조를 활용해 연결된 요소들만 저장한다.

 

 

 

 

주어진 조건에 따라 효과적인 방법으로 그래프를 구현하자.

 

그래프 문제에서 가장 중요한 요소는 이 문제가 그래프 문제인걸 아는 것이다.

문제를 보고 그래프 자료구조를 사용할 수 있도록 문제를 디자인 한 후 그래프를 설계하도록 하자.

 

 

 

그래프에 대한 이해를 바탕으로 그래프 탐색 알고리즘 DFS / BFS를 공부하자.