그래프 표현 | 인접 리스트

---

📌 각 정점에 연결되어 있는 모든 정점을 저장
📌 배열 안에 인접 정점들이 담긴 리스트를 저장하는 것

---

인접 리스트(Adjacent List)

• 각 정점에 대한 인접 정점들을 순차적으로 표현
• 하나의 정점에 대한 인접 정점들을 각각 노드로 하는 연결 리스트로 저장

무방향 그래프일 경우

💡 여기서의 노드는 리스트의 노드

노드 수 = 간선의 수 * 2
각 정점의 노드 수 = 정점의 차수

유향 그래프일 경우

💡 여기서의 노드는 리스트의 노드

노드 수 = 간선의 수
각 정점의 노드 수 = 정점의 진출 차수

특징

1. 메모리 효율이 좋다.
2. 조회가 느리다. (리스트의 특성으로 인해)

코드

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class 인접리스트 {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int V = sc.nextInt(); 
        // 정점의 개수 V (시작 정점이 0인지 1인지는 문제에 따라 다름)
		int E = sc.nextInt(); // 간선의 수

		// adjList 배열에 List<Integer>인 타입의 자료가 들어가겠다
		List<Integer>[] adjList = new ArrayList[V+1];
		
		// List<Integer>를 ArrayList 객체로 생성해서 배열에 넣기
		for(int i = 0; i < V+1; i++) {
			adjList[i] = new ArrayList<>();
		}
		
		// 정점들 저장
		for(int i = 0; i< E; i++) {
			int startV = sc.nextInt();
			int endV = sc.nextInt();
			
			// 무향 그래프일 경우
			adjList[startV].add(endV);
			adjList[endV].add(startV);
			
			// 유향 그래프일 경우
			adjList[startV].add(endV);
		}
	}
}