[개념 학습 및 정리] 그래프

1. 자료구조

• 스택
• 큐
• 트리
• 그래프

 

 

 

2. 그래프

1) 그래프 

그래프는 정점과 간선으로 이루어진 자료구조이다. 현실 세계의 많은 것들을 그래프로 나타낼 수 있기에(지하철 노선, 지도, 페이스북, 등) 그래프와 관련된 문제가 매우 많다. 따라서 그래프와 관련된 수학적 정리가 매우 많으며 이론도 어렵고 구현도 어렵다.

 

그래프의 용어는 4가지가 있다.

• 정점 (Node)
• 간선 (Edge)
• 차수 (Degree) : 정점에 연결된 간선의 개수
• 사이클 (Cycle) : 특정 노드에서부터 시작해 다시 자기 자신으로 돌아올 수 있는 경로

 

그래프에 관한 기본적인 수학적 지식은 다음과 같다.

• 간선의 개수는 정점의 제곱보다 작거나 같다.
• 각 정점의 차수의 합은 간선의 개수의 2배와 같다.

2) 인접 행렬 구현

그래프는 2차원 배열에 0(연결x)과 1(연결o)로 정점의 연결 관계를 표현하여 구현이 가능하다.

인접 행렬

인접 행렬은 2차원 배열로 구현하기 때문에, 노드 x와 y가 연결되어 있는지에 대한 여부는 O(1)의 시간복잡도로 빠르게 찾을 수 있다. 하지만 2차원 배열이기에 무조건 n^2 만큼의 크기를 가지며, 노드 x와 연결된 정점을 찾을 때에는 실제 인접한 정점 수와 관계 없이 무조건 O(n)의 시간복잡도를 가진다는 단점이 있다.

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

public class Main {

    private static int node; // 정점의 개수
    private static int edge; // 간선의 개수
    private static int[][] graph;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st_1 = new StringTokenizer(br.readLine());
        node = Integer.parseInt(st_1.nextToken());
        edge = Integer.parseInt(st_1.nextToken());

        graph = new int[10][10];
        for(int i = 0; i < edge; i++) {
            StringTokenizer st_2 = new StringTokenizer(br.readLine());
            int y = Integer.parseInt(st_2.nextToken());
            int x = Integer.parseInt(st_2.nextToken());

            graph[y][x] = 1;
            graph[x][y] = 1;
        }

        for(int i = 1; i <= node; i++) {
            for(int j = 1; j <= node; j++) {
                bw.write(graph[i][j] + " ");
            }
            bw.newLine();
        }
        bw.close();
        br.close();
    }
}
/*
5 6
1 2
1 3
1 4
2 4
4 5
3 5
 */

3) 인접 리스트 구현

인접 리스트를 이용한 구현은 각각의 정점에 대해 인접한 정점 변호를 저장하는 방법이다.

인접 리스트 구현

인접 리스트는 노드 x와 y가 연결되어 있는지에 대한 여부는 인접한 정점을 모두 봐야하기 때문에 O(dev(n)), 차수 만큼 걸린다. 하지만 노드 x와 연결된 정점을 찾을 때에는 O(dev(n)) 만큼 필요한 만큼만 보기 때문에 인접 행렬에 비해 빠르게 찾을 수 있다. 또한 필요한 공간 만큼만 활용할 수 있다는 장점을 가지고 있다.

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

class ListGraph {
    private ArrayList<ArrayList<Integer>> listGraph;

    public ListGraph(int listSize) {
        this.listGraph = new ArrayList<ArrayList<Integer>>();

        for(int i = 0; i < listSize + 1; i++) {
            listGraph.add(new ArrayList<Integer>());
        }
    }

    // 그래프 반환
    public ArrayList<ArrayList<Integer>> getListGraph() {
        return this.listGraph;
    }

    // 그래프의 특정 노드 반환
    public ArrayList<Integer> getNode(int n) {
        return this.listGraph.get(n);
    }

    // 그래프 추가 (양방향)
    public void put(int n, int m) {
        listGraph.get(n).add(m);
        listGraph.get(m).add(n);
    }

    // 그래프 추가 (단방향)
    public void putSingle(int n, int m) {
        listGraph.get(n).add(m);
    }

    public void printListGraph() {
        for(int i = 1; i < listGraph.size(); i++) {
            System.out.print("정점 : " + i + "의 인접리스트");

            for(int j = 0; j < listGraph.get(i).size(); j++) {
                System.out.print("--> " + listGraph.get(i).get(j));
            }
            System.out.println();
        }
    }
}
public class Main {

    public static void main(String[] args) throws IOException {

        ListGraph listGraph = new ListGraph(6);
        listGraph.put(1,2);
        listGraph.put(1,3);
        listGraph.put(2,3);
        listGraph.put(2,4);
        listGraph.put(3,4);
        listGraph.put(3,5);
        listGraph.put(4,5);
        listGraph.put(4,6);

        listGraph.printListGraph();
    }
}

---

Vector

• 필요에 따라 크기를 동적으로 조절할 수 있는 동적 배열을 구현한다.
• 배열과 동일하게 정스 인덱스를 이용하여 배열에 접근할 수 있다.
• 동기화(Thread Safe) 되어 있으며 한번에 하나의 스레드만 벡터의 메서드를 호출할 수 있다.

 

ArrayList

• Java 표준 배열보다 약간 느릴 수 있지만 배열에서 많은 조작이 필요할 때 유용하게 사용된다.
• 기본 데이터 타입에 대해 만들 수 없기 때문에 객체(Wrapper)에 대해 참조해서 사용한다.
• 검색에 용이하나 삽입과 삭제 빈번한 데이터인 경우에는 부적합하다.

 

LinkedList

• 노드가 연결된 형태이다.
• 검색에는 적합하지 않지만 삽입과 삭제가 빈번한 데이터에 적합하다.

 

Vector vs ArrayList

• 동기화

Vector는 동기화가 되지만 ArrayList는 동기화가 되지 않은 상태이다. 즉, Vector는 한번에 하나의 스레드만 접근할 수 있으며 ArrayList는 동시에 여러 스레드가 적업할 수 있다. ArrayList에서 여러 스레드가 동시에 접근하는 경우 개발자가 명시적으로 동기화하는 코드를 추가해주어야 한다.

 

• 스레드 안전

스레드 안전은 멀티 스레드 프로그래밍에서 여러 스레드가 동시에 접근이 이루어져도 프로그램 실행에 문제가 없음을 뜻한다. 즉, Vector는 동기화가 되어있어 한번에 하나의 스레드만 접근할 수 있기 때문에 안전하다. ArrayList에도 스레드 안전을 보장하기 위해서는 명시적으로 동기화를 해주어야 한다.

 

• 성능

ArrayList는 동기화를 하지 않기 때문에 동기화된 Vector보다 더 빠르다.

 

• 크기 증가

Vector와 ArrayList 모두 동적 배열 클래스로 최대 인덱스를 초과할 때추가되는 인덱스 수가 다르다. Vector는 현재 배열의 크기의 100%가 증가하며 ArrayList는 현재 배열의 크기의 50%가 증가한다. 즉, Vector는 모자른 공간을 확보하는 과정에서 메모리를 많이 잡아먹는다는 단점이 있따.

 

결국, 멀티 스레드 환경이 아니라면 ArrayList를 사용하는 것이 바람직하다.

4) 그래프 순회

• 깊이 우선 탐색, DFS (Depth First Search) - 스택을 이용하여 순회하는 방법
• 너비 우선 탐색, BFS (Breath First Search) - 큐를 이용하여 순회하는 방법