[JAVA/자바 - 그래프] 인접 행렬 구현

오늘은 자바를 이용하여 인접행렬을 구현해보려고 합니다.

 

인접 행렬 

인접행렬은 다음과 같이 무방향 그래프가 존재할 때 
이차원 배열을 이용하여 각 정점에 인접한 정점의 정보를 넣어주는 구조입니다. 

 

인접행렬

1. 정점의 개수에 해당하는 크기의 2차원 배열을 선언 합니다. 
2. 관계를 입력 받습니다.
3. 입력받은 from, to 정보를 배열에 저장해줍니다

공간 복잡도: O(V^2) 
※ V(vertex): 정점 / E(edge): 간선 

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


 public class Main {

    public static void main(String[] args) throws IOException{ 
         int N = 5; //정점 갯수 
         boolean[][] arr = new boolean[N][N];
      
         for(int i=0; i<N; i++){
             st = new StringTokenizer(br.readLine(), " ");
             int from = Integer.parseInt(st.nextToken());
             int to = Integer.parseInt(st.nextToken());

             arr[from][to] = true; 
             arr[to][from] = true; 
         }
     }
 }

 

만약, 간선에 가중치가 있다면 2차원 배열을 boolean이 아닌 int 배열로 만들어 주면 됩니다. 

배열에 연결되지 않은 간선은 -1과 같은 값을 넣어주고 연결된 간선은 해당하는 가중치를 배열안에 값으로 넣어주어 정점끼리의 연결 여부를 확인할 수 있습니다.