그래프의 표현에는 여러가지 방법이 있다.
위와 같은 그래프가 있을 때, 그래프를 표현하는 방법은 크게 두 가지 방법이 있다.
인접 행렬
0 | 1 | 2 | 3 | 4 | |
0 | 0 | 1 | 0 | 0 | 1 |
1 | 0 | 0 | 0 | 0 | 0 |
2 | 1 | 0 | 0 | 1 | 0 |
3 | 0 | 0 | 1 | 0 | 1 |
4 | 1 | 0 | 0 | 0 | 0 |
인접 리스트
두 가지 표현 방식은 완전히 정반대의 특성을 가지기 때문에, 구현하려고 하는 문제의 알고리즘 종류나 그래프의 종류에 따라 적절히 선택해 사용해야 한다.
인접 행렬
정점의 번호 u, v가 주어졌을 때 두 정점을 잇는 간선이 있는지 한 번의 배열 접근만으로 확인할 수 있다.
|V| x |V| 크기의 2차원 배열을 사용하기 때문에 실제 간선의 개수와 관계 없이 항상 O(|V^2|) 크기의 공간을 사용한다는 문제점이 있다.
인접 리스트
간선 (u, v)가 존재하는지 확인하기 위해서는 연결 리스트를 처음부터 일어가면서 각 원소를 일일이 확인해야 한다.
|V|개의 연결 리스트에 실제 간선 수 만큼의 원소가 들어있으므로 O(|V| + |E|)의 공간만을 사용한다.
간선의 개수가 |V|^2 과 비슷하다면 인접 행렬과 비슷한 메모리를 사용하지만, 실제로 간선 수가 훨씬 더 적은 경우가 많기 때문에 결과적으로 큰 차이가 나게된다.
간선의 수가 |V|^2에 비해 훨씬 적은 그래프를 희소그래프라고 하고, 간선의 수가 |V|^2에 비례하는 그래프를 밀집 그래프라고 한다. 희소그래프에 대해서는 인접 리스트를, 밀집 그래프에 대해서는 인접 행렬을 사용하는 것이 유리하다.
정리
인접 행렬 | 인접 리스트 | |
설명 | |V| x |V| 크기의 2차원 배열을 사용해 간선 정보 저장 | 각 정점마다 해당 정점에서 나가는 간선의 목록을 연결 리스트로 저장 |
공간 복잡도 | O(|V^2|) | O(|V| + |E|) |
간선 여부 파악 | 한 번의 배열 접근 | 연결리스트를 처음부터 읽으면서 각 원소를 일일이 확인 |
사용 | 밀집 그래프 | 희소 그래프 |
구현
위의 그래프에서 아래와 같은 간선 정보가 주어진다고 가정한다.
입력
0 1
0 4
2 0
2 3
3 2
3 4
4 0
인접 행렬 구현
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
int N = 5;
int M = 7;
int from, to;
boolean[][] adjMatrix = new boolean[N+1][N+1];
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
from = Integer.parseInt(st.nextToken());
to = Integer.parseInt(st.nextToken());
adjMatrix[from][to] = true;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
sb.append(adjMatrix[i][j] ? 1 : 0).append(" ");
}
sb.append("\n");
}
System.out.println(sb);
}
}
출력 결과
0 1 0 0 1
0 0 0 0 0
1 0 0 1 0
0 0 1 0 1
1 0 0 0 0
인접 리스트 구현 (List 사용)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
int N = 5;
int M = 7;
List<Integer> [] adjList = new ArrayList[N];
for (int i = 0; i < N ; i++) {
adjList[i] = new ArrayList<>();
}
int from, to;
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
from = Integer.parseInt(st.nextToken());
to = Integer.parseInt(st.nextToken());
adjList[from].add(to);
}
for (int i = 0; i < N; i++) {
sb.append(i).append(" : ");
for (int j = 0; j < adjList[i].size(); j++) {
sb.append(adjList[i].get(j)).append(" -> ");
}
sb.append("end \n");
}
System.out.println(sb);
}
}
출력 결과
0 : 1 -> 4 -> end
1 : end
2 : 0 -> 3 -> end
3 : 2 -> 4 -> end
4 : 0 -> end
인접 리스트 구현 (Node 사용)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static class Node {
int vertex;
Node link;
public Node(int vertex, Node link) {
this.vertex = vertex;
this.link = link;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
int N = 5;
int M = 7;
Node[] adjList = new Node[N];
int from, to;
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
from = Integer.parseInt(st.nextToken());
to = Integer.parseInt(st.nextToken());
adjList[from] = new Node(to, adjList[from]);
}
for (int i = 0; i < N; i++) {
sb.append(i).append(" : ");
for (Node temp = adjList[i]; temp != null; temp = temp.link) {
sb.append(temp.vertex).append(" -> ");
}
sb.append("end \n");
}
System.out.println(sb);
}
}
출력 결과
0 : 4 -> 1 -> end
1 : end
2 : 3 -> 0 -> end
3 : 4 -> 2 -> end
4 : 0 -> end
주의
출력결과가 0 : 4 -> 1 이라고 4와 1이 이어져있다고 혼동하기 쉬운데 이는 4->1로 연결되어있다는 뜻이 아니라, 0에 4와 1이 각각 연결되어있다는 의미이다. 즉 0->4 이고 0->1 이다.
또한 인접리스트를 List로 구현하는 경우 입력 순서대로 추가되지만, Node를 이용해서 구현하는 경우는 입력 순서의 반대의 결과가 나온다!
'알고리즘 > 개념 정리 (알고리즘 문제 해결 전략)' 카테고리의 다른 글
그래프 알고리즘 - 깊이 우선 탐색(DFS) 알고리즘 (0) | 2023.04.11 |
---|