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

오늘은 자바를 이용하여 인접리스트를 구현해보려고 합니다.

 

인접 리스트 

인접 리스트는 다음과 같이 무방향 그래프가 존재할 때
정점의 개수만큼 리스트를 생성하고 정점의 리스트와 인접한 정점의 정보를 연결해주는 구조입니다. 

인접 리스트

 

1. arraylist를 담을 수 있는 array list를 선언해줍니다.
2. 관계를 입력받습니다. 
3. arraylist[from]에 to 값을 삽입해주고, arraylist[to]에 from값을 삽입해줍니다. 

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

 

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


 public class Main {

    public static void main(String[] args) throws IOException{ 
         int N = 5; //정점 갯수 
         ArrayList<Integer>[] list = (ArrayList<Integer>[]) new ArrayList[N]; //인접 리스트 
         
         for(int i=0; i<N; i++) {
         	list[i] = new ArrayList<Integer>();
         }

         for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine(), " ");
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            
            list[from].add(to);
            list[to].add(from);
         }
     }
 }