• 이미지 출처: 나노 바나나 프로 (Nano Banana Pro)

1. 인접 행렬 (Adjacency Matrix)

• 그래프를 행렬로 구현
• 정점의 개수가 $N$일 때, $N \times N$ 크기의 2차원 배열
• matrix[i][j] = 1이면 $i$와 $j$가 연결됨, 0이면 연결되지 않음 (가중치 그래프라면 1 대신 가중치 값 저장)

import java.io.*;
import java.util.*;
public class Main {

	static Scanner sc= new Scanner (System.in); 
	static int arr[][];
	public static void main(String[] args) {
		int N,T; 
		N = sc.nextInt();
		T = sc.nextInt();
		//N번노드까지 있으니까 N+1*N+1이상의 size로 만들어야 함!
		arr = new int[N+1][N+1];
		for(int i=0; i<T; i++) {
			int from=sc.nextInt();
			int to = sc.nextInt();
			//단방향연결
			arr[from][to] = 1;
			//양방향연결
			//arr[to][from] = 1;
		}
		
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=N; j++) {
				System.out.print(arr[i][j]+" ");
			}
			System.out.println();
		}
	}
		
}

2. 인접 리스트 (Adjacency List)

• 그래프를 리스트로 구현
• 각 정점마다 리스트(List, Vector, ArrayList 등)를 하나씩 가짐
• list[i]에는 정점 $i$와 실제로 연결된 정점들만 들어있음

import java.io.*;
import java.util.*;

public class Main {
	static Scanner sc= new Scanner (System.in); 
	static int arr[][];
	public static void main(String[] args) {
		int arr[] = new int[10];
		ArrayList<Integer> al[] = new ArrayList[10];
		for(int i=0; i<10; i++) {
			al[i] = new ArrayList<>();
		}
		//2 -> 3 
		//4 -> 5
		//add로 맨뒤에 값을 삽입가능
		al[2].add(3);
		al[2].add(4);
		al[2].add(1);
		al[4].add(5);
		//get(idx)에 저장된 value를 찾을 수 있다.
		for(int i=0; i<al[2].size(); i++) {
			System.out.print(al[2].get(i)+" ");
		}
		//size()로 요소갯수 알수 있다.
		//isEmpty()로 비었는지 여부 : 비어있으면 true, 요소가 들어있으면 false return;
	}
		
}```