728x90
2차원 배열
2차원 배열을 사용하여 정점에서 다른 정점으로 가는 간선의 존재유무(1 : 존재, 0 : 없음)를 알 수 있다. 2차원 배열을 사용할 경우 연결된 정점을 찾기 쉽고 구현이 쉽다는 장점이 있지만 O(n^2)의 공간 복잡도를 가진다는 단점이 있다.
구현 코드
public static void main(String[] args) {
int[][] edges = new int[][] {
{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 5}, {4, 5}
};
int n = 5; //정점의 개수
int[][] matrix = new int[n + 1][n + 1];
for(int[] edge : edges) { //무방향 그래프이기 때문에 양쪽 모두 1로 초기화
matrix[edge[0]][edge[1]] = 1;
matrix[edge[1]][edge[0]] = 1;
}
//출력
for(int i = 1 ; i <= n ; i++) {
for(int j = 1 ; j <= n ; j++) {
System.out.print(matrix[i][j]+" ");
}
System.out.println();
}
}
리스트
배열 대신 리스트를 사용하여 구현하는 것도 가능하다. 2차원 배열을 리스트로 변경한다고 생각하면 되는데 이 때에 1차원만 리스트를 사용한다면 배열 + 리스트의 조합이 되고, 모두 리스트를 사용한다면 리스트 + 리스트 조합이 되는 것이다.
리스트의 경우, 필요한 만큼만 공간을 사용하기 때문에 공간 낭비가 적지만 2차원 배열보다는 구현이 어렵다는 단점이 있다.
배열 + 리스트 구현 코드
public static void main(String[] args) {
int[][] edges = new int[][] {
{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 5}, {4, 5}
};
int n = 5;
ArrayList<Integer>[] list = new ArrayList[n + 1];
for (int i = 0; i <= n; i++) list[i] = new ArrayList<>();
for(int[] edge : edges) {
list[edge[0]].add(edge[1]);
list[edge[1]].add(edge[0]);
}
//출력
for (int i = 1; i <= n; i++) {
for(int j = 0 ; j < list[i].size();j++)
System.out.print(list[i].get(j)+" ");
System.out.println();
}
}
리스트 + 리스트 구현 코드
public static void main(String[] args) {
int[][] edges = new int[][] {
{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 5}, {4, 5}
};
int n = 5;
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
for(int i = 0 ; i <= n ; i++) list.add(new ArrayList<>());
for(int[] edge : edges) {
list.get(edge[0]).add(edge[1]);
list.get(edge[1]).add(edge[0]);
}
//출력
for (int i = 1; i < list.size(); i++) {
for(int j = 0 ; j < list.get(i).size(); j++)
System.out.print(list.get(i).get(j)+" ");
System.out.println();
}
}
728x90
'기타 > 알고리즘' 카테고리의 다른 글
[알고리즘]그래프5 - 다익스트라(feat. Java) (0) | 2023.09.22 |
---|---|
[알고리즘]그래프4 - BFS(feat. Java) (0) | 2023.09.21 |
[알고리즘]그래프3 - DFS(feat. Java) (0) | 2023.09.21 |
[알고리즘] 그래프1 - 그래프란? (0) | 2023.09.21 |
[알고리즘] 자바로 Union Find 구현하기 (0) | 2023.09.20 |