Tree 순회방법

Tree 순회방법 / Graph 알고리즘 §

들어가며 §

알고리즘에서 트리를 순회하는 알고리즘을 정리할 생각이다. 트리를 순회하는 방법은 크게 두 가지로 나뉜다. 첫째는 깊이우선탐색(DFS) 이고, 둘째는 넓이우선탐색(BFS)이다. 이 페이지의 모든 코드는 java로 짜여져 있다.

Node 정의 §

class Node {
	Node left;
	Node right;
	int data;
 
	public Node(int data) {
		this.data = data;
	}
}

깊이우선탐색(Depth First Search) §

사실 이게 더 간단한 편이다. 트리를 순회하는 데 있어서 깊이를 우선으로 순회하는 방법이다. preorder, inorder, postorder 의 세 가지 방법이 있다.

preorder §

자기 자신의 노드를 기준으로, 자기 노드를 먼저(pre) 탐색하는 방법이다.

public void preorder(Node head) {
	if(head == null) {
		return;
	}
	System.out.println(head.data);
	preorder(head.left);
	preorder(head.right);
}

이렇게 자기 자신의 노드를 먼저 탐색하고, 왼쪽/오른쪽 노드를 재귀적으로 순환한다.

inorder §

자기 자신의 노드를 기준으로, 자기 노드를 도중에(in) 탐색하는 방법이다.

public void inorder(Node head) {
	if(head == null) {
		return;
	}
	preorder(head.left);
	System.out.println(head.data);
	preorder(head.right);
}

postorder §

자기 자신의 노드를 기준으로, 자기 노드를 나중에(postorder) 탐색하는 방법이다.

public void inorder(Node head) {
	if(head == null) {
		return;
	}
	preorder(head.left);
	preorder(head.right);
	System.out.println(head.data);
}

넓이우선탐색(BFS) §

public void BFSSearch(Node head) {
	if(head == null) {
		return;
	}
 
	LinkedList<Node> queue = new LinkedList<Node>();
 
	queue.add(head);
 
	while(!queue.isEmpty()) {
		Node node = queue.remove();
		System.out.println(node.data);
 
		if(node.left != null) {
			queue.add(node.left);
		}
 
		if(node.right != null) {
			queue.add(node.right);
		}
	}
 
	return;
}

BFS는 큐를 사용한다. head가 입력으로 들어오면 head를 큐에 집어 넣고, 큐가 빌 때까지 연산을 수행한다.

1. 큐가 비지 않았다면 큐에서 데이터를 하나 dequeue한다.
2. 그 데이터를 출력한다.
3. 그 node의 children을 큐에 넣는다

이 알고리즘을 큐가 빌 때까지 수행하면 된다.

Graph 정의 §

그래프 알고리즘을 정리하기 전에 그래프의 용어를 정리할 필요가 있을 거 같다.

• vertex : 그래프에서 node를 가리키는 용어
• edge : 그래프에서 두 node를 연결하는 선을 가리키는 용어
• Directed Graph : 방향성이 있는 edge로 구성된 그래프
• Undirected Graph : 방향성이 없는 edge로 구성된 그래프 (그래프라 함은 일반적으로 undirected Graph를 말한다)
• Connected Graph : 모든 vertex가 다 연결되어 있는 그래프
• Weighted Graph : 가중치가 있는(weight) edge로 구성된 그래프
• Degree : Vertex에 연결된 edge 개수
  • 모든 vertex에 연결된 edge 개수의 총합 = 2 * edge 개수
• Indegree / Outdegree : Indegree 는 Directed graph에서 자신을 가리키는 edge의 개수 / Outdegree는 Directe graph에서 자신이 가리키는 edge 개수
• Forest : 0개 이상의 연결되지 않는 tree의 집합

Breadth-First Search §

class Vertex {
	int distence;
	boolean isVisited;
	Vertex preVertex;
	List<Vertex> abjacentVertex;
}
 
public void BFS(Vertex head) {
		if(head == null) return;
 
		LinkedList<Vertex> queue = new LinkedList<Vertex>();
 
		queue.add(head);
		head.isVisited = true;
 
		while(!queue.isEmpty()) {
			Vertex curVertex = queue.remove();
			for(Vertex abjacent : curVertex.abjacentVertex) {
				abjacent.distence = curVertex.distence + 1;
				abjacent.preVertex = curVertex;
 
				if(!abjacent.isVisited) {
					queue.add(abjacent);
					abjacent.isVisited = true;
				}
			}
		}
		return;
	}

BFS로 구한 head 부터 그래프의 임의의 점 v 까지의 경로는 head와 v까지의 최단경로이다. 단 이 알고리즘은 edge의 weight가 같다는 가정 하에만 사용할 수 있다. 만약 edge의 weight가 다르다면 다익스트라 알고리즘을 사용해야 한다.

Depth-First Search §

public void DFS(Vertex head) {
	if(head == null) return;
 
	head.isVisited = true;
 
	for(Vertex abjacent : curVertex.abjacentVertex) {
		if(!adjacent.isVisited) {
			DFS(head);
		}
	}
	return;
}

DFS는 재귀를 사용하면 BFS보다 간단하게 구현할 수 있다. 다만 이 코드는 Undirected 인 그래프에만 통용되며, 만약 그래프에 방향이 있다면 코드가 수정되어야 한다. 또한 얻어지는 해가 최단 경로가 된다는 보장이 없다.