인접리스트

정점의 개수가 클때 인접행렬로 하기에는 비효율적

 

인접리스트

정점 개수만큼 리스트 객체 생성

간선 정보가 들어올때 해당 정점 리스트에 연결된 번호 추가

경로 탐색시 해당 정점 리스트의 사이즈만큼만 돌면 됨

연결된 선인지 확인할 필요가 없음(방문 했는지만 체크)

 

예시

ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
int n = 5; //점 개수
int m = 9; //간선 개수

//점 개수만큼 리스트 생성 (0번째는 사용 x)
for (int i = 0; i <= n; i++) {
   graph.add(new ArrayList<>());
}
   
//간선 개수만큼 돌면서 해당 점 리스트에 연결된 점 번호 추가
for (int i = 0; i < m; i++) {
    int a = kb.nextInt();
    int b = kb.nextInt();
    graph.get(a).add(b);
}