자바 [JAVA] - 그래프(Graph)

그래프란?

객체 사이의 연결 관계를 표현할 수 있는 Cyclic한 자료구조이다.
그래프는 인접행렬(AdjacencyMatrix)과 인접리스트(AdjacencyList)로 표현할 수 있다.
그래프는 정점(Vertex)과 그 사이를 잇는 간선(Edge)으로 이루어진다.
- G = (V, E)는 정점의 집합 V와 간선의 집합 E라고 할 때, 그래프 G는 V와 E의 집합 (V, E)라는 뜻이다.
- V(G)는 그래프 G의 정점 집합이고, E(G)는 그래프 G의 간선 집합이다. 간선은 (정점 v, 정점 w)형식이다.
- 예시)
  V(G) = {1, 2, 3, 4, 5} => 정접 집합
  E(G) = {(1, 2), (3, 1), (3, 2), (4, 1), (5, 2), (5, 4)} => 간선 집
이때, 정점의 위치 정보나 간선의 순서와 같은 정보는 그래프의 정의에 포함되지 않는다.

추가) 트리도 그래프의 한 종류이다.

그래프 구조

정점(Vertex): 노드(node), 데이터 저장
간선(Edge): 노드와 노드를 연결하는 선 (link, branch)
분지수, 정점의 차수(Degree)
- 무방향 그래프에서 하나의 정점에 붙어있는 간선 개수
- 무방향 그래프 모든 정점 차수의 합 = 그래프 간선의 수 2배
내향 분지수 or 진출 차수(in-degree): 방향 그래프에서 외부에서 들어오는 간선의 수
외향 분지수 or 진입 차수(out-degree): 방향 그래프에서 외부로 나가는 간선의 수
인접
- 인접(adjacent): 정점 사이 간선이 있음
- 부속(incident): 정점과 간선 사이 관계
경로(path): 출발지에서 목적지로 가는 순서
경로 길이(path length) : 경로를 구성하는데 사용된 간선의 수
단순 경로(simple path): 경로 중 반복되는 정점이 없음, 한붓그리기처럼 같은 간선 지나지 않음
사이클(cycle): 단순 경로의 출발지와 목적지가 같은 경우

그래프의 특징과 트리와의 차이

그래프 종류

무방향 그래프(Undirected Graph)

간선에 방향이 없는 그래프이다. 정점 v와 정점 w를 연결하는 간선을 (v, w)라고 하면, (v, w)와 (w, v)는 같은 간선이다.
정점 n개일 때 무방향 그래프가 가질 수 있는 최대 간선 수는 n(n-1)/2개 이다.

방향 그래프(Directed Graph)

간선에 방향이 있는 그래프이다.

정점 v에서 w로 가는 간선을 (v, w)라고 하고, 이때는 간선 (w, v)와 다르다.
정점 n개일 때 방향 그래프가 가질 수 있는 최대 간선 수는 n(n-1)개 이다.

완전 그래프(Complete graph)

모든 정점에 간선이 있고, 한 정점에서 다른 정점과 모두 연결되어 있다.

정점이 N개일 경우, 간선의 수는 n(n-1)/2 개

가중치 그래프(Weighted graph)

간선에 가중치(=비용)가 있다.

그래프 구현 - Java

그래프는 인접행렬 또는 인접리스트로 표현할 수 있다.

1. 그래프 구현 - 인접행렬

2차원 배열 matrix 사용
matrix[v][w] = 1 : 정점 v에서 정점 w로 가는 간선이 있음
matrix[v][w] = 0 : 정점 v에서 정점 w로 가는 간선이 없음
예시) 정점 5는 정점 2와 정점 4와 연결되어있음, 위의 행렬이 matrix라고 하면 matrix[5][2] = 1, matrix[5][4] =1 이고 나머지는 0
장점
- 연결된 정점 찾기 빠름 O(1)
- 구현 쉬움
단점
- O(n^2)의 공간복잡도 가짐

구현 코드

public static void main(String[] args) {
    // 간선 
    int[][] edges = new int[][]{
            {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 5}, {4, 5}
    };

    int n = 5; // 정점의 개수
    int[][] matrix = new int[n + 1][n + 1];
    
    // 무방향 행렬 구성
    for (int[] edge : edges) {
        matrix[edge[0]][edge[1]] = 1;
        matrix[edge[1]][edge[0]] = 1;
    }

    // 출력
    System.out.print("  ");
    for (int i = 1; i < n + 1; i++) {
        System.out.print(i + " ");
    }
    System.out.println();

    for (int i = 1; i < n + 1; i++) {
        System.out.print(i + " ");
        for (int j = 1; j < n + 1; j++) {
            System.out.print(matrix[i][j] + " ");
        }
        System.out.println();
    }
}

출력 결과

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

2. 그래프 구현 - 인접 리스트

배열과 연결 리스트 사용
정점의 개수만큼 헤드 노드가 있고, 각 정점에 인접한 정점들 리스트로 연결
정점 v의 인접 정점이 w와 z라면 헤드노드 v에 w와 z가 연결 리스트로 연결되어있음
예시) 정점 5는 정점 2와 정점 4와 연결되어있음, 5번 인덱스에 2와 4가 리스트로 연결
장점
- 필요한 만큼 공간 사용하기 때문에 공간 낭비 적음
- 노드의 추가, 삭제가 빠름
단점
- 간선 정보 확인이 상대적으로 오래 걸
- 인접 행렬보다 구현 어려움

구현 코드 - 1. 배열 + 리스트

	public static void main(String[] args) {
		int[][] edges = new int[][] {
			{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 5}, {4, 5}
		};
		
		int n = 5;
		
		ArrayList<Integer>[] list = new ArrayList[n + 1];

		for (int i = 0; i <= n; i++) list[i] = new ArrayList<>();
		
		for(int[] edge : edges) {
			list[edge[0]].add(edge[1]);
			list[edge[1]].add(edge[0]);
		}
		
        //출력
		for (int i = 1; i <= n; i++) {
			for(int j = 0 ; j < list[i].size();j++)
				System.out.print(list[i].get(j)+" ");
			System.out.println();
		}
	}

구현 코드 - 2. 리스트 + 리스트

	public static void main(String[] args) {
		int[][] edges = new int[][] {
			{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 5}, {4, 5}
		};
		
		int n = 5;
		
		ArrayList<ArrayList<Integer>> list = new ArrayList<>();
		
		for(int i = 0 ; i <= n ; i++) list.add(new ArrayList<>());
		
		for(int[] edge : edges) {
			list.get(edge[0]).add(edge[1]);
			list.get(edge[1]).add(edge[0]);
		}
		
        //출력
		for (int i = 1; i < list.size(); i++) {
			for(int j = 0 ; j < list.get(i).size(); j++) 
				System.out.print(list.get(i).get(j)+" ");
			System.out.println();
		}
	}

참고