1. 그래프란?
: 정점 (vertex, node)와 간선 (edge)로 구성된 자료구조이다.
데이터 간의 연결 관계를 표현하는 데 사용된다.
2. 그래프의 구성 요소
- 정점(Vertex) : 데이터를 표현하는 기본 단위이다.
- 간선(Edge) : 정점 간의 연결을 나타낸다. 두 정점이 연결되었는지와 관계를 표현한다.
3. 그래프 종류
- 방향 그래프(Directed Graph) : 간선에 방향이 있는 그래프.
- 무방향 그래프(Undirected Graph) : 간선에 방향이 없는 그래프.
- 가중치 그래프(Weighted Graph) : 간선에 가중치(비용, 거리, 시간 등)가 있는 그래프.
- 비가중치 그래프(Unweighted Graph) : 간선에 가중치가 없는 그래프.
- 연결 그래프(Connected Graph) : 모든 정점이 최소한 하나의 간선으로 연결된 그래프.
- 비연결 그래프(Disconnected Graph) : 일부 정점이 연결되지 않은 그래프.
- 사이클 그래프(Cyclic Graph) : 정점을 따라 이동하다가 처음 정점으로 돌아올 수 있는 순환 구조가 있는 그래프.
- 비사이클 그래프(Acyclic Graph) : 순환 구조가 없는 그래프.
4. 구현방법
(1) 인접 행렬
: 2차원 배열을 사용하여 노드 간의 연결 관계를 표현한다.
- 장점 : 정점 간의 관계를 빠르게 확인 가능하다.
- 단점 : 메모리 낭비가 클 수 있다.
0 1 2
0 [0, 1, 1]
1 [1, 0, 0]
2 [0, 1, 0]
// 1 : 연결 O
// 0 : 연결 X(2) 인접 리스트
: 연결된 노드에 대한 정보만 리스트 형식으로 저장한다.
- 장점 : 간선의 개수에 비례하기 때문에 메모리에 효율적이다.
- 단점 : 특정 간선 존재 여부를 확인하는데 시간이 오래 걸린다.
0: [1]
1: [0, 1, 1]
2: [1, 1]
3: [0, 1]