[Data Structure] NonLinear - (3) Graph - 기본 개념

---

---

 그래프(Graph)

 그래프는 어떤 개념들 간의 연결관계를 표현하기 위해 사용하는 자료구조다. '개념들 간의 연결관계'라는 말이 모호하기 때문에 그 관계의 예를 몇 가지 들면, 사람과 사람 간의 관계, 도시와 도시와 연결된 도로들의 관계,  네트워크에서 A컴퓨터, B컴퓨터, C컴퓨터, ... 들 간의 관계 등이다.

 

 즉, 그래프 자료구조에서 주로 포커싱되는 대상은 관계이며, 현실세계나 추상적인 개념의 문제들을 그래프 구조로 맵핑시키고 난 뒤에는 그 관계들을 이용해 다양한 알고리즘을 적용해 문제들을 해결할 수 있다.

 

1) 기본 개념

 자료구조로서 그래프는, 위의 설명에서 개념에 대응하는 정점(Vertex; 노드(Node) - 컴퓨터 과학에서는 주로 노드를 씀)과 관계에 대응되는 간선(Edge)으로 이루어진다. 개념들 간의 관계를 정점과 간선만으로 추상화시켜 나타내므로 표현하고자 하는 관계에 따라 다양한 형태의 그래프로 그릴 수 있다.

 

다양한 형태의 그래프

 

 위의 그림처럼 방향의 유무나 가중치 유무 등에 따라 그래프의 형태가 달라질 수 있고, 그에 따라 맞는 알고리즘을 선택해 문제를 풀어나갈 수 있다.

 

2) 구현 방법

 프로그래밍에서 그래프를 구현하는 방법으로는 크게 인접 행렬(Adjacency Matrix)와 인접 리스트(Adjacency List)가 있다. 인접 행렬은 2차원 행렬을 사용해 노드 간의 연결 관계를 행렬로 나타내는 방법이다. 노드 간의 연결 여부를 행렬에 직접 기록하므로 인덱스를 통해 바로 확인할 수 있다는 장점이 있지만, 2차원 행렬 형태를 유지하기 위해서는 연결되어 있지 않은 노드들 간의 관계도 불가피하게 기록해야만 하므로 꼭 필요하지 않은 추가적인 메모리가 필요하다는 단점이 있다.

 

 인접 리스트는 동적 배열인 리스트를 이용해 각 정점과 연결된 모든 정점과의 관계를 저장하는 방법으로, 해당 정점에 연결된 필요한 간선들만 저장하면 되기 때문에 바로 접근할 수 있다는 장점이 있다. 하지만, 임의의 A 정점이 B정점과 연결되어 있는지를 확인하기 위해서 인접 행렬의 경우에는 인덱스를 통해 바로 접근해 확인할 수 있는 반면 인접 리스트에 경우에는 해당 리스트에 접근해 순회하며 연결 여부를 확인해야 한다는 단점이 있다.

 

 따라서 언제 인접 행렬을 써야 하고 언제 인접 리스트를 써야 하는지는 구현하고자 하는 알고리즘이나 표현하고자 하는 그래프의 속성에 따라 깊이 생각한 뒤 적절히 사용해야 한다.

 

✔ 인접 행렬 (Adjacency Matrix) 구현

public class AdjacencyMatrix {
	// 노드 개수는 10으로, 1 ~ 10까지 지정
	// 간선의 수는 12로, edgeData배열을 통해 표현되어 있음
	static int numberOfNodes = 10, numberOfEdges = 12;
	static int[][] edgeData = {
			{1, 3},
			{1, 4},
			{2, 3},
			{4, 6},
			{8, 10},
			{9, 3},
			{9, 10},
			{7, 2},
			{5, 3},
			{2, 6},
			{7, 1},
			{5, 2}
			};
	
	public static void main(String[] args) {
		// 노드의 번호가 1부터 시작하므로 노드의 수 numberOfNodes + 1을 통해 10까지 저장하도록 함
		boolean[][] edges = new boolean[numberOfNodes + 1][numberOfNodes + 1];
		
		// edgeData를 edges 배열에 반영
		for (int i = 0; i < numberOfEdges; i++) {
			int start = edgeData[i][0];
			int end = edgeData[i][1];
			
			// 양방향으로 연결된 그래프라면 양방향으로 연결해주어야 함
			edges[start][end] = true;
			edges[end][start] = true;
		}
		
		// 결과 출력
		for (int i = 1; i < numberOfNodes + 1; i++) {
			System.out.print(i + "번과 연결된 정점 : ");
			
			for (int j = 1; j < numberOfNodes + 1; j++) {
				if (i == j) continue;
				
				if (edges[i][j]) {
					System.out.print(j + "번 ");
				}
			}
			System.out.println();
		}
	}
}

1번과 연결된 정점 : 3번 4번 7번
2번과 연결된 정점 : 3번 5번 6번 7번
3번과 연결된 정점 : 1번 2번 5번 9번
4번과 연결된 정점 : 1번 6번
5번과 연결된 정점 : 2번 3번
6번과 연결된 정점 : 2번 4번
7번과 연결된 정점 : 1번 2번
8번과 연결된 정점 : 10번
9번과 연결된 정점 : 3번 10번
10번과 연결된 정점 : 8번 9번

 

 간단한 예제를 통해 일반적인 무방향 그래프를 만들었다. 이차원 배열의 각 인덱스를 정점의 번호로 표현하고 각각의 연결관계를 표현한 것만으로 추후 이 배열에 접근하는 것만으로 정점 간의 관계를 알 수 있다.

 

✔ 인접 리스트 (Adjacency List) 구현

package blog;

import java.util.ArrayList;
import java.util.List;

public class AdjacencyMatrix {
	// 노드 개수는 10으로, 1 ~ 10까지 지정
	// 간선의 수는 12로, edgeData배열을 통해 표현되어 있음
	static int numberOfNodes = 10, numberOfEdges = 12;
	static int[][] edgeData = {
			{1, 3},
			{1, 4},
			{2, 3},
			{4, 6},
			{8, 10},
			{9, 3},
			{9, 10},
			{7, 2},
			{5, 3},
			{2, 6},
			{7, 1},
			{5, 2}
			};
	
	public static void main(String[] args) {
		// 노드의 번호가 1부터 시작하므로 노드의 수 numberOfNodes + 1을 통해 10까지 저장하도록 함
		List<Integer>[] edges = new ArrayList[numberOfNodes + 1];
		
		for (int i = 1; i < numberOfNodes + 1; i++) {
			edges[i] = new ArrayList<>();
		}
		
		// edgeData를 edges 배열에 반영
		for (int i = 0; i < numberOfEdges; i++) {
			int start = edgeData[i][0];
			int end = edgeData[i][1];
			
			// 양방향으로 연결된 그래프라면 양방향으로 연결해주어야 함
			edges[start].add(end);
			edges[end].add(start);
		}
		
		// 결과 출력
		for (int i = 1; i < numberOfNodes + 1; i++) {
			System.out.print(i + "번과 연결된 정점 : ");
			
			for (int j = 1; j < numberOfNodes + 1; j++) {
				if (i == j) continue;
				
				if (edges[i].contains(j)) {
					System.out.print(j + "번 ");
				}
			}
			System.out.println();
		}
	}
}

1번과 연결된 정점 : 3번 4번 7번
2번과 연결된 정점 : 3번 5번 6번 7번
3번과 연결된 정점 : 1번 2번 5번 9번
4번과 연결된 정점 : 1번 6번
5번과 연결된 정점 : 2번 3번
6번과 연결된 정점 : 2번 4번
7번과 연결된 정점 : 1번 2번
8번과 연결된 정점 : 10번
9번과 연결된 정점 : 3번 10번
10번과 연결된 정점 : 8번 9번

 

 위의 인접 행렬 예제를 그대로 인접 리스트로 옮기면 위와 같다. 지금 예제는 1 ~ 10번까지 작은 수의 정점이 있지만, 100만 혹은 그 이상이 정점의 범위일 경우 간선은 드문드문 연결되어 있다면 이를 인접 행렬로 표현하기는 메모리 낭비가 심할 것이다. 이 때 위와 같은 인접 리스트가 도움이 될 수 있다.

 

✔ 암시적 그래프

대표적인 암시적 그래프 문제 '유기농 배추'

 

 제일 처음에 설명했듯 그래프는 정점과, 정점 간의 관계를 표현하는 간선만으로 추상화한 자료구조이므로, 관계가 암시적으로 나타나있다면 데이터를 가공해 흔한 그래프 구조로 만들지 않아도 해결할 수 있는 문제가 있다. 대표적으로 백준의 '유기농 배추' 문제가 있다. 배추가 심어진 땅(1) 사방으로 또 다른 배추 땅(1)이 있다면 이 배추 땅들은 서로 연결된 것이라고 보고 문제를 해결해 나갈 수 있다.

 

 이 때, 이 연결관계를 배추 땅(1) 상하좌우를 연결해 일반적인 그래프로 표현할 수도 있겠지만, 우리는 배추 땅(1) 상하좌우를 (x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)로 접근할 수 있다는 암시적인 룰을 알고 있기 때문에 굳이 간선으로 표현하지 않고도 문제를 해결할 수 있다. 이러한 그래프를 암시적 그래프라고 한다.

 

 

3) 차수 (Degree)

 그래프의 차수(Degree)는 입력 차수(Indegree)와 출력 차수(Outdegree)로 나뉘는데, 각각 해당 정점으로 들어오는 간선의 수와 정점에서 나가는 간선의 수를 의미한다. 무방향 그래프에서는 두 수가 같을 수 밖에 없기 때문에 고려해 줄 필요가 없지만, 간선의 방향이 한 정점에서 다른 정점으로 향하는 방향 그래프에서는 입력 차수와 출력 차수가 서로 달라질 수 있다.

 

 또 한 가지 주목해야 할 점은 어떤 그래프의 차수의 총합은 항상 '간선의 수 x 2'라는 것이다. 이는 생각해보면 당연한 말이다. 무방향 그래프나 방향 그래프나 한 간선이 A 정점에서는 출력 차수가 될 것이고 B 정점에서는 입력 차수가 되기 때문이다.