그래프 알고리즘 - 입력 받기

그래프의 표현에는 여러가지 방법이 있다.

위와 같은 그래프가 있을 때, 그래프를 표현하는 방법은 크게 두 가지 방법이 있다.

 

인접 행렬

	0	1	2	3	4
0	0	1	0	0	1
1	0	0	0	0	0
2	1	0	0	1	0
3	0	0	1	0	1
4	1	0	0	0	0

 

인접 리스트

 

두 가지 표현 방식은 완전히 정반대의 특성을 가지기 때문에, 구현하려고 하는 문제의 알고리즘 종류나 그래프의 종류에 따라 적절히 선택해 사용해야 한다.

 

 

인접 행렬

정점의 번호 u, v가 주어졌을 때 두 정점을 잇는 간선이 있는지 한 번의 배열 접근만으로 확인할 수 있다.

|V| x |V| 크기의 2차원 배열을 사용하기 때문에 실제 간선의 개수와 관계 없이 항상 O(|V^2|) 크기의 공간을 사용한다는 문제점이 있다.

 

 

인접 리스트

간선 (u, v)가 존재하는지 확인하기 위해서는 연결 리스트를 처음부터 일어가면서 각 원소를 일일이 확인해야 한다.

|V|개의 연결 리스트에 실제 간선 수 만큼의 원소가 들어있으므로 O(|V| + |E|)의 공간만을 사용한다.

간선의 개수가 |V|^2 과 비슷하다면 인접 행렬과 비슷한 메모리를 사용하지만, 실제로 간선 수가 훨씬 더 적은 경우가 많기 때문에 결과적으로 큰 차이가 나게된다.

 

간선의 수가 |V|^2에 비해 훨씬 적은 그래프를 희소그래프라고 하고, 간선의 수가 |V|^2에 비례하는 그래프를 밀집 그래프라고 한다. 희소그래프에 대해서는 인접 리스트를, 밀집 그래프에 대해서는 인접 행렬을 사용하는 것이 유리하다.

 

 

정리

	인접 행렬	인접 리스트
설명	|V| x |V| 크기의 2차원 배열을 사용해 간선 정보 저장	각 정점마다 해당 정점에서 나가는 간선의 목록을 연결 리스트로 저장
공간 복잡도	O(|V^2|)	O(|V| + |E|)
간선 여부 파악	한 번의 배열 접근	연결리스트를 처음부터 읽으면서 각 원소를 일일이 확인
사용	밀집 그래프	희소 그래프

 

 

구현

위의 그래프에서 아래와 같은 간선 정보가 주어진다고 가정한다.

 

입력

0 1
0 4
2 0
2 3
3 2
3 4
4 0

 

인접 행렬 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int N = 5;
        int M = 7;
        int from, to;
        boolean[][] adjMatrix = new boolean[N+1][N+1];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            from = Integer.parseInt(st.nextToken());
            to = Integer.parseInt(st.nextToken());
            adjMatrix[from][to] = true;
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                sb.append(adjMatrix[i][j] ? 1 : 0).append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
}

 

출력 결과

0 1 0 0 1 
0 0 0 0 0 
1 0 0 1 0 
0 0 1 0 1 
1 0 0 0 0

 

인접 리스트 구현 (List 사용)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int N = 5;
        int M = 7;
        List<Integer> [] adjList = new ArrayList[N];
        for (int i = 0; i < N ; i++) {
            adjList[i] = new ArrayList<>();
        }
        int from, to;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            from = Integer.parseInt(st.nextToken());
            to = Integer.parseInt(st.nextToken());
            adjList[from].add(to);
        }
        for (int i = 0; i < N; i++) {
            sb.append(i).append(" : ");
            for (int j = 0; j < adjList[i].size(); j++) {
                sb.append(adjList[i].get(j)).append(" -> ");
            }
            sb.append("end \n");
        }
        System.out.println(sb);
    }
}

 

출력 결과

0 : 1 -> 4 -> end 
1 : end 
2 : 0 -> 3 -> end 
3 : 2 -> 4 -> end 
4 : 0 -> end

 

인접 리스트 구현 (Node 사용)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static class Node {
        int vertex;
        Node link;

        public Node(int vertex, Node link) {
            this.vertex = vertex;
            this.link = link;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int N = 5;
        int M = 7;
        Node[] adjList = new Node[N];
        int from, to;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            from = Integer.parseInt(st.nextToken());
            to = Integer.parseInt(st.nextToken());
            adjList[from] = new Node(to, adjList[from]);
        }
        for (int i = 0; i < N; i++) {
            sb.append(i).append(" : ");
            for (Node temp = adjList[i]; temp != null; temp = temp.link) {
                sb.append(temp.vertex).append(" -> ");
            }
            sb.append("end \n");
        }
        System.out.println(sb);
    }
}

 

출력 결과

0 : 4 -> 1 -> end 
1 : end 
2 : 3 -> 0 -> end 
3 : 4 -> 2 -> end 
4 : 0 -> end

 

주의

출력결과가 0 : 4 -> 1 이라고 4와 1이 이어져있다고 혼동하기 쉬운데 이는 4->1로 연결되어있다는 뜻이 아니라, 0에 4와 1이 각각 연결되어있다는 의미이다. 즉 0->4 이고 0->1 이다.

또한 인접리스트를 List로 구현하는 경우 입력 순서대로 추가되지만, Node를 이용해서 구현하는 경우는 입력 순서의 반대의 결과가 나온다!