1. 그래프(Graph)란?
그래프는 객체들이 쌍으로 연관되어 집합을 이루는 구조를 의미한다. 말이 어렵다면, 그래프 구조의 일종인 트리(Tree) 구조를 생각하면 된다.
트리(Tree) 구조 또한 노드(Node)들이 부모/자식 관계로 연결되어 있었다. 노드(Node)가 객체이며 그 관계를 연관성으로 하나의 전체 구조를 이루었다고 보면 된다. 트리(Tree) 처럼, 그래프 또한 내부적으로 부분 그래프(Sub Graphs)로 이루어진다.
그래프는 가장 기본적이고 유연한 구조로 관계를 나타낼 수 있다. 많은 문제들 중 그래프로 해결 가능한 문제가 50% 정도 된다고 이야기하는 엔지니어도 있다. (참고)
해결 가능한 문제들의 예시를 대충 알아보자. 어떠한 것들이 특히 해결이 가능할까?
ⓐ 네트워크 : 우리가 사용하는 컴퓨터는 인터넷으로 연결된다. 각 컴퓨터나 네트워크 장비를 정점(vertex , node)로 연결을 간선(edge)로 본다면 그래프로 표현이 가능하다.ⓑ 경로 찾기 : 특정 위치 간 가장 짧은 경로 / 긴 경로를 그래프를 이용해 찾을 수 있다. 구글 맵 또한 이러한 응용을 한 것이며, 게임 내 NPC 등의 모델도 이를 통해 움직임이 구현된다.(이외 GPS, High Frequency Trading 등에도 활용)ⓒ 순서 확인 : 특정 정점을 할 일이라고 본다면 그에 대한 연결을 통해 순서를 지정할 수 있다.(위상 정렬 예시)ⓓ 연결성 확인 : 전자 회로 내 특정 회로가 상호 연결되어 있는지 확인하는 경우 등에 사용
그래프와 트리의 차이는 아래와 같다.
트리 관련 포스팅은 여기를 참조
그래프의 구성 요소는 아래와 같다.
- 정점(Node, Vertex) - 객체, 위치의 개념
- 간선(Edge) - 정점 간의 관계, 연결선(Link, Branch)
- 인접 정점(Adjacent vertex) - 1개의 간선으로 직접 연결된 정점
- 정점 차수(Degree) - 하나의 정점에 인접해 있는 간선의 개수
- 진입 차수(In-Degree) - 방향성이 있는 그래프에서 외부에서 오는 간선의 수(내차수라고도 부른다)
- 진출 차수(Out-Degree) - 방향성이 있는 그래프에서 외부로 향하는 간선의 수(외차수라고도 부른다)
- 경로 길이(Path Length) - 정점에서 정점 간 경로 구성 시 사용된 간선의 수
- 단순 경로(Simple Path) - 구성된 경로 중에서 반복되는 정점이 없는 경우
- 사이클(Cycle) - 경로 중에서 시작 / 종료의 정점이 동일하여 내부적으로 순환이 발생하는 경우
그래프는 다양한 객체(혹은 노드)들의 연관성을 표현한 것이다. 그렇다면, 그 관계라고 함은 방향을 가질 수도 있고, 관계가 일방적인 것이 아닌 상호적인 것일 수 있으며, 어떠한 관계는 가중치를 가질 수도 있을 것이다. 이에 대한 예시를 아래와 같이 생각하여 보자.
① 무방향 그래프(Undirected Graph)
- 노드(Node) 혹은 객체가 상호 연결만 되어 있는 형태라고 볼 수 있다. 그 연결을 통해 상호 양방향으로 이동할 수 있다.
- 트리(Tree) 구조와 같이 부모 / 자식 노드(Node) 간에 상호 연결이 되어 있고 어느 방향으로든 서로를 참조할 수 있는 형태이다.
- A→B를 G(A, B) B→A를 G(B, A)라고 표현한다면 그 2가지는 동일하다고 보면 된다.
- 예시 : 양방향 도로 형태
- 아래의 그림과 같은 형태를 보면 각 노드들이 상호 연결되어 있으나 특정 방향성은 가지지 않는 것을 알 수 있다.
- 아래와 같은 무방향 그래프는 실제로는 A → B, B → A를 모두 표현하여 유방향 그래프 처럼 보고 문제를 해결한다.
무방향 그래프 예시
② 유방향 그래프(Directed Graph)
- 노드(Node) 혹은 객체가 연결되어 있으나 특정 방향으로만 이동할 수 있는 경우를 의미한다.
- 예를 들어, A→B로는 이동이 가능하지만 B→A로는 이동이 불가한 경우가 있을 수 있으며 이러한 형태를 표현 시 적합하다.
- 예시 : 일방통행 도로 형태
- 아래의 그림을 보면 하나의 노드에서 다른 노드로 방향성이 제시되어 있는 것을 확인할 수 있다.
유방향 그래프 예시
③ 가중치 그래프(Weighted Graph)
- 노드(Node) 혹은 객체의 연결에 가중치가 부여된 형태의 경우를 의미하며 '네트워크' 라고도 부른다.
- 단순 방향 그래프는 G(A, B) 및 G(B, C)가 1이라고 한다면 가중치 그래프는 G(A, B)와 G(B, C)가 다른 값을 가질 수 있다.
- 예를 들면, 노드(Node) 간 이동 시에 비용이 드는 경우를 생각해볼 수 있다.
- 가중치 그래프는 방향성을 갖거나 가지지 않을 수 있다.
- 예시 : 도시 간 이동 경로(경로에 따른 비용이 다름)
- 아래 그림을 보면 각각의 노드(Node) 끼리 연결된 내역에 가중치가 부여되어 있음을 알 수 있으며 각 경로의 비용이라고 본다면 가장 효율적인 비용으로 이동하는 방법을 계산해볼 수도 있다.
가중치 그래프 예시
④ 연결 그래프(Connected Graph)
- 무방향 그래프에 있는 모든 정점의 쌍에 대해서 항상 경로가 존재하는 경우를 의미한다.
- 트리(Tree) 구조 또한 그렇다고 볼 수 있다. 모든 정점들이 계층에 따라 연결되어 있다.
- 위의 그림들처럼 모든 노드(Node)에 대해 연결되지 않은 것이 없는 경우 모두를 포괄한다고 볼 수 있다.
⑤ 비연결 그래프(Disconnected Graph)
- 무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 경우
- 아래의 그림과 같이 1번 노드(Node)와 4번 노드(Node) 간에는 연결이 되어 있지 않다.
비연결 그래프
⑥ 순환 그래프(Cycle Graph)
- 정점 간의 단순 경로에서 시작 정점 / 종료 정점이 동일하여 경로에 순환이 발생할 수 있는 경우
- 단순 경로(Simple Path)는 경로 중 반복되는 정점이 없는 경우를 의미
- 아래의 그림과 같이 3→5→4→3 또는 3→2→3 또는 1→1(이 경우는 Loop 라고도 함) 과 같이 경로에 순환이 발생하는 경우를 의미한다.
- 이러한 경우, 코드로 처리 시, Cycle Detection(순환 감지) 기능을 넣어야 한다.
순환 그래프 예시
⑦ 비순환 그래프(Acyclic Graph)
- 순환이 발생하지 않는 그래프
- 별도의 그림 예시는 불필요할 것으로 보인다.
⑧ 완전 그래프(Complete Graph)
- 그래프에 속한 모든 정점들이 상호 연결된 그래프
- N개의 정점의 수가 있는 경우 간선의 수는 (n-1) * n / 2개가 된다.
완전 그래프 예시
참고1) 다중 간선(Multi Edge)A → B로 가는 경로가 2가지 이상인 경우를 의미하는데, 이런 경우는 흔하지 않다. 참고로만 알아두자. 다음 그림을 참조아래와 같이 빨간 경로가 있는 경우 다중 간선(Multi Edge)라고 부른다. 이 경우에는 두 간선은 서로 다른 간선이다.참고 2) 차수(Degree)위에서 설명하였지만 더욱 직관적으로 이해하기 위해 아래의 설명을 추가하였다.무방향 그래프에서는 단순히 차수(Degree)를 계산한다. 즉, 특정 정점에 연결된 간선의 개수를 차수라고 본다.아래의 그림에서 2번 정점은 연결된 간선이 3개 이므로 차수가 3이다.유방향 그래프에서는 내차수(In-Degree) / 외차수(Out-Degree)를 계산한다. 내차수는 현재 정점 방향으로 이어지는 간선의 개수이며, 외차수는 현재 정점에서 다른 정점 방향으로 이어지는 간선의 개수이다.즉, 아래의 그림에서 4번 노드는 내차수가 2이고 외차수가 1임을 알 수 있다.
2. 그래프(Graph) 구현하기
그래프를 구현하는 방법은 다양하겠지만 가장 기본적으로 이용되는 방법은 크게 2가지이다. 기본적으로 이 구조의 목적은 특정 정점 A와 연결된 간선을 효율적으로 찾기 위해 구현된다.
- 인접 리스트
- 인접 행렬
1) 인접 리스트
인접 리스트는 정점(혹은 노드)와 정점 간의 연결을 리스트 형태로 나타내는 것을 의미한다. 리스트 형태의 배열을 생성하고 각각의 위치(Index)에 리스트를 저장하여 정점 간의 연결성을 구현하는 방법이다.
간단하게 예를 들어서 바로 확인해보자. 아래 그래프를 리스트 형태로 구현해보자.
그래프 예시
1번 정점의 인접 정점 : 2, 42번 정점의 인접 정점 : 1, 3, 53번 정점의 인접 정점 : 24번 정점의 인접 정점 : 1, 55번 정점의 인접 정점 : 2, 4
리스트를 이용하여 구현한 그림은 아래와 같다.
인접 리스트 형태의 그래프
위의 그림은 연결리스트(LinkedList) 형태로 그림이 그려졌으나, 배열 기반의 리스트 형태로 구현하여도 문제는 없다. 아래의 소스코드를 통해 직접 구현하는 내역을 확인해보자.
package com.test;
import java.util.ArrayList;
public classAdjacencyList {
// Main 메소드로 실험
public static voidmain(String[] args){
int initSize = 5;
AdjacencyList adList = newAdjacencyList(initSize);
adList.put(1, 2, 1);
adList.put(1, 4, 1);
adList.put(2, 3, 1);
adList.put(2, 5, 1);
adList.put(4, 5, 1);
adList.printGraph(1);
}
// vertex 번호와 가중치를 저장하는 Node 클래스
private static classNode{
private int vertex;
private int weight;
publicNode(int vertex, int weight){
this.vertex = vertex;
this.weight = weight;
}
public intgetVertex(){
return this.vertex;
}
public intgetWeight(){
return this.weight;
}
}
// 아래부터 인접리스트 구현 내역
private ArrayList<ArrayList<Node>> adList;
private int size;
public AdjacencyList(int initSize){
this.adList = newArrayList<ArrayList<Node>>();
this.size = initSize;
for(int i=0; i < initSize+1; i++){
this.adList.add(newArrayList<Node>());
}
}
// 아래는 가중치 그래프를 기반으로 진행.// 만약 가중치가 없다면 weight를 단순히 1로 전달해도 된다.// 양방향 혹은 무방향 그래프인 경우 아래 활용
public voidput(int vertex_x, int vertex_y, int weight){
this.adList.get(vertex_x).add(newNode(vertex_y, weight));
this.adList.get(vertex_y).add(newNode(vertex_x, weight));
}
// 단방향 그래프인 경우 아래 활용
public voidputSingleDirect(int vertex_x, int vertex_y, int weight){
this.adList.get(vertex_x).add(newNode(vertex_y, weight));
}
// 전체 Graph 가져오기
public ArrayList<ArrayList<Node>>getGraph(){
return this.adList;
}
// 특정 vertex의 list 정보 가져오기
public ArrayList<Node>getVertex(int idx){
return this.adList.get(idx);
}
// 특정 vertex X와 vertex Y의 관계 반환
public intgetWeight(int vertex_x, int vertex_y){
return this.adList.get(vertex_x).get(vertex_y).getWeight();
}
// vertex가 0번 혹은 1번부터 시작할 수 있으니 startIdx를 가져온다.
public voidprintGraph(int startIdx){
StringBuilder sb = newStringBuilder();
for(int i=startIdx; i <= this.size; i++){
sb.append("정점 ").append(i).append("의 인접 정점 리스트");
for(int j=0; j < this.adList.get(i).size(); j++){
sb.append(" -> ").append(this.adList.get(i).get(j).getVertex());
}
sb.append("\n");
}
System.out.println(sb);
}
}
가중치가 있는 경우에는 위와 같이 (정점, 가중치)를 모두 저장할 수 있는 자료구조를 활용하면 된다. 없으면 가중치를 1로 저장해도 됨
코드를 천천히 보면 쉽게 이해할 수 있다. 해당 코드의 실행 결과는 아래와 같다.
인접 리스트 코드 실행 결과
참고로 위에서는 ArrayList안에 ArrayList를 넣는 방식으로 구현했는데 꼭 이렇게 해야 하는 것은 아니고 ArrayList 배열을 만들어도 동일하게 구현할 수 있다.(ArrayList[] 형태로 구현!)
다만, 주어지는 정점의 크기가 동적으로 변하더라도 안정적으로 저장할 수 있는 구조를 만들기 위해 위에서는 저렇게 생성했는데 보기에는 더 복잡해 보이는 듯 하다.
2) 인접 행렬
인접 행렬은 N * N 형태의 행렬(2차원 배열)을 통해 연결성이 있는 경우에는 0이 아닌 다른 숫자를 저장하여 연결성을 표현하는 방식이다.
간단하게 아래의 그림을 통해 인접 리스트에서 구현한 그래프를 표현해보자.
예를 들어서, 1번 정점(Vertex)는 2, 4번 정점(Vertex)와 연결성이 있기 때문에 M[1][2], M[1][4] 는 1로 표현한 것이다. 가중치 그래프라면 1이 아닌 다른 숫자를 저장하면 된다.
코드는 아래와 같다.
package graph;
public classAdjacencyArray<T> {
public static voidmain(String[] args){
int initSize = 5;
AdjacencyArray adArray = newAdjacencyArray(initSize);
adArray.put(1, 2, 1);
adArray.put(1, 4, 1);
adArray.put(2, 3, 1);
adArray.put(2, 5, 1);
adArray.put(4, 5, 1);
adArray.printGraph();
}
private int[][] adArray;
private int size;
publicAdjacencyArray(int size){
// 그래프 생성// 1번부터 정점이 시작될 수 있으니 +1 하여 생성함.this.adArray = newint[size+1][size+1];
this.size = size;
}
// 양방향 가중치 그래프를 가정하여 weight를 전달.// 만약 가중치가 없는 그래프라면 1로 전달한다.
public voidput(int vertex_y, int vertex_x, int weight){
this.adArray[vertex_y][vertex_x] = this.adArray[vertex_x][vertex_y] = weight;
}
// 단방향 그래프 정보 추가
public voidputSingle(int vertex_y, int vertex_x, int weight){
this.adArray[vertex_y][vertex_x] = weight;
}
// 전체 Graph 가져오기
public int[][] getGraph(){
return this.adArray;
}
// 특정 Vertex의 인접 Vertex 정보를 1차원 배열로 반환하기
public int[] getVertex(int idx){
return this.adArray[idx];
}
// 특정 vertex X와 vertex Y의 관계 반환
public intgetWeight(int vertex_y, int vertex_x){
return this.adArray[vertex_y][vertex_x];
}
public voidprintGraph(){
StringBuilder sb = newStringBuilder();
sb.append("인접 행렬을 구현한 2차원 배열 내역\n");
for(int i=0; i < this.adArray.length; i++){
for(int j=0; j < this.adArray[i].length; j++){
sb.append(this.adArray[i][j]).append(" ");
}
sb.append("\n");
}
System.out.println(sb);
}
}
이 코드는 단순히 2차원 배열을 생성하여 가중치 값을 저장하는 방식이므로 전혀 어렵지 않다. 출력한 결과는 아래와 같다.
인접 행렬 구현 결과
결과가 상단 표와 조금 다른 이유는 Index 0번 부터 출력했기 때문이다.
인접 리스트와 인접 행렬 구현의 차이점은 다음과 같다.
시간 복잡도는 어떠할까? 위에서 이러한 구조를 만드는 이유는 특정 정점과 연결된 간선을 빠르게 찾는 것이 목적이라고 하였다.
실제로 그래프 문제는 최단 경로 문제와 같이 현재 정점과 이어진 다른 정점을 찾아내는 연산이 가장 많이 수행된다.
그래서 시간 복잡도는 아래와 같다.
위의 2개의 표를 통해 인접 리스트가 시간 / 공간 복잡도가 더욱 우수한 것을 알 수 있다. 그래서 대부분의 경우에 그래프는 인접 리스트를 활용하여 구현되는 경우가 많다.
인접 행렬은 정점 A, 정점 B 간에 간선이 있는 지 여부를 판단 시에 많이 쓰고, 간선이 많은 경우에도 쓰는 경우가 있지만 대부분은 인접리스트를 활용하여 그래프 문제를 해결한다.
3) 간선 리스트
이는 간선 정보를 갖고 1차원의 배열을 만들어서 어떤 정점이 어느 정점으로 연결되는지를 나타내는 자료구조 방식이다.
많이 사용되는 방식은 아니고 라이브러리 사용이 금지되어 인접 리스트를 사용하기 어려울 때, 가끔씩 사용되는 방식이다. 거의 쓰지 않지만 알아두면 좋다.
아래 그림과 같이 i번째 정점과 연결된 간선의 수를 저장하는 방식이다. 미리 간선의 정점 간 연결 정보를 Pair 형태(배열 또는 리스트)로 저장해두고 그 개수를 판단하여 각 정점에서 연결된 간선의 수를 누적하여 저장한다.
그러면, 전체 간선 정보를 배열 또는 리스트로 저장했으니 index를 이용하여 몇 번 부터 몇 번 까지는 i번째 정점과 연결된 간선이라는 것을 알 수 있게 된다.
간선 리스트, 백준 강의 참조
위와 같이, 1번 정점과 연결된 간선은 2개인데 cnt라는 곳에는 해당 i번째 정점과 연결된 간선의 수를 나타내고 간선의 정보는 E라는 다른 배열에 Start - End Pair로 저장되어 있을 것이다.
따라서, 1번 정점에 연결된 간선은 cnt배열에서 2라고 저장되어 있으니 E배열의 0, 1번째가 되므로 그것을 통해 연결된 정점의 정보를 알아낼 수 있게 된다.2번 정점에 연결된 것은 cnt 배열에서 6이라고 되어 있으니 2~5번째 index의 E배열 정보가 된다. 이와 같이 확인 가능
그런데 자바의 경우에는 라이브러리를 쓸 수 없을 때 사용하고자 하면 구현이 쉽지 않다. 동적으로 늘어나는 형태의 자료구조가 라이브러리를 사용해야 하기 때문임.(간선의 개수는 최대 N^2개인데(복수 간선이 없다면) 그 상태로 cnt 배열을 구현해야 해서 공간 낭비가 있음)
따라서 그냥 ArrayList나 LinkedList를 직접 구현하여 해결하는 연습을 하는 것이 더 좋아보인다.
아래 코드를 통해 대략적인 개념을 이해해보자.
// start - end Pair의 Edge 정보를 저장하는 classclassEdge{
private int start;
private int end;
publicEdge(int start, int end){
this.start = start;
this.end = end;
}
public intgetStart() { return start; }
public voidsetStart(int start) { this.start = start; }
public intgetEnd() { return end; }
public voidsetEnd(int end) { this.end = end; }
}
public classMain{
static int n = 6;
static int cnt[];
public static voidmain(String[] args){
// 다른 언어와 다르게.. 동적으로 늘어나는 형태가 없어서 아래와 같이 만듦
Edge[] edges = newEdge[n*n];
// 입력으로 주어지는 정점 간 관계. 여기서는 그냥 직접 넣자.
edges[0] = newEdge(1, 2);
edges[1] = newEdge(1, 5);
edges[2] = newEdge(2, 1);
edges[3] = newEdge(2, 3);
edges[4] = newEdge(2, 4);
edges[5] = newEdge(2, 5);
edges[6] = newEdge(3, 2);
edges[7] = newEdge(3, 4);
edges[8] = newEdge(4, 2);
edges[9] = newEdge(4, 3);
edges[10] = newEdge(4, 5);
edges[11] = newEdge(4, 6);
edges[12] = newEdge(5, 1);
edges[13] = newEdge(5, 2);
edges[14] = newEdge(5, 4);
edges[15] = newEdge(6, 4);
cnt = newint[n+1];
// edge 개수를 찾아서 추가for(int i=0; i < edges.length; i++){
if(edges[i] == null) break;
cnt[edges[i].getStart()]++;
}
// index 값으로 변형되도록 이전 값에 ++for(int i=1; i < cnt.length; i++){
cnt[i] = cnt[i-1] + cnt[i];
}
for(int i=0; i < cnt.length; i++){
System.out.print(cnt[i]+", ");
}
}
}