[자료구조] 그래프

정의

- 정점과 간선으로 이루어진 자료구조

- 원소사이의 연결관계를 설정해야 하는 상황에서 유용함

그래프의 정의

 

종류

1. 무방향 그래프 - 간선에 방향성이 없음

- 차수(degree)는 이웃한 정점의 개수를 나타냄

2. 방향 그래프 - 간선에 방향성이 있음

- outdegree: 나가는 간선의 개수

- indegree: 들어오는 간선의 개수

 

3. 순환 그래프 - 간선에의해 사이클이 형성되는 그래프

4. 비순환 그래프 - 간선의 방향성에 의해 사이클이 형성되지 않음

 

5. 완전 그래프 - 모든 두 정점 쌍이 간선으로 연결된 그래프

6. 연결 그래프 - 임의의 두 정점 사이의 경로가 항상 존재하는 그래프

 

표현법

1. 인접 행렬

- 구현 방법: V x V의 2차원 배열 선언 후 연결된 두 정점에는 1을 연결되지 않은 두 정점에는 0을 할당

- 효율적인 상황: 두 점의 연결 여부를 자주 확인할때, E가 V^2에 가까울때

- 방향 그래프일때는 graph[1][2] 인 경우 2번 정점에서 1번 정점으로 가는 간선이 있다는 의미

- 정점이 V개이고 간선이 E개 일때 어떤 두 점이 연결되어있는지 O(1)에 알 수 있음

- O(V^2)의 공간이 필요함, 모든 정점의 목록을 알아내고 싶을때는 O(V)

무방향 그래프(왼), 방향 그래프(오)

2. 인접 리스트

- 구현 방법: V개의 리스트를 만들어 각 리스트에 자신과 연결된 정점을 넣음

- 효율적인 상황: 특정 정점에 연결된 모든 정점을 자주 확인할때, E가 V^2 보다 훨씬 작을때

- 인접 행렬과 비교했을때 정점이 많고 간선의 개수가 적을때 공간복잡도가 효율적임

- 방향 그래프라면 outdegree만 리스트에 넣음

- O(V+E)의 공간이 필요함

무방향 그래프(왼), 방향 그래프(오)

 

참고자료

https://www.youtube.com/watch?v=9iI6fuOLiLg&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=25