5. 그래프 구현
그래프를 구현하는 방법은 다양하겠지만 가장 기본적으로 이용되는 방법은 인접리스트, 인접행렬 크게 2가지이다. 기본적으로 이 구조의 목적은 특정 정점 A와 연결된 간선을 효율적으로 찾기 위해 구현된다.
1. 인접리스트
인접 리스트는 정점(혹은 노드)와 정점 간의 연결을 리스트 형태로 나타내는 것을 의미한다. 리스트 형태의 배열을 생성하고 각각의 위치(Index)에 리스트를 저장하여 정점 간의 연결성을 구현하는 방법이다.
- 1번 정점의 인접 정점 : 2, 4
- 2번 정점의 인접 정점 : 1, 3, 5
- 3번 정점의 인접 정점 : 2
- 4번 정점의 인접 정점 : 1, 5
- 5번 정점의 인접 정점 : 2, 4
리스트를 이용하여 구현한 그림은 아래와 같다.
위의 그림은 연결리스트(LinkedList) 형태로 그림이 그려졌으나, 배열 기반의 리스트 형태로 구현하여도 문제는 없다. 아래의 소스코드를 통해 직접 구현하는 내역을 확인해보자.
package com.test;
import java.util.ArrayList;
public class AdjacencyList {
// Main 메소드로 실험
public static void main(String[] args){
int initSize = 5;
AdjacencyList adList = new AdjacencyList(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 class Node{
private int vertex;
private int weight;
public Node(int vertex, int weight){
this.vertex = vertex;
this.weight = weight;
}
public int getVertex(){
return this.vertex;
}
public int getWeight(){
return this.weight;
}
}
// 아래부터 인접리스트 구현 내역
private ArrayList<ArrayList<Node>> adList;
private int size;
public AdjacencyList(int initSize){
this.adList = new ArrayList<ArrayList<Node>>();
this.size = initSize;
for(int i=0; i < initSize+1; i++){
this.adList.add(new ArrayList<Node>());
}
}
// 아래는 가중치 그래프를 기반으로 진행.
// 만약 가중치가 없다면 weight를 단순히 1로 전달해도 된다.
// 양방향 혹은 무방향 그래프인 경우 아래 활용
public void put(int vertex_x, int vertex_y, int weight){
this.adList.get(vertex_x).add(new Node(vertex_y, weight));
this.adList.get(vertex_y).add(new Node(vertex_x, weight));
}
// 단방향 그래프인 경우 아래 활용
public void putSingleDirect(int vertex_x, int vertex_y, int weight){
this.adList.get(vertex_x).add(new Node(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 int getWeight(int vertex_x, int vertex_y){
return this.adList.get(vertex_x).get(vertex_y).getWeight();
}
// vertex가 0번 혹은 1번부터 시작할 수 있으니 startIdx를 가져온다.
public void printGraph(int startIdx){
StringBuilder sb = new StringBuilder();
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이 아닌 다른 숫자를 저장하여 연결성을 표현하는 방식이다.
간단하게 아래의 그림을 통해 인접 리스트에서 구현한 그래프를 표현해보자.
| Index | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 1 | 0 |
| 2 | 1 | 0 | 1 | 0 | 1 |
| 3 | 0 | 1 | 0 | 0 | 0 |
| 4 | 1 | 0 | 0 | 0 | 1 |
| 5 | 0 | 1 | 0 | 1 | 0 |
예를 들어서, 1번 정점(Vertex)는 2, 4번 정점(Vertex)와 연결성이 있기 때문에 M[1][2], M[1][4] 는 1로 표현한 것이다. 가중치 그래프라면 1이 아닌 다른 숫자를 저장하면 된다.
package graph;
public class AdjacencyArray<T> {
public static void main(String[] args){
int initSize = 5;
AdjacencyArray adArray = new AdjacencyArray(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;
public AdjacencyArray(int size){
// 그래프 생성
// 1번부터 정점이 시작될 수 있으니 +1 하여 생성함.
this.adArray = new int[size+1][size+1];
this.size = size;
}
// 양방향 가중치 그래프를 가정하여 weight를 전달.
// 만약 가중치가 없는 그래프라면 1로 전달한다.
public void put(int vertex_y, int vertex_x, int weight){
this.adArray[vertex_y][vertex_x] = this.adArray[vertex_x][vertex_y] = weight;
}
// 단방향 그래프 정보 추가
public void putSingle(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 int getWeight(int vertex_y, int vertex_x){
return this.adArray[vertex_y][vertex_x];
}
public void printGraph(){
StringBuilder sb = new StringBuilder();
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);
}
}출력한 결과는 아래와 같다.
결과가 상단 표와 조금 다른 이유는 Index 0번 부터 출력했기 때문이다.
6. 그래프 구현 - 인접리스트, 인접행렬 차이점
인접 리스트와 인접 행렬 구현의 차이점은 다음과 같다.
| 방식 | 특징 | 공간 복잡도 |
|---|---|---|
| 인접리스트 | 특정 정점을 접근하기 위해 리스트를 모두 확인해야 한다. | 각 정점의 List에 간선 수 만큼 저장하여 O(E) |
| 인접행렬 | 특정 정점의 연결에 대해 배열로 한 번에 접근 가능하다. | V개의 정점의 수만큼 2차원 배열을 만들기에 O(V^2) |
그래프는 특정 정점과 연결된 간선을 빠르게 찾는 것이 목적이다. 이에 따른 시간 복잡도는 아래와 같다.
| 방식 | 시간 복잡도 |
|---|---|
| 인접리스트 | 리스트에 각 정점에 연결된 간선의 개수 만큼 저장되므로 O(E) |
| 인접행렬 | 배열이 VxV형태가 되기 때문에 특정 정점의 0이 아닌 경우를 모두 찾아야 하기 때문에 O(V) |
위의 2개의 표를 통해 인접 리스트가 시간 / 공간 복잡도가 더욱 우수한 것을 알 수 있다. 그래서 대부분의 경우에 그래프는 인접 리스트를 활용하여 구현되는 경우가 많다.
인접 행렬은 정점 A, 정점 B 간에 간선이 있는 지 여부를 판단 시에 많이 쓰고, 간선이 많은 경우에도 쓰는 경우가 있지만 대부분은 인접리스트를 활용하여 그래프 문제를 해결한다.
