[기초] 그래프

그래프는 가장 중요한 자료구조이다.

정점의 개수 V , 간선의 개수 E

같은 정점을 두 번이상 방문 않는 것. 단순 경로 / 사이클

사이클 (원래로 돌아오는 경로)

directed graph 와 undirected graph( bidirection graph ) 가 있다.

차수 degree 는 정점과 연결되어 있는 간선의 개수이다.In degree 와 out degree 로 나눈다.

그래프의 표현

그래프를 저장하는 방법을 배울 것이다.그래프는 정점 / 간선 을 저장하면 된다.정점 : 정점의 개수만 저장한다.간선 : 개수 / 간선을 어떻게 저장할 것인가.간선을 저장하는 효율을 생각 하려면 한 정점 V와 연결된 모든 정점을 구하는 시간 을 고려해야 한다. 또한, 방향성을 고려해야 한다.효율적으로 저장하는 방법.

1. 인접 행렬 (2차원 배열)

공간 : V^2 / 효율성 : V / 장점 : 임의의 두 정점 사이에 간선의 유무 파악 용이 ( O(1) )

거의 사용하지 않는다. 공간을 너무 많이 차지 하기 때문이다. 없는 간선을 다 저장하기 떄문

2. 인접 리스트 (리스트)

A[i] = i 와 연결된 모든 정점을 리스트로 포함하고 있음.

공간 : E / 효율성 : O(정점의 차수) / 장점 : 한 정점과 연결된 모든 간선을 찾는 것이 빠름.

c++ STL 의 vector 로 구현 하자. 가중치가 있는 것이라면 같이 기록한다.

간선 리스트 (edge list) 도 있는데, 잘 안쓴다.

3과 연결되어 있는것은 cnt[3 - 1] ~ cnt[3] - 1 까지 이다.

ABCDE (13023)