그래프(graph)
그래프의 정의
그래프는 연결되어 있는 원소 간 관계를 표현하는 자료구조이다.
실세계의 지하철 노선도, 컴퓨터 네트워크 등의 예를 생각하면 된다.
그래프의 구성 요소
그래프는 vertex(정점)과 정점들을 잇는 edge(간선)으로 구성된다.
위 사진에서 0,1,2,3,4가 정점에 해당하고, 정점을 잇는 선이 간선이다.
그래프 G가 있을 때,
G에 포함된 모든 정점들의 집합을 V(G), 모든 간선들의 집합을 E(G)라고 표기한다.
G = (V,E)라고 쓰기도 한다.
그래프의 종류
그래프는 무방향성 그래프와 방향성 그래프로 나뉜다.
무방향성 그래프
무방향성 그래프는 각 vertex가 서로 연결됐음만을 나타내는 그래프이다.
이 때 vertex 0과 1에 대해서 (0,1)과 (1,0)는 동일한 edge를 표현한다.
방향성 그래프
방향성 그래프는 edge에 방향성이 존재하는 그래프이다.
이제 <0,1>는 vertex 0에서 1로 가는 edge를 표현한다.
그래프 관련 용어
완전 그래프(complete graph)
Edge의 수가 최대인 그래프이다.
vertex의 수가 n개일 때,
완전 그래프 edge의 수 = n(n-1)/2
사이클(cycle)
처음과 마지막이 동일한 경로를 뜻한다.
연결(connected)
Vertex u와 v 사이에 경로가 존재할 경우, u와 v는 연결되었다고 표현한다.
위 그래프 G에서 0과 3은 연결되었지만, 0과 4는 연결되어있지 않다.
연결 요소(connected component)
위 그래프 G에는 2개의 연결 요소가 존재한다.
(0 1 2 3)과 (4 5 6)이 각각 연결 요소이다.
Vertex v의 차수(degree)
특정 vertex에 부속된 edge의 수를 차수로 표현한다.
방향성 그래프에서는 in-degree와 out-degree로 나누어 표현할 수 있다.
in-degree는 말 그대로 vertex를 향해 들어오는 edge를 의미하고, out-degree는 vertex에서 나가는 edge를 의미한다.
위 그래프에서 vertex 0의 in-degree는 3, out-degree는 1이다.
그래프 구현 방법
그래프는 리스트를 사용하거나, 배열을 사용하여 구현할 수 있다.
배열, 인접 행렬(Adjacency Matrix)
n개의 vertex를 갖는 그래프 G에 대해서 arr[n][n]의 인접 행렬을 만들어 사용한다.
0으로 초기화된 배열에, 만일 G에 (u,v)의 edge가 존재한다면 arr[u][v] = 1로 표현할 수 있다.
- 무방향성 그래프의 경우, [u][v]가 1이라면 [v,u] 또한 1이 된다. 따라서 대칭 행렬이 된다. 따라서 원한다면 n(n-1)/2 크기를 갖는 1차원 배열의 형태로도 구현이 가능하다.
- 방향성 그래프의 경우, 비대칭 행렬이 된다.
리스트, 인접 리스트(Adjacency List)
n개의 vertex를 갖는 그래프 G에 대해 그래프의 vertex마다 연결 리스트를 만들어 사용한다.
즉 n개 크기를 갖는 배열이 있으며, 각 요소는 해당 vertex의 연결 리스트이다.
각 연결 리스트는 해당 vertex와 연결된 vertex에 대한 정보를 담고 있다.
방향성 그래프의 경우, (0,1)의 edge가 있는 경우 0의 연결 리스트에 1의 정보가, 1의 연결리스트에 0의 정보가 담기게 된다.
무방향성 그래프의 경우, <0,1>의 edge가 있는 경우 0의 연결 리스트에 1의 정보가 담기게 된다. 즉, out-degree를 표현하게 되는 것이다.
역인접 리스트(Inverse Adjacency List)
무방향 그래프의 in-degree만을 표현하는 인접 리스트이다.
<0,1>의 edge가 존재하는 경우, 역인접 리스트에는 1의 연결 리스트에 0의 정보가 담기게 된다.
리스트를 이용한 그래프 구현
public interface Graph {
int size(); // vertex의 수
void addEdge(int v, int w); // v와 w를 연결하는 edge 추가
Iterable<Integer> adj(int v); // v에 연결된 정점들 순회
String toString(); // 전체 그래프 출력
}
모든 그래프를 구현할 때 쓰일 인터페이스이다.
package graph;
import java.util.LinkedList;
public class ListGraph implements Graph{
int size;
boolean directed;
LinkedList<Integer>[] adj; // 인접 리스트
LinkedList<Integer>[] inv; // 역인접 리스트
public ListGraph(int size, boolean directed) {
this.size = size; // vertex의 수
this.directed = directed; // true: 방향성 그래프, false: 무방향성 그래프
adj = new LinkedList[size];
inv = new LinkedList[size];
for(int i = 0; i < size; i++) {
adj[i] = new LinkedList<Integer>();
inv[i] = new LinkedList<Integer>();
}
}
@Override
public int size() {
return size;
}
@Override
public void addEdge(int v, int w) {
adj[v].add(w);
if(!directed) {
adj[w].add(v);
} else {
inv[w].add(v);
}
}
@Override
public Iterable<Integer> adj(int v) {
return adj[v];
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for(int i = 0; i< size; i++) {
sb.append(i).append(" -> ( ");
for(int k: adj[i])
sb.append(k).append(" ");
sb.append(")\n");
}
return sb.toString();
}
public int inDegree(int v) { // vertex v로 들어오는 edge의 수
if(v < 0 || v >= size) {
throw new IllegalArgumentException("잘못된 vertex 번호입니다.");
}
return inv[v].size();
}
public int outDegree(int v) { // vertex v에서 나가는 edge의 수
if(v < 0 || v >= size) {
throw new IllegalArgumentException("잘못된 vertex 번호입니다.");
}
return adj[v].size();
}
}
배열을 이용한 그래프 구현
package graph;
import java.util.ArrayList;
public class MatrixGraph implements Graph{
int size;
boolean directed;
int[][] adj; // 인접 행렬
public MatrixGraph(int size, boolean directed) {
this.size = size;
this.directed = directed;
adj = new int[size][size];
}
@Override
public int size() {
return size;
}
@Override
public void addEdge(int v, int w) {
adj[v][w] = 1;
if(!directed) {
adj[w][v] = 1;
}
}
@Override
public Iterable<Integer> adj(int v) {
// array를 Iterable한 자료구조로 바꿔서 리턴
ArrayList<Integer> L = new ArrayList<Integer>(size);
for(int i = 0; i < size; i++) {
if(adj[v][i]==1)
L.add(i);
}
return L;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for(int i = 0; i < size; i++) {
sb.append(i).append(" -> ( ");
for(int k = 0; k < size; k++) {
if(adj[i][k] == 1)
sb.append(k).append(" ");
}
sb.append(")\n");
}
return sb.toString();
}
public int inDegree(int v) {
int count = 0;
for(int i = 0; i < size; i++) {
count += adj[i][v];
}
return count;
}
public int outDegree(int v) {
int count = 0;
for(int i = 0; i < size; i++) {
count += adj[v][i];
}
return count;
}
}
테스트
위와 같은 그래프를 만들어보자.
public class GraphTestDriver {
public static void main(String[] args) {
MatrixGraph G = new MatrixGraph(4,true);
G.addEdge(0,1);
G.addEdge(0,3);
G.addEdge(1,2);
G.addEdge(1,3);
G.addEdge(3,2);
System.out.println(G);
for(int x: G.adj(0)) {
System.out.print(x+ " ");
}
System.out.println();
System.out.println("3의 out degree = "+G.outDegree(3));
System.out.println("3의 out degree = "+G.inDegree(3));
}
}
