[자료 구조] Java로 그래프 구현하기 :: 인접 리스트로 구현한 그래프

To Do

• 인접 리스트란?
• 가중치가 없는 그래프를 인접 리스트로 구현하기
• 가중치가 있는 그래프를 인접 리스트로 구현하기

 

 

지난 시간에 우리는 인접 행렬로 그래프를 그리는 시간을 가졌다.

오늘은 그래프를 그리는 또 다른 방법인 인접 리스트로 그래프를 그려보자.

인접 리스트

Adjancency List 인접 리스트는

 

Geeksforgeeks.org

한 노드에 연결 상태를 연결 리스트로 구현한 것을 의미한다.

 

우리가 아까 위에서 만들어 놨던 임의의 그래프를 토대로 연결 리스트로 만들어보자.

 

노드가 6개가 있으므로 1번 노드부터 관계를 찾아보자

 

1 -> 2

2 -> 1 - 3 - 4

3 -> 2 - 4 - 5

4 -> 3 - 5 - 6

5 -> 3 - 4

6 -> 4

 

 

관계를 찾았으니 이제 각 노드에 해당하는 연결 리스트를 만들어보자.

 

 

소스 코드

우리는 인접 리스트를 주로 그래프에서 많이 쓸 예정이다.

 

그래프에는 여러 종류가 있겠지만 조금 크게 나누자면 2가지 종류가 있다.

 

1. 가중치가 없는 그래프

2. 가중치가 있는 그래프

 

이 두 버전 모두 구현을 해보겠다.

 

 

가중치가 없는 그래프

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

public class Main {

    public static void main(String[] args) throws IOException{
    	// 입출력 처리
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = 4 // 정점의 개수 == 노드 갯수
        int m = 5 // 간선의 개수
        
        // 인접 리스트
		ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        
        // 인접 리스트로 구성한 그래프에 ArrayList를 넣어주면서 초기화
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        
		/** 입력 예시
        *	1  2
        *   1  3
        *   1  4
        *   2  4
        *   3  4
        */
        for (int i = 0; i < m; i++) {
            String[] nv = br.readLine().split(" ");
            int n1 = Integer.parseInt(nv[0]);
            int n2 = Integer.parseInt(nv[1]);

            graph.get(n1).add(n2);
            graph.get(n2).add(n1);
        }

		1번 인접 리스트에서 4번 인접 리스트까지 출력
        for(int i = 1; i <= 4; i++){
        	bw.write(graph.get(i).toString());
        }
        bw.flush();
        bw.close();
    }
}


// 출력 : [2, 3, 4][1, 4][1, 4][1, 2, 3]

 

이렇게 가중치가 없는 그래프는 인접 리스트를 하나 생성하고 노드의 개수만큼 반복을 돌며 ArrayList 객체 할당을 해준다.

 

그리고 간선의 수 만큼 반복을 또 돌며 그래프 연결 상태를 입력 받고 각각의 그래프에 추가해준다.

 

알고리즘 문제풀이에서 자주 사용되는 BufferedReader와 Writer로 구현을 해보았다.

 

가중치가 있는 그래프

import java.util.ArrayList;
import java.util.Scanner;

class Edge<W, V> {
    private W weight;
    private V v;

    public void setEdge(W weight, V v) {
        this.weight = weight;
        this.v = v;
    }
}

public class Main {


    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        int n = 4; // 노드의 갯수
        int m = 5; // 간선의 갯수

        ArrayList<Edge<Integer, Integer>> graph = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            graph.add(new Edge<>());
        }

        for (int i = 0; i < m; i++) { // 간선의 갯수만큼 반복
            int n1 = input.nextInt(); // 노드 1
            int n2 = input.nextInt(); // 노드 2

            int weight = input.nextInt();

            graph.get(n1).setEdge(n2, weight);
            graph.get(n2).setEdge(n1, weight);
        }
    }
}

 

가중치가 있는 그래프에는 우리의 인접 리스트에 연결된 그래프 뿐만 아니라 그에 대한 가중치도 넣어야 하기 때문에 Edge 클래스를 새롭게 만들어준다.

 

그 Edge 클래스에는 가중치와 노드 번호가 들어가게 된다.

 

이번에는 자바에서 일반적으로 많이 사용되는 Scanner 로 입출력을 처리해보았다.

특징

 

	특징	공간 복잡도
인접 리스트	특정 정점에 접근하려면 연결된 모든 정점 방문해야함	v라는 간선의 수는 O(V+E)