[JAVA] 그래프 구현 방법 2가지

그래프 구현 방법 2가지

그래프를 구현할 때, 보통 ArrayList를 이용하였는데, Map을 이용하여 구현하는 방법도 익혀보고자 작성하게 되었습니다.

ArrayList<TYPE>[]

• 배열을 사용
• 그래프 크기가 고정되어 있어야하므로, 최대 크기로 배열의 크기를 선언해야 함

final int MN = 100;
ArrayList<Integer>[] graph = new ArrayList[MN];
for(int i=0; i<MN; ++i) graph[i] = new ArrayList<>();

Map<Type, List<Type>>

• Map 사용
• 그래프 크기가 동적으로 사용될 수 있음

// HashMap으로 구현(노드 번호를 Key, 해당 노드와 연결된 다른 노드들의 번호를  List로 관리)
Map<Integer, List<Integer>> graph = new HashMap<>(); 

int s = 10; // 임의의 시작 노드 번호
int e = 11; // 임의의 끝 노드 번호
graph.putIfAbsent(s, new ArrayList<>()); // s라는 키가 없으면, ArrayList 새로 생성
graph.get(s).add(e); // Map이므로, get(s)를 이용하여 ArrayList를 불러와 add(e)로 e를 추가

그 외 메소드

graph.containsKey(key); // boolean 값으로 리턴.