그래프 - 인접행렬/인접리스트

그래프 표현 - ① 인접행렬

 

인접행렬 (무방향그래프, 가중치 1일 때)

 

- 정점 두 개의 관계가 v1->v2, v1-v2 와 같이 연결되어 있는 경우(인접해있는 경우) 간선의 가중치를 배열로 표현한다.

 

- 장점 : 구현이 용이하고, v1->v2 의 가중치와 연결 여부를 한 번에 탐색할 수 있다. (v1->v2의 가중치==arr[v1][v2]이므로)

 

- 단점 : 임의의 정점에 연결된 정점을 알기 위해서 정점의 개수만큼 탐색해야 하고,

              인접관계를 저장하기 위한 배열의 크기가 nXn 만큼 필요하다. -> 간선 개수가 적을 경우 비효율

 

 

 

코드 구현 - ① 인접행렬

/* 입력 예시:
   5 6 (정점 개수, 간선 개수)
   0 1 (정점0 - 정점1 인접)
   0 2
   0 4
   1 3
   2 3
   2 4
*/

public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;
    
    st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken()); //정점 개수
    int m = Integer.parseInt(st.nextToken()); //간선 개수
    
    int[][] graph = new int[n][n];
    
    for(int i=0; i<m; i++){
    	st = new StringTokenizer(br.readLine());
        int v1 = Integer.parseInt(st.nextToken());
        int v2 = Integer.parseInt(st.nextToken());
        graph[v1][v2] = graph[v2][v1] = 1;
    }
	
    br.close();
}    

 

 

 

 

그래프 표현 - ② 인접리스트

 

인접리스트 (무방향그래프, 가중치 1일 때)

 

- 정점 두 개의 관계가 v1->v2, v1-v2 와 같이 연결되어 있는 경우(인접해있는 경우) 간선의 가중치를 리스트로 표현한다.

   : LinkedList, ArrayList 이용

 

- 장점 : 간선의 개수가 적은 경우 효율적이고(메모리 절약 가능), 임의의 정점과 연결된/인접한 정점 탐색에 유용하다.

              정점 추가/삭제 가 쉽고 빠르다. 

 

- 단점 : 정점 간 연결 관계를 파악하기 위해서는 연결된 정점을 모두 거치는 탐색 과정이 필요하다.

 

 

 

코드 구현 - ② 인접리스트

/* 입력 예시:
   5 6 (정점 개수, 간선 개수)
   0 1 (정점0 - 정점1 인접)
   0 2
   0 4
   1 3
   2 3
   2 4
*/

public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;
    
    st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken()); //정점 개수
    int m = Integer.parseInt(st.nextToken()); //간선 개수
    
    ArrayList<Integer>[] graph = new ArrayList[n];
    for(int i=0; i<n; i++){
    	graph[i] = new ArrayList<>();
    }
    
    for(int i=0; i<m; i++){
    	st = new StringTokenizer(br.readLine());
        int v1 = Integer.parseInt(st.nextToken());
        int v2 = Integer.parseInt(st.nextToken());
        graph[v1].add(v2);
        graph[v2].add(v1);
    }
	
    br.close();
}