[graph] 인접 배열로 방향 그래프 구현하기

★ 정점의 개수 n개 ,  모서리의 개수 m개 ★

 

앞의 무방향 그래프를 구현한 게시글과 마찬가지로

n X n 이차원 배열(정점의 수에 대한 정방행렬)을 사용하여 두 정점 사이에 간선이 존재하면 1, 존재하지 않으면 0으로 저장한다.

행렬의 대각선 값은 항상 0이다.

그러나 <i,j> ≠ <j,i> 이므로 대칭을 이루지는 않는다.

 

예시 방향 그래프

 

인접 배열로 표현

행 i의 합 = 정점 i의 진출 차수

열 i의 합 = 정점 i의 진입 차수

ex) 정점 2의 진출 차수 = 0 + 0 + 1 + 1 = 2

정점 2의 집입 차수 = 1 + 0 + 0 + 0 = 1

---

JAVA 구현 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(bf.readLine()); //정점의 수
        int M = Integer.parseInt(bf.readLine()); //간선의 수

        //인접행렬로 그래프 구현 - 0번 인덱스 사용X
        int[][] graph = new int[N+1][N+1];
        StringTokenizer st;
        for(int i = 0; i < M; i++){
            st = new StringTokenizer(bf.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            //방향 그래프이므로 x->y로 저장
            graph[x][y] = 1;
        }
    }
}