[자바/JAVA] 자바로 그래프(Graph) 직접 구현해보기 -인접 행렬, 인접 리스트

 

 

 

rvrlo - [자료구조] 그래프(Graph)

자바를 이용해서 그래프를 직접 구현해보려고 한다.

그래프에 대한 설명은 위 링크에서 확인할 수 있다. 이 글에서는 설명 없이 코드로 구현한 과정만 적는다.

 

 

---

 

 

인접 행렬로 무향 그래프 구현하기

무방향 그래프를 구현할 것이기 때문에 입력받은 정점은 뒤바꿔서 서로 연결을 다시 해줘야 한다.
방향 그래프로 구현한다면, [ from → to ]만 연결해줘도 된다.

 

 

사용하는 메서드 - add, getPrint

    public static void add(int from, int to){
        graph[from-1][to-1] = 1;
        graph[to-1][from-1] = 1;
    }

	public static String getPrint(){
        StringBuilder print = new StringBuilder();
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                print.append(graph[i][j]).append(" ");
            }
            print.append("\n");
        }
        return print.toString();
    }

먼저 메서드를 가져왔다.

모든 인덱스는 0부터 시작하기 때문에 값을 넣어줄 때는 [인덱스-1]로 넣어주었다.
사용자 입장에서 보이는 대로 값을 입력하기 위해 -1을 해주었는데, 처음부터 크기를 size+1로 초기화해줘도 되지만
인접 행렬은 공간복잡도 $O(n^2)$으로 n이 커질수록 더 많은 메모리가 필요해 size를 입력받은 그대로 두었다.

인접 행렬로 되어있어 중첩for문을 이용해 행렬을 순회한다.
매트릭스 출력은 StringBuilder의 append를 이용해 연결해주고 그 결과를 String타입으로 반환한다.

 

 

구성하는 필드

    static int size;
    static int[][] graph;

정점의 개수를 입력받을 size

우리가 사용할 graph

 

 

main 함수

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        System.out.print("정점 개수: ");
        size = Integer.parseInt(sc.nextLine());

        graph = new int[size][size];

        while(true){
            String input = sc.nextLine();
            if(input.equals("/")) break;

            String[] inputR = input.split(" ");
            add(Integer.parseInt(inputR[0]), Integer.parseInt(inputR[1]));
        }

        System.out.println(getPrint());
    }

Scanner를 이용해 입력 받는다.
정점의 개수(size)를 먼저 입력해주고, size만큼 2차원 배열을 만들어준다.

그 뒤에 / 를 입력받을 때까지 반복하면서 연결할 정점을 입력한다.
두 숫자는 띄어쓰기(" ")로 구분해서 각 인덱스에 from, to 순서로 들어간다.
지금은 무방향 그래프이기 때문에 from과 to가 뒤바뀌어도 되지만, 방향 그래프를 구현할 때는 순서에 주의해야 한다.

 

 

구현할 그래프 이미지

 

1	2	3	4	5
4	3	2	1	1
5	5	4	3	2

 

첫 행이 from 그 아래는 to 값으로 들어간다.
무방향 그래프로 from 3까지만 입력해줘도 뒤에 4와 5는 자동으로 연결이 된다.

 

 

입력 내용과 출력 결과

정점 개수 5를 입력받아 5*5 크기의 배열이 만들어졌다.
각 정점을 띄어쓰기 기준으로 입력하고, 간선을 다 입력하면 / 를 입력한다.

마지막에는 데칼코마니 형태의 무방향 그래프를 구현한 인접 행렬

 

배열로 되어 있어 인덱스로 바로 접근할 수 있는 장점이 있다.

 

 

---

 

 

인접 리스트로 무향 그래프 구현하기

이번엔 인접 리스트를 이용해서 무방향 그래프를 만든다.

인접 리스트는 ArrayList<ArrayList<Integer>> 형태로 만들어준다. 이유는 코드를 보면서 알 수 있다.

 

 

구성하는 필드

    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static int size;

인접 리스트가 어떻게 되어있는지 알아야 한다.
각 ArrayList 안에 자기 Node와 연결된, 다른 노드가 ArrayList로 들어간다.
ArrayList Node → ArrayList edgeNode

size를 입력받으면 전체 Node 수에 맞춰서, 연결할 Node를 저장할 ArrayList를 인스턴스화 해줘야 한다.
인접 리스트 방식으로 구현할 때는 해당 메서드가 추가되었다.

 

같은 단어가 반복되니 파란색으로 칠한 부분과 쉼표로 나누어둔 부분, 밑줄을 그어둔 부분으로 잘 구분해야 한다...

1. size를 입력받으면 연결 노드의 ArrayList 인스턴스화
2. 큰 ArrayList와 그 안에 들어갈 ArrayList 구분
3. 연결할 Node도 ArrayList 형태

 

 

사용하는 메서드 - add, getPrint, initialize

인접 행렬과 비슷하지만 미묘하게 달라졌기 때문에 하나하나 설명해보려고 한다.
단순히 행렬 인덱스로 지명하는 것보다 조금 더 복잡해진 모습을 보인다.

 

	public static void add(int from, int to){
        graph.get(from-1).add(to-1);
        graph.get(to-1).add(from-1);
    }

    public static String getPrint(){
        StringBuilder print = new StringBuilder();
        // 1.
        for (int i = 0; i < size; i++) {
            ArrayList<Integer> node = graph.get(i);
            print.append(i+1).append("번 노드: ");
            // 2.
            for (int j = 0; j < node.size(); j++) {
                print.append(node.get(j) + 1);
                // 3.
                if (j < node.size()-1) {
                    print.append(" -> ");
                }
            }
            print.append("\n");
        }

        return print.toString();
    }

1. ArrayList<Integer> node = graph.get(i)

그래프에서 전체 ArrayList의 인덱스를 가져온다. → Node ArrayList

 

2. node.get(j)+1

여기서 각 Node와 연결된 edgeNode를 가져온다.
Node도 ArrayList 형태로 되어 있어 ArrayList.get(index)를 사용한다.

그래프에서 각 노드의 리스트를 node라는 이름으로 빼왔으니 node.get( j /연결된 각 노드/ )로 불러온다.
뒤에 +1은 0번부터 시작되는 인덱스를 눈으로 보기 편하게 숫자를 맞춰준 것

 

3. if ( j <node.size()-1 )

사실 인접리스트 구현에 딱히 필요는 없지만 출력 형태를 예쁘게 만들어주려고 추가했다.
연결된 노드를 모두 출력하고, 마지막 노드는 다음으로 넘어갈 -> 표시가 필요 없어서 추가한 조건문.

 

 

    public static void initialize(){
        for (int i = 0; i < size; i++) {
            graph.add(new ArrayList<>());
        }
    }

인접 행렬과 다르게 새로 추가된 초기화 메서드

노드의 개수 size에 맞게 ArrayList를 초기화한다.
안에 값을 넣어주는 건 아니지만, 전체 노드의 개수에 따라서 ArrayList를 만들어주기 위해 필요한 메서드

graph : (
　ArrayList 0 : ( new ArrayList ),
　ArrayList 1 : ( new ArrayList ),
　... ,
　Arraylist n : ( new ArrayList ) )

빨간색은 맨 처음 선언할 때 초기화를 해준 new ArrayList, size에 맞게 ArrayList 안에 new ArrayList를 add로 추가

 

 

main 함수

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("정점 개수: ");
        size = Integer.parseInt(sc.nextLine());
        initialize();

        while(true){
            // 동일
        }

        System.out.println(getPrint());
    }

메인에서 동작은 다 동일하고, 초기화 하는 initialize() 만 추가하면 된다.

 

 

구현할 그래프 이미지

 

1	2	3	4	5
4	3	2	1	1
5	4	4	2	2
	5		3

 

처음에 그림을 막 그렸더니 모든 노드가 2개씩만 연결되어 있어서 간선 하나를 더 추가했다.
출력 형태는 인접행렬과 다르게 -> 로 연결된 모습으로 나올 것이다.

위에 있는 표에 적어둔 형태로 나오면 성공

 

 

입력 내용과 출력 결과

getPrint에서 쓸데없는 3번 조건문을 추가해준 덕분에 마지막 노드 뒤에는 화살표가 없는 예쁜 출력 형태 완성