[Java]자료구조 - Graph

Graph(그래프)는 노드 사이의 연결 관계를 표현할 수 있는 자료구조이다.

 

앞서 보았던 트리구조 역시 사실은 그래프의 일종인데, 두 구조의 차이는 아래와 같다.

 

구분	그래프(Graph)	트리(Tree)
정의	객체 혹은 노드(Node)와 그것을 연결하는 간선(Edge)으로 모인 구조	그래프의 한 종류 방향성이 없으며 순환하지 않음
방향성	무방향 혹은 유방향으로 가능	단방향 그래프
순환성	순환 가능 자기 자신을 연결하는 간선(Self-Loop) 가능 순환(Cyclic), 비순환(Acyclic) 그래프 모두 가능	순환 불가능 자기 자신을 연결하는 간선(Self-Loop) 불가능 비순환 그래프(Acyclic Graph)
루트	루트의 개념이 있거나 없을 수 있음	하나의 루트 노드 존재
모델	네트워크 모델	계층 모델
순회	넓이 우선 탐색(BFS) 깊이 우선 탐색(DFS)	전위(Pre) / 중위(In) / 후위(Post) 순회 방식
간선 수	그래프에 따라 다르며 없을 수도 있음	n개의 노드(Node)라면 n-1개

그래프의 구조는 대략적으로 다음과 같다.

 

• 정점(Node) - 그래프 상의 하나의 점, Vertex
• 간선(Edge) - 정점 사이의 연결선
• 인접 정점(Adjacent Node) - 하나의 간선으로 바로 이어진 정점
• 정점 차수(Degree) - 하나의 정점에 연결된 간선의 개수
• 진출 차수(Out-Degree) - 방향이 있는 그래프에서 외부로 향하는 간선의 수
• 진입 차수(In-Degree) - 방향이 있는 그래프에서 내부로 향하는 간선의 수
• 사이클(Cycle) - 어느 경로가 정점 하나를 두 번 이상 거치도록 되어있는 경우 (ex. A-E-B-A)
• 자기 루프(Self Loof) - 진출하는 간선이 바로 자기 자신에게 진입하는 경우
• 무방향 그래프(Undirected Graph) - 간선에 방향이 존재하지 않는 그래프 ((A, B) = (B, A))
• 방향 그래프(Directed Graph) - 간선에 방향이 존재하는 그래프 (<A, B> ≠ <B, A>)

예를 들면 위 그림에서 A의 진출 차수는 1(A->C), 진입 차수는 2(B->A, C->A)이며

 

G1의 경우 무방향 그래프, G2의 경우 방향 그래프이다.

 

이 그래프 자료구조를 자바에 구현하는 방법은 크게 두 가지가 존재한다.

 

 

인접 행렬(Adjacency Matrix)

 

인접 행렬은 정점끼리의 인접관계를 나타내는 행렬이다.

 

정점의 수 n개의 경우 (n X n) 행렬을 만든 후

 

정점끼리 인접한 경우엔 1, 그렇지 않은 경우엔 0을 입력하는 식이다.

 

먼저 무방향 그래프의 경우 아래와 같이 표현된다.

 

무방향 그래프의 인접 행렬의 경우 대칭구조를 이루고 있는 것이 특징이다.

 

이어서 방향 그래프의 경우를 살펴보자.

 

n개의 정점을 가진 그래프의 경우 간선의 유무와 상관없이 n^2개의 메모리 공간이 필요함을 볼 수 있다.

 

이와 같이 인접 행렬은 가장 빠른 경로를 찾기엔 유리하지만 메모리 낭비를 걱정해야 한다.

 

 

인접 리스트(Adjacency List)

 

인접 리스트는 인접한 정점들 사이의 관계를 리스트의 형태로 표현한다.

 

각 정점별로 인접 정점을 정리한 후, 리스트로 정점들을 연결하는 방식이다.

 

n개의 정점을 가진 그래프의 경우 n개의 리스트가 필요하기 때문에 메모리를 효율적으로 사용할 수 있다.