To Do
- 인접 리스트란?
- 가중치가 없는 그래프를 인접 리스트로 구현하기
- 가중치가 있는 그래프를 인접 리스트로 구현하기
지난 시간에 우리는 인접 행렬로 그래프를 그리는 시간을 가졌다.
오늘은 그래프를 그리는 또 다른 방법인 인접 리스트로 그래프를 그려보자.
인접 리스트
Adjancency List 인접 리스트는
한 노드에 연결 상태를 연결 리스트로 구현한 것을 의미한다.
우리가 아까 위에서 만들어 놨던 임의의 그래프를 토대로 연결 리스트로 만들어보자.
노드가 6개가 있으므로 1번 노드부터 관계를 찾아보자
1 -> 2
2 -> 1 - 3 - 4
3 -> 2 - 4 - 5
4 -> 3 - 5 - 6
5 -> 3 - 4
6 -> 4
관계를 찾았으니 이제 각 노드에 해당하는 연결 리스트를 만들어보자.
소스 코드
우리는 인접 리스트를 주로 그래프에서 많이 쓸 예정이다.
그래프에는 여러 종류가 있겠지만 조금 크게 나누자면 2가지 종류가 있다.
1. 가중치가 없는 그래프
2. 가중치가 있는 그래프
이 두 버전 모두 구현을 해보겠다.
가중치가 없는 그래프
import java.io.*;
import java.util.ArrayList;
public class Main {
public static void main(String[] args) throws IOException{
// 입출력 처리
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = 4 // 정점의 개수 == 노드 갯수
int m = 5 // 간선의 개수
// 인접 리스트
ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
// 인접 리스트로 구성한 그래프에 ArrayList를 넣어주면서 초기화
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<>());
}
/** 입력 예시
* 1 2
* 1 3
* 1 4
* 2 4
* 3 4
*/
for (int i = 0; i < m; i++) {
String[] nv = br.readLine().split(" ");
int n1 = Integer.parseInt(nv[0]);
int n2 = Integer.parseInt(nv[1]);
graph.get(n1).add(n2);
graph.get(n2).add(n1);
}
1번 인접 리스트에서 4번 인접 리스트까지 출력
for(int i = 1; i <= 4; i++){
bw.write(graph.get(i).toString());
}
bw.flush();
bw.close();
}
}
// 출력 : [2, 3, 4][1, 4][1, 4][1, 2, 3]
이렇게 가중치가 없는 그래프는 인접 리스트를 하나 생성하고 노드의 개수만큼 반복을 돌며 ArrayList 객체 할당을 해준다.
그리고 간선의 수 만큼 반복을 또 돌며 그래프 연결 상태를 입력 받고 각각의 그래프에 추가해준다.
알고리즘 문제풀이에서 자주 사용되는 BufferedReader와 Writer로 구현을 해보았다.
가중치가 있는 그래프
import java.util.ArrayList;
import java.util.Scanner;
class Edge<W, V> {
private W weight;
private V v;
public void setEdge(W weight, V v) {
this.weight = weight;
this.v = v;
}
}
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = 4; // 노드의 갯수
int m = 5; // 간선의 갯수
ArrayList<Edge<Integer, Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new Edge<>());
}
for (int i = 0; i < m; i++) { // 간선의 갯수만큼 반복
int n1 = input.nextInt(); // 노드 1
int n2 = input.nextInt(); // 노드 2
int weight = input.nextInt();
graph.get(n1).setEdge(n2, weight);
graph.get(n2).setEdge(n1, weight);
}
}
}
가중치가 있는 그래프에는 우리의 인접 리스트에 연결된 그래프 뿐만 아니라 그에 대한 가중치도 넣어야 하기 때문에 Edge 클래스를 새롭게 만들어준다.
그 Edge 클래스에는 가중치와 노드 번호가 들어가게 된다.
이번에는 자바에서 일반적으로 많이 사용되는 Scanner 로 입출력을 처리해보았다.
특징
| 특징 | 공간 복잡도 | |
| 인접 리스트 | 특정 정점에 접근하려면 연결된 모든 정점 방문해야함 | v라는 간선의 수는 O(V+E) |
댓글7