[자료구조] 그래프 (Graph)
Graph :
여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조
직접적인 관계? - 두 점 사이를 이어주는 선이 있음(간선)
간접적인 관계? - 몇 개의 점과 선에 걸쳐 이어짐
- 정점 (vertex): =노드(node), 데이터가 저장되는 그래프의 기본 원소(복수형 : vertices)
- 간선 (edge): 정점을 이어주는 선, 정점 간 관계를 나타냄
(단방향 →← / (양방향 ↔) = (무방향 -) ) - 인접 정점 (adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점
- 가중치 그래프 (weighted Graph): 연결의 강도(추가적인 정보)가 얼마나 되는지 적혀져 있는 그래프
- 비가중치 그래프 (unweighted Graph): 연결의 강도가 적혀져 있지 않는 그래프를 뜻합니다.
- 무(방)향 그래프 (undirected graph) ↔ 단방향 그래프
- 진입차수 (in-degree) / 진출차수 (out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지 의미
- 인접 (adjacency): 두 정점 간에 간선이 직접 이어져 있다면 = 두 정점은 인접한 정점
- 자기 루프 (self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우
다른 정점을 거치지 않는다는 것이 특징 - 사이클 (cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현합니다.
그래프를 표현하는 방식 - 인접 행렬 / 인접리스트
인접 행렬
: 그래프의 연결 관계를 이차원 배열로 나타냄 - 모든 정보를 저장
인접하다? = 두 정점을 이어주는 간선이 있다!
adj[i][j] = i에서 j로 가는 길이 있으면 1(true), 없으면 0(false)
단방향 그래프 / 무방향 그래프일 때 다르다.
무방향(=양방향)일 경우 대각선을 기준으로 대칭이 된다.
- 장점: 직관적이며 쉽게 구현 가능
- 단점: 불필요한 정보의 저장이 많으며, 그래프의 크기가 커지면 메모리 초과가 발생할 수 있음
- 사용 : 가장 빠른 경로를 찾을때 사용
- 시간 복잡도 = O(1) / adj[i][j]만 알아보면 되어서!
인접 리스트
: 각 정점이 어떤 정점과 인접하는지 리스트 형태로 표현 - 갈 수 있는 곳만 저장
(순서는 크게 중요치 않음)
adj[i] : 노드 i에 연결된 노드들을 원소로 갖는 vector
- 장점: 필요한 정보만 저장하여 메모리 절약 가능
- 단점: 인접행렬에 비해 다소 어려움
- 사용 : 메모리를 효율적으로 사용하고 싶을 때 인접 리스트를 사용
(인접 행렬은 모든 경우의 수를 저장하기 때문에 메모리 비효율적 사용)
- 구현: 리스트(List)나 벡터(Vector)등의 자료구조를 이용하여 각 정점에서 이동가능한 정점들을 저장
(List나 Vector를 이용한 2차원 배열)