그래프는 노드와 그 노드들을 연결하는 간선으로 구성된 자료구조다. 그래프는 여러 가지 방법으로 표현될 수 있고, 대표적으로 인접 행렬(Adjacency Matrix), 인접 리스트(Adjacency List), 간선 리스트(Edge List)가 있다.
✨ 인접 행렬
그래프를 2차원 배열로 표현하는 방법
A[i][j] = 1: 노드 𝑖에서 노드 j로 가는 간선이 존재함
𝐴[i][j] = 0: 노드 i에서 노드 j로 가는 간선이 존재하지 않음
방향 그래프
public static void main(String[] args) {
int V = 6; // 노드의 수 (0부터 6까지 총 7개의 노드)
int[] edge = {0, 1, 0, 2, 0, 5, 0, 6, 4, 3, 5, 3, 5, 4}; // 간선 정보
int[][] adjM = new int[V + 1][V + 1]; // 인접 행렬 초기화
// 간선 정보에 따라 인접 행렬 업데이트
for (int i = 0; i < edge.length / 2; i++) {
int n1 = edge[2 * i];
int n2 = edge[2 * i + 1];
adjM[n1][n2] = 1;
}
// 인접 행렬 출력
for (int[] row : adjM) {
System.out.println(Arrays.toString(row));
}
}[0, 1, 1, 0, 0, 1, 1]
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 1, 1, 0, 0]
[0, 0, 0, 0, 1, 0, 0]무방향 그래프
public static void main(String[] args) {
int V = 6; // 노드의 수 (0부터 6까지 총 7개의 노드)
int[] edge = {0, 1, 0, 2, 0, 5, 0, 6, 3, 4, 3, 5, 4, 5, 4, 6}; // 간선 정보
int[][] adjM = new int[V + 1][V + 1]; // 인접 행렬 초기화
// 간선 정보에 따라 인접 행렬 업데이트 (무향 그래프)
for (int i = 0; i < edge.length / 2; i++) {
int n1 = edge[2 * i];
int n2 = edge[2 * i + 1];
adjM[n1][n2] = 1;
adjM[n2][n1] = 1; // 무향 그래프에서는 대칭 위치도 1로 설정
}
// 인접 행렬 출력
for (int[] row : adjM) {
System.out.println(Arrays.toString(row));
}
}
[0, 1, 1, 0, 0, 1, 1]
[1, 0, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 1, 0]
[0, 0, 0, 1, 0, 1, 1]
[1, 0, 0, 1, 1, 0, 0]
[1, 0, 0, 0, 1, 0, 0]인접 행렬의 장단점
🟢 장점
- 간선의 존재 여부를 indexing으로 접근하기 때문에 O(1) 시간 복잡도로 빠르게 확인할 수 있다.
- 구현이 직관적이고 간단하다.
🔴 단점
- 노드 수가 많아지면 큰 메모리 공간을 차지할 수 있다.
전체 노드의 개수를 v개, 간선의 개수를 E개라고 하면, 노드 i에 연결된 모든 노드들에 방문하고 싶은 경우 adj[i][1]부터 adj[i][V]를 모두 확인해봐야 하기 때문에 총 O(V)의 시간이 걸린다. - 간선의 수가 적은 희소 그래프(sparse graph)에서는 비효율적이다.
✨ 인접 리스트
각 노드에 연결된 노드들의 목록을 저장하는 방식
예를 들어, 노드 A에 연결된 노드가 B와 C라면, 인접 리스트는 다음과 같이 표현된다.
A : [B, C]
B : [A]
C : [A]
방향 그래프
public static void main(String[] args) {
int V = 6; // 노드의 수 (0부터 6까지 총 7개의 노드)
int[] edge = {0, 1, 0, 2, 0, 5, 0, 6, 4, 3, 5, 3, 5, 4, 6, 4}; // 간선 정보
List<List<Integer>> adjL = new ArrayList<>(V + 1);
// 인접 리스트 초기화
for (int i = 0; i <= V; i++) {
adjL.add(new ArrayList<>());
}
// 간선 정보에 따라 인접 리스트 업데이트 (유향 그래프)
for (int i = 0; i < edge.length / 2; i++) {
int n1 = edge[2 * i];
int n2 = edge[2 * i + 1];
adjL.get(n1).add(n2);
}
// 인접 리스트 출력
for (int i = 0; i < adjL.size(); i++) {
System.out.println("Node " + i + ": " + adjL.get(i));
}
}Node 0: [1, 2, 5, 6]
Node 1: []
Node 2: []
Node 3: []
Node 4: [3]
Node 5: [3, 4]
Node 6: [4]
무방향 그래프
public static void main(String[] args) {
int V = 6; // 노드의 수 (0부터 6까지 총 7개의 노드)
int[] edge = {0, 1, 0, 2, 0, 5, 0, 6, 4, 3, 5, 3, 5, 4, 6, 4}; // 간선 정보
List<List<Integer>> adjL = new ArrayList<>(V + 1);
// 인접 리스트 초기화
for (int i = 0; i <= V; i++) {
adjL.add(new ArrayList<>());
}
// 간선 정보에 따라 인접 리스트 업데이트 (무향 그래프)
for (int i = 0; i < edge.length / 2; i++) {
int n1 = edge[2 * i];
int n2 = edge[2 * i + 1];
adjL.get(n1).add(n2);
adjL.get(n2).add(n1); // 무향 그래프에서는 반대 방향도 추가
}
// 인접 리스트 출력
for (int i = 0; i < adjL.size(); i++) {
System.out.println("Node " + i + ": " + adjL.get(i));
}
}Node 0: [1, 2, 5, 6]
Node 1: [0]
Node 2: [0]
Node 3: [4, 5]
Node 4: [3, 5, 6]
Node 5: [0, 3, 4]
Node 6: [0, 4]인접 리스트의 장단점
🟢 장점
- 실제 연결된 노드에 대한 정보만 저장하기 때문에, 모든 원소의 개수의 합이 간선의 개수와 동일하다.
- 즉, 간선의 개수에 비례하는 메모리만 차지하여 구현이 가능하다.
- 각 노드에 연결된 모든 노드들을 방문해 보아야 하는 경우, 인접 리스트로 연결 관계를 저장하는 것이 시간상 큰 이점을 가진다.
🔴 단점
- 노드 i와 j의 연결 여부를 알고 싶을 때, A[i] 리스트를 순회하며 j 원소가 존재하는지 확인해야 한다 → 시간 복잡도 O(V)
- 인접 행렬은 A[i][j]가 1인지 0인지만 확인하면 i와 v 노드의 연결 여부를 O(1)로 확인 가능하다.
✨ 간선 리스트
인접 리스트와 인접 행렬을 모두 사용할 수 없는 경우에 간선 리스트를 사용한다.
간선 리스트는 각각의 간선을 시작 노드와 끝 노드의 쌍으로 표현한다.
간선 리스트의 구성
-
간단한 리스트 형태:
각 간선을 두 개의 노드 쌍으로 표현하는 방법
예를 들어, 그래프에 (A-B), (B-C), (C-D)라는 간선이 있다면, 간선 리스트는 다음과 같다.[[(A, B), (B, C), (C, D)]]
-
가중치 포함 리스트:
가중치가 있는 그래프의 경우, 간선 리스트는 노드 쌍과 함께 각 간선의 가중치를 포함할 수 있다.
예를 들어, (A-B) 간선의 가중치가 3, (B-C) 간선의 가중치가 5라면, 간선 리스트는 다음과 같이 표현될 수 있다.[[(A, B, 3), (B, C, 5), (C, D, 2)]]
간선 리스트의 장단점
🟢 장점
- 매우 단순하고 직관적인 표현 방법이다.
- 간선의 목록을 직접 가지고 있어, 간선에 대한 접근이 용이하다.
- 그래프가 희소할 때(간선이 적을 때) 공간 효율적이다.
🔴 단점
- 특정 노드의 이웃 노드를 찾기 위해 리스트를 순회해야 하므로 시간이 걸린다.
- 특정 노드 쌍에 간선이 존재하는지 확인하는 데 시간이 많이 소요된다.
- 인접 행렬이나 인접 리스트와 비교했을 때, 간선의 존재 여부나 연결된 노드를 찾는 데 효율적이지 않을 수 있다.
사용 예시
간선 리스트는 주로 그래프의 간선 집합을 다루는 알고리즘, 예를 들어 크루스칼(Kruskal) 알고리즘 같은 최소 스패닝 트리 알고리즘에서 자주 사용된다. 이러한 알고리즘에서는 간선의 가중치를 기준으로 간선들을 정렬하거나 선택하는 작업이 중요하기 때문에 간선 리스트 형태가 유리하다.
Reference
[graph] 그래프를 인접행렬 또는 인접리스트로 받아오기
[자료구조] 그래프를 저장하는 방법 3가지 : 인접 행렬, 인접 리스트, 간선 리스트 with Python
