그래프 - 그래프 표현

그래프의 표현

그래프를 표현하는 방법에는 여러 가지가 있다. 그래프의 크기가 어느 정도인지, 그리고 그래프를 어떻게 처리하는지에 따라 알맞은 자료 구조가 결정된다. 

 

인접 리스트

인접 리스트(Adgacency list) 표현법은 그래프의 각 노드 x에 대한 인접 리스트, 즉 x에서 출발하는 간선이 있는 노드의 리스트를 관리한다. 인접 리스트는 그래프를 나타내는 가장 대중적인 방법이다.

인접 리스트를 ArrayList를 이중으로 이용하여 구현할 수있다. 

import java.util.ArrayList;

public class GraphBasic {

	public static void main(String[] args) {
		  ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>();
		  
		  for(int i = 0 ; i < 5 ; i++) {
			  adj.add(new ArrayList<Integer>());
		  }
		  
		  adj.get(0).add(1);
		  adj.get(1).add(2);
		  adj.get(1).add(3);
		  adj.get(2).add(3);
		  adj.get(3).add(1);
		  
	}

}

다음과 같은 그래프를 나타낼 수 있다.

가중치를 추가하려면 C++에서는 pair를 사용하지만, java에서는 지원하지 않는 경우도 있어서 class를 만들었다.

public class Pair{
	int a;
	int b;
	public Pair(Integer a, Integer b) {
		this.a = a;
		this.b = b;
	}
	public int first() {
		return a;
	}
	public int second() {
		return b;
	}
	public int getA() {
		return a;
	}
	public void setA(int a) {
		this.a = a;
	}
	public int getB() {
		return b;
	}
	public void setB(int b) {
		this.b = b;
	}
	
}

Pair class를 이용하여 위의 코드를 수정하여 가중치를 추가할 수 있다.

 

import java.util.ArrayList;

import util.Pair;

public class GraphWeight {

	public static void main(String[] args) {
		  ArrayList<ArrayList<util.Pair>> adj = new ArrayList<ArrayList<util.Pair>>();
		  
		  for(int i = 0 ; i < 5 ; i++) {
			  adj.add(new ArrayList<util.Pair>());
		  }
		  
		  adj.get(0).add(new Pair(1, 5));
		  adj.get(1).add(new Pair(2, 7));
		  adj.get(1).add(new Pair(3, 6));
		  adj.get(2).add(new Pair(3, 5));
		  adj.get(3).add(new Pair(0, 2));
		  
	}

}

 

인접 행렬

인접 행렬(Adjacency martix)은 그래프에 포함된 간선을 나타내는 행렬이다.
인접 행렬에서는 두 노드 사이에 간선이 있는지 효율적으로 확인할 수 있다.

int adj[a][b]

노드 a에서 노드b로 향하는 간선이 있는지를 나타낸다. 간선이 있다면 1, 없다면 0이다.
여기서 1을 다른 숫자로 놓으면 가중치까지 표현할 수 있다.
하지만, 원소의 개수가 n^2개나 되고, 대부분이 0으로 채워진다는 점이 단점이다.

 

간선 리스트

간선 리스트(Edge list)는 그래프의 모든 간선을 특정한 순서에 따라 저장한 리스트이다. 

import java.util.ArrayList;

import util.Pair;

public class EdgeList {

	public static void main(String[] args) {
		ArrayList<util.Pair> edge = new ArrayList<util.Pair>();
		
		edge.add(new Pair(0, 1));
		edge.add(new Pair(1, 2));
		edge.add(new Pair(1, 3));
		edge.add(new Pair(2, 3));
		edge.add(new Pair(3, 0));
	}

}