4. 트리와 그래프 - 그래프편

▶ 그래프

트리는 그래프의 한 종류이다. 그렇다고 모든 그래프가 트리는 아니다. 트리는 사이클이 없는 하나의 연결 그래프이다. 그래프는 단순히 노드와 그 노드를 연결하는 간선을 하나로 모아 놓은 것과 같다.

- 그래프에는 방향성이 있을 수도 있고 없을 수도 있다. 방향성이 있는 간선은 일방통행, 방향성이 없는 간선은 양방향 통행 도로라고 생각하면 된다.

- 그래프는 여러 개의 고립된 부분 그래프로 구성될 수 있다. 모든 정점 쌍간에 경로가 존재하는 그래프는 연결 그래프라고 부른다.

- 그래프에는 사이클이 존재할 수도 있고 존재하지 않을 수도 있다. 사이클이 없는 그래프는 '비순환 그래프'라고 부른다.

인접 리스트

인접 리스트는 그래프를 표현할 때 사용되는 가장 일반적인 방법이다. 모든 정점을 인접 리스트에 저장한다. 무방향 그래프에서 *(a, b) 간선은 두 번 저장된다. 한 번은 a 정점에 인접한 간선을 저장하고 다른 한 번은 b에 인접한 간선을 저장한다. 그래프에서 노드를 정의하는 간단한 클래스는 트리의 노드 클래스와 궁극적으로 같아 보인다.

class Graph {
	public Node[] nodes;
}

class Node {
	public String name;
	public Node[] children;
}

트리에서는 특정 노드 하나에서 다른 모든 노드로 접근이 가능했었기 때문에 굳이 Tree 클래스를 따로 두지 않았다. 하지만 그래프는 트리와 달리 특정 노드에서 다른 모든 노드로 접근이 가능하지는 않아 Graph라는 클래스를 사용한다.

 

그래프를 표현하기 위한 추가적인 클래스를 따로 만들 필요는 없다. 배열과 배열의 각 인덱스마다 존재하는 또 다른 리스트를 이용하여 인접 리스트를 표현할 수 있다.

인접 행렬

인접 행렬은 NxN 불린 행렬로써 matrix[i][j]가 true라면 i에서 j로의 간선이 있다는 뜻이다. 0과 1을 이용한 정수 행렬을 사용할 수도 있다. 여기서 N은 노드의 개수를 뜻한다. 무방향 그래프를 인접 행렬로 표현한다면 이 행렬은 대칭행렬이 된다.

 

인접 리스트를 사용한 그래프 알고리즘들, 예를 들어 너비 우선 탐색 또한 인접 행렬에서도 사용 가능하다. 하지만 인접 행렬은 조금 효율성이 떨어진다. 인접 행렬에서는 어떤 노드에 인접한 노드를 찾기 위해서는 모든 노드를 전부 순회해야 알 수 있다.

그래프 탐색

그래프를 탐색하는 일반적인 방법 두 가지로는 깊이 우선 탐색, 너비 우선 탐색이 있다.

깊이 우선 탐색은 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법을 말한다. 즉, 넓게 탐색하기 전에 깊게 탐색한다는 뜻이다.

너비 우선 탐색은 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법을 말한다. 즉, 깊게 탐색하기 전에 넓게 탐색한다는 뜻이다.

너비 우선 탐색과 깊이 우선 탐색은 서로 다른 상황에서 사용되는 경향이 있고, DFS(깊이 우선 탐색)는 그래프애서 모든 노드를 방문하고자 할 때 더 선호되는 편이다. 하지만 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때는 BFS가 일반적으로 더 낫다. 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 뒤 Ash와 Vanessa사이에 존재하는 경로를 찾는 경우를 생각해 보면 왜 BFS가 더 나은지 쉽게 알 수 있다.

깊이 우선 탐색(DFS)

a 노드를 방문한 뒤 a와 인접한 노드들을 차례로 순회한다. a와 이웃한 노드 b를 방문했다면, a와 인접한 또 다른 노드를 방문하기 전에 b의 이웃 노드들을 전부 방문해야 한다. 즉, b의 분기를 전부 완벽하게 탐색한 뒤에야 a의 다른 이웃 노드를 방문할 수 있다. 전위 순회를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다. 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 감시해야 한다. 이를 검사하지 않을 경우 무한 루프에 빠질 위험이 있다.

void search(Node root) {
	if(root == null) return;
	visit(root);
	root.visited = true;
	for each(Node n in root.adjacent) {
		if(n.visited == false) {
			search(n);
		}
	}
}

너비 우선 탐색(BFS)

BFS는 직관적이지 않은 면이 있다. 이는 재귀적으로 동작하지 않으며, 큐를 사용한다. a 노드에서 시작한다고 했을 때, BFS는 a 노드의 이웃 노드를 모두 방문한 다음에 이웃의 이웃들을 방문한다. 즉, BFS는 a에서 시작해서 거리에 따라 단계별로 탐색한다고 볼 수 있다. 일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다.

void search(Node root) {
	Queue queue= new Queue();
	root.marked = true;
	queue.enqueue(root);
	while(!queue.isEmpty()) {
		Node r = queue.dequeue();
		visit(r);
		foreach(Node n in r.adjacent) {
			if(n.marked == false) {
				n.marked = true;
				queue.enqueue(n);
			}
		}
	}
}