그래프 표현 | 인접 행렬

---

📌 두 정점을 연결하는 간선의 유무를 행렬로 표현

---

인접 행렬(Adjacent matrix)

• |V| * |V| 크기의 2차원 배열을 이용해서 간선 정보를 저장
• 행 번호와 열 번호는 그래프의 정점에 대응
• 두 정점이 인접되어 있으면 1, 그렇지 않으면 0으로 표현

무향 그래프일 경우

i번째 행의 합 = i번째 열의 합 = Vi의 차수

유향 그래프일 경우

행 i의 합 = Vi의 진출 차수
열 i의 합 = Vi의 진입 차수

특징

1. 조회가 빠르다.
2. 두 개의 정점이 인접해있는지 바로 조회가 가능하다.
3. 정점에 비해 간선의 수가 적으면 낭비되는 공간이 많아진다.

코드

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(); // 간선의 수

		int[][] adjArr = new int[V + 1][V + 1];

		// 간선을 입력받자
		for (int i = 0; i < E; i++) {
			int startV = sc.nextInt();
			int endV = sc.nextInt();

			// 무향 그래프
			adjArr[startV][endV] = 1;
			adjArr[endV][startV] = 1;

			// 유향 그래프
			adjArr[startV][endV] = 1;
		}
	}
}