[Java] 비선형 자료구조 - Graph

비선형 자료구조란, 선형 구조와 달리 비선형적인 계층 구조를 가지는 자료구조를 말한다. 다시 말해, 하나의 자료 뒤에 여러개의 자료가 존재할 수 있는 자료구조를 말한다.

Graph

• 정점(Vertex)과 간선(Edge)으로 이루어진 집합
  • 정점은 Node라고도 하며, 데이터를 저장한다.
  • 간선은 객체들을 연결한다.
• $G = (V, E)$ 와 같이 표현 가능하다.

그래프 관련 용어

• 인접 정점(adjacent vertex): 간선에 의해 직접 연결된 정점
• 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 - 무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배
• 진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수 (내차수 라고도 부름)
• 진출 차수(out-degree): 방향 그래프에서 외부로 향하는 간선의 수 (외차수 라고도 부름)
  • 방향 그래프에 있는 정점의 진입 차수 또는 진출 차수의 합 = 방향 그래프의 간선의 수(내차수 + 외차수)
• 경로 길이(path length): 경로를 구성하는 데 사용된 간선의 수
• 단순 경로(simple path): 경로 중에서 반복되는 정점이 없는 경우
• 사이클(cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우

그래프의 종류

• 무방향 그래프 - 간선을 통해 갈 수 있는 방향이 정해져 있지 않은 그래프 - 정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 표현
• 방향 그래프 - 하나의 간선을 통해 갈 수 있는 방향이 정해진 그래프 - A -> B로만 갈 수 있는 간선은 <A, B>로 표시 - 이때 A를 tail, B를 head라 함
• 완전 그래프: 그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프 - 무방향 완전 그래프의 정점 수가 n이면 간선의 수는 n * (n-1) / 2
• 가중치 그래프 - 간선에 비용이나 가중치가 할당된 그래프. 네트워크라고도 함
• 오일러 경로(Eulerian tour)
  • 그래프에 존재하는 모든 간선(edge)을 한 번만 통과하면서 처음 정점(vertex)으로 되돌아오는 경로를 말한다.
  • 그래프의 모든 정점에 연결된 간선의 개수가 짝수일 때만 오일러 경로가 존재한다.

    자바에서는 그래프를 인접 리스트 혹은 인접 행렬으로 표현할 수 있다.

인접 리스트, 인접 행렬

인접 리스트

• 모든 정점을 인접 리스트에 저장한다.

• 배열과 배열의 각 인덱스마다 존재하는 또 다른 리스트(배열, 리스트 등)을 이용해 인접 리스트를 표현할 수 있다.

• 특정 정점의 인접 노드를 찾기 편하다.
• 특정 정점과 연결된 간선 갯수를 파악하기 용이하다.
• 두 정점이 서로 연결되어 있는지 확인하기 위해 양쪽 노드의 리스트를 모두 탐색해야 한다.

class Graph { public Node[] nodes; }

class Node {
  public String name;
  public Node[] children;
}

인접 행렬

• N * N의 boolean 행렬(혹은 정수 행렬)로써 matrix[i][j] 가 true이면 i -> j로의 간선이 존재함을 의미한다.

• 특정 두 정점 사이 간선 존재 유무를 바로 확인할 수 있다.
• 각 간선의 가중치 파악이 용이하다.
• 그래프 내 간선 수를 계산하는 것이 힘들다.
• N개 노드 표현을 위해 N*N 만큼의 공간을 차지한다.
• 원하는 노드가 연결되어 있는지 확인하기 위해서는 모든 노드를 순회해야 한다.

if(간선 (i, j)가 그래프에 존재)
  matrix[i][j] = true;
else
  matrix[i][j] = false;

• 성능은 다음과 같은 양상을 보인다.

	인접 행렬	인접 리스트
저장 방식	2차원 배열	리스트(연결 리스트)
메모리 사용량	O($V^2$)	O($V+E$)
노드 추가/삭제	어려움	쉬움
두 노드 간 연결 확인	$O(1)$	노드의 차수에 비례하는 시간복잡도
모든 노드와의 연결 확인	$O(V)$	$O(E)$
예시 알고리즘	프림 알고리즘, 크루스칼 알고리즘	DFS, BFS

• 간선이 많을 경우 인접 행렬을 통해 연결 여부 확인
• 간선이 적을 경우 인접 리스트를 통해 인접 노드 확인