10. Trees

10.1. Introduction to Trees

Tree는 Simple circuit이 존재하지 않는 Connected undirected graph이다.

팁

Example

그림 중 Tree인 Graph

• Solution
  $G_1, G_2$는 Simple circuit을 가지지 않은 Connected graph이므로 Tree이다.
  $G_3$의 경우 $e,b,a,d,e$인 Simple circuit을 가지므로 Tree가 아니고, $G_4$의 경우 $$Connected graph가 아니므로 Tree가 아니다.

정보

Theorem

Undirected graph가 두 Vertex 사이에 유일한 Simple path가 존재할 때만 Tree이다.

• Solution
  Connected simple graph이며 Circuit이 없으려면 어떠한 두 Vertex 사이에 Simple path는 단 하나만 존재할 수 있다.

Tree를 응용할 때 특정 Vertex를 Root로 지정한다.
Root를 지정할 경우 각 Edge에 Direction을 부여할 수 있다.

Rooted tree는 하나의 Vertex가 Root로 지정되고 모든 Edge가 Root에서 멀어지도록 Direction이 지정된 Tree이다.

$v$가 Rooted tree의 Root가 아닌 Vertex라면 $v$의 Parent $u$는 $v$가 Root로의 Path를 생성할 때 $u$에서 $v$로의 Directed edge를 가진 유일한 Vertex이며 반대의 관계를 Child라고 한다.
같은 Parent를 둔 여러 Vertex들의 관계는 Sibling이라고 한다.
Root가 아닌 Vertex의 Ancestor는 Root에서 해당 Vertex까지의 Path에 있는 Vertex들로 Root를 포함하며 해당 Vertex는 제외한다.
반대의 관계를 Descendant라고 한다.

Tree에서 Child가 없을 경우 Leaf라고 부르며 Root가 유일한 Vertex일 경우 Leaf, 그렇지 않을 경우 Internal vertex라고 불린다.
만약 $a$가 Tree의 Vertex라면 $a$를 Root로 삼는 Subtree는 $a$와 그 Descendant들에 Adjacent인 모든 Edge로 이루어진 Tree의 Subgraph가 된다.

Internal vertex가 $m$보다 많은 Children을 가지지 않을 때 $m$-ary tree라 하고 Full $m$-ary tree의 경우 모든 Internal vertex가 $m$만큼의 Children을 가질 때이다.
$m=2$일 때 Binary tree라고 부른다.

팁

Example

그림의 각 Graph가 Full $m$-ary tree인 지 확인

• Solution
  $T_1$의 경우 Full binary tree, $T_2$의 경우 Full 3-ary tree, $T_3$의 경우 Full 5-ary tree, $T_4$의 경우 Full $m$-ary의 Tree가 아니며 Children 수가 $2, 3$ 중 하나이므로 3-ary tree이다.

Ordered rooted tree의 경우 Children들이 왼쪽에서 오른쪽으로 표시되도록 그려지며 Binary tree에서 첫 번째 Child를 Left child, 두 번째 Child를 Right child라고 부른다.
Child를 Root 삼은 Subtree 중 Left child가 Root가 된 Subtree를 Left subtree, 반대를 Right subtree라 부른다.

팁

Example

그림의 $(a)$에 표시된 Binary tree의 $(b), (c)$의 관계

• Solution
  $(b)$는 $c$의 Left subtree, $(c)$는 $c$의 Right subtree이다.

Trees as Models

Tree를 Model로 삼는 다양한 예시가 존재한다.

팁

Simple Example

• Saturated Hydrocarbons and Trees\
• Representing Organizations\
• Computer File Systems\

Properties of Trees

정보

Theorem

$n$개의 Vertex가 있는 Tree는 $n-1$개의 Edge를 가진다.

• Proof
  간단히 Mathematical induction을 사용하여 증명 가능하다.
  Tree의 Vertex가 1개일 때 Edge는 0을 Basis step으로 삼고
  모든 Vertex가 $n-1$개인 Tree의 Edge 수가 $n-2$개 일 때 어느 Vertex에 Child로 추가하여도 Edge는 단 1개만 증가하므로 증명 가능하다.

정보

Theorem

Full $m$-ary tree의 Internal vertex의 수가 $i$일 때 Vertex 수 $n=mi+1$

정보

Theorem

Full $m$-ary tree는

1. $n$개의 Vertex가 있는 경우 Internal vertex 수 $i=(n-1)/m$이며 Leaf의 수 $l=[(m-1)n+1]/m$이다.
2. $i$개의 Internal vertex가 있는 경우 $n=mi+1$개의 Vertex와 $l=(m-1)i+1$개의 Leaf가 존재한다.
3. $l$개의 Leaf가 존재하는 경우 $n=(ml-1)/(m-1)$개의 Vertex와 $i=(l-1)/(m-1)$개의 Internal vertex가 존재한다.

Blanced rooted tree를 사용할 경우 각 Vertex의 Subtree가 대략 같은 길이의 Path를 포함하도록 하기 위함이다.
Rooted tree에서 Vertex $v$의 Level은 Root에서 해당 Vertex까지의 유일한 Path의 길이이다.
Root의 Level은 0이다.
Rooted tree의 Height는 Vertex들의 Level 중 Maximum value이다.

팁

Example

각 Vertex의 Level

• Solution
  Root $a= 0$
  $b,j,k=1$
  $c,e,f,l=2$
  $d,g,i,m,n=3$
  $h=4$
  Height가 4인 Rooted tree이다.

Height $h$의 Rooted $m$-ary tree는 모든 Leaf가 Level $h$, $h-1$에 있을 때 Balanced라고 할 수 있다.

팁

Example

위 Rooted tree들이 Balanced인 지

• Solution
  $T_1, T_3$는 Balanced이다. 각각 3-4, 3에 Leaf가 존재하기 때문이다.
  $T_2$는
  Not balanced이며 Leaf들의 Level이 2,3,4이기 때문이다.

정보

Theorem

Height가 $h$인 $m$-ary tree는 최대 $m^h$개의 Leaf들을 가질 수 있다.

• Proof
  Full balanced $m$-ary tree의 경우 $h$Level $lv$에 따라 최대 $m^{ lv}$개의 Vertex를 추가할 수 있으므로 최대 $m^h$개의 Leaf들을 가질 수 있게 된다.

정보

Corollary

Height가 $h$인 $m$-ary tree에 Leaf가 $l$개 존재한다면 $h\geq \lceil \log_m l\rceil$이며, $m$-ary tree가 Full and balanced이면 $h=\lceil \log_ml\rceil$이다.

• Proof
  앞전 Theorem의 역치로 증명할 수 있다.

10.2. Applications of Trees

Binary Search Trees

정보

Pseudocode

Algorithm Locating and Adding Items to a Binary Search Tree

procedure $insertion$($T$: binary search tree, $x$: item)
$v$ := root of $T${a vertex not present in $T$ has the value $null$}
while $v\not= null$ and $label(v)\not= x$
begin
if $x<label(v)$ then
if left chilid of $v\not= null$ then $v$ := left child of $v$
else add $new\ vertex$ as a right child of $v$ to $T$ and set $v$ := $null$
else
if right child of $v\not= null$ then $v$ := right child of $v$
else add $new\ vertex$ as a right child of $v$ to $T$ and set $v$ := $null$
end
if root of $T=null$ then add a vertex $v$ to the tree and label it with $x$
else if $v$ is $null$ or $label(v)\not = x$ then label $new\ vertex$ with $x$ and let $v$ be this new vertex {$v$= location of $x$}

Decision Trees

Rooted tree는 일련의 Decision을 통해 Solution에 도달하는 Problem을 모델링 하는 데 사용될 수 있다.
예시로 위에서 다룬 Binary search tree의 경우 일련의 비교를 기반으로 원하는 Item을 찾는 데 사용할 수 있으며, 각 비교는 Item을 찾았는 지, Subtree에서 오른쪽 또는 왼쪽으로 가야하는 지를 알 수 있다.
각 Interior vertex가 Dicision에 해당하고 이 Vertex에서 각 가능한 Dicision Result에 대한 Subtree가 있는 Rooted tree를 Decision tree라고 한다.

팁

Example

List $a, b, c$ 를 정렬하는 Decision tree

정보

Theorem

Binary comparison에 기반한 Sorting algorithm은 최소한 $\lceil \log n!\rceil$의 Comparison이 필요하다.

정보

Corollary

Binary comparison에 기반한 Sorting algorithm이 $n$개의 Element를 정렬하는 데 사용하는 Comparison 횟수는 $\Theta(n \log n)$이다.

정보

Theorem

Binary comparison에 가반한 Sorting algorithm이 $n$개의 Element를 정렬하는 데 사용하는 Comparison의 평균은 $\Omega(n \log n)$이다.

Prefix Codes

Bit string을 이용하여 Alphabet 글자를 Incoding하는 방법을 고려할 때 총 26개의 글자가 존재하기에 최소 5 Bit string으로 표현해야 하나 이보다 더 효율적인 방법이 있는 지 고려해볼 수 있다.
이 때 가변 길이 Bit string을 쓴다면 자주 발생하는 글자는 짧은 Bit string으로, 드물게 발생하는 글자는 비교적 더 긴 Bit string으로 Incoding할 수 있다.
예시로 e, a, t를 각각 0, 1, 01로 Incoding 할 수 있으며 이 때 Bit string 0101은 eat, tea, eaea, tt 등으로 해당할 수 있다.

위 예시와 같이 하나의 Bit string이 여러 글자 Sequence에 해당하지 않도록 보장하여야 사용 가능한데, 이 때 하나의 글자를 Incoding할 때 한 글자의 Bit string이 다른 글자의 Bit string의 첫 부분으로 나타나지 않게 하는 것이다.
이를 Prefix code라고 한다.
e, a, t를 0, 10, 11로 각각 Incoding 하였을 때 Bit string 10110은 ate만이 될 수 있다.

Prefix code는 Binary tree를 사용하여 표현할 수 있으며 이 Tree의 Leaf에 글자가 Label로 달려 있다.
Tree의 Edge는 Left child로 갈 때 0, Right child로 갈 때 1을 할당해 Label을 붙인다.
특정 Bit string을 Incoding하는 Bit string은 root에서 해당 글자가 Label로 붙은 Leaf까지의 고유한 Path에서 Edge의 Label로 구성된 Sequence이다.

Huffman Coding은 Symbol의 빈도를 Input으로 받아 가능한 적은 Bit를 사용하여 String을 Incoding하는 Prefix를 출력하는 Algorithm이다.
Huffman coding은 Data compression의 Fundamental algorithm이다.

간단히 요약하여 Huffman coding은 Rooted tree의 Root에서 Leaf까지의 Path가 유일하게 Item을 구분 할 수 있게 해줌을 이용하여, 사용 빈도가 높은 Item을 짧은 Path에, 그렇지 않은 Item을 비교적 긴 Path에 놓아 효율을 중시한 기법이다.

정보

Pseudocode

Algorithm Huffman Coding

procedure $Huffman$($C$: symbol $a_i$ with frequencies $w_i$, $i=1,\dots,n$)
$F$ := forest of $n$ rooted trees, each consisting of the single vertex $a_i$ and assigned weight $w_i$
while $F$ is not a tree
begin
Replace the rooted trees $T$ and $T'$ of least weights from $F$ with $w(T)\geq w(T')$ with a tree having a new root that has $T$ as its left subtree and $T'$ as its right subtree. Label the new edge to $T$ with 0 and the new edge to $T'$ with 1. Assign $w(T)+w(T')$ as the weight of the new tree
end
{the Huffman coding for the symbol $a_i$ is the concatenation of the labels of the edges in the unique path from the root to the vertex $a_i$}

팁

Example

Huffman coding을 사용하여 다음 Symbol을 주어진 Frequency로 Incoding
A: 0.08, B: 0.10, C: 0.12, D: 0.15, E: 0.20, F: 0.35

• Solution
  
  위 과정에 의해 A=111, B=110, C=011, D=010, E=10, F=00으로 Incoding하였다.

Game Trees

Game tree는 Tic-tac-toe, Nim, Checker, Chess와 같이 Player들이 번갈아 가며 각 상황의 수(우연 요소 없이)를 두는 것을 의미한다.

Game tree의 Vertex의 Value는 Recursive하게 Define할 수 있다.

1. Leaf의 Value는 Game이 이 Leaf로 나타내는 위치에서 종료될 때 첫 번째 Player에게 지급되는 보상이다.
2. 짝수 Level의 Interior vertex의 Value는 Children 중 Maximum이며 홀수 Level의 Interior vertex의 Value는 Children 중 Minimum이다.

정보

Theorem

Game tree의 Vertex의 Value는 두 Player가 Minmax strategy를 따르고 이 Vertex로 부터 Player가 시작될 때 첫 번째 Player에게 지급되는 보상이다.

• Proof
  Induction을 사용하여 Theorem의 증명과 추가 설명을 할 수 있다.
  Basis step: 만약 Vertex가 Leaf인 경우 Theorem에 따라 이 Vertex에 할당된 가치는 첫 번째 Player에게 지급되는 보상이다.
  Inductive step: Vertex의 Children의 Value가 각 Vertex가 나타내는 위치에서 Play가 시작될 때 첫 번째 Player에게 지급되는 보상이다.
  즉 이 때 두 가지 상황이 발생하는데, 첫 번째 Player냐 두 번째 Player냐의 상황이다.
  첫 번째 Player의 상황에는 각 Vertex에서 Maximum value를 선택하는 것이 첫 번째 Player에게 유리한 상황이 되고, 두 번째 Player의 상황에는 각 Vertex에서 Minimum value를 선택하여 첫 번째 Player의 이득을 줄이는 것이 이득이 된다.

10.3. Tree Traversal

Universal Address Systems

Ordered rooted tree의 모든 Vertex를 순회하는 Procedure는 Children의 Ordering에 의존한다.
Ordered rooted tree의 Interior vertex의 Children들이 이 Digraph를 나타내는 도면에서 왼쪽에서 오른쪽으로 표시된다.

1. Root에 Integer 0을 붙인다.
   그 다음 첫 번째 Level의 $k$ 자식들에게 $1,\dots,k$ 순으로 왼쪽에서 오른쪽으로 Label을 붙인다.
2. Level $n$에 있는 Vertex $v$와 Label $A$에 대해 왼쪽에서 오른쪽으로 그려진 $k_v$ Children들을 $A.1, A.2,\dots,A.k_v$로 Label을 붙인다.

위 Procedure에 따르면 Level $n$에 있는 Vertex $v$는 고유한 $x_1.x_2.\cdots.x_n$으로 Label이 있으며 Root에서 $v$로 가는 고유한 Path는 Level 1의 $x_1$번째 Vertex, Level 2의 $x_2$번째 Vertex등을 지난다.
이를 Universal Address System이라 하며 Lexicographic ordreing을 사용하여 총 Vertex를 Ordering할 수 있다.

Traversal Algorithm

Ordered rooted tree의 모든 Vertex를 방문하는 Procedure를 Traversal algorithm이라 한다.
일반적으로 Preorder(전위), Inorder(중위), postorder(후위) traversal이 존재한다.

$T$를 Root $r$을 가진 Ordered rooted tree라고 할 때 $T$가 $r$만으로 구성되어 있다면 $r$이 $T$의 Preorder traversal이다.
그렇지 않다면 $r$에서 왼쪽에서 오른쪽으로 $T_1, T_2,\dots, T_n$의 Subtree가 있다고 가정할 시 Preorder traversal은 $r$ 방문 후 $T_1, T_2, \dots, T_n$ 순서대로 방문한다.

팁

Example

위 Ordered rooted tree $T$를 Preorder traversal했을 경우 Vertex 방문 순서

• Solution
  $a, b, e, j, k, n, o, p, f, c, d, g, l, m, h, i$ 순서이다.

$T$를 Root $r$을 가진 Ordered rooted tree라고 할 때 $T$가 $r$로만 구성되어 있다면, $r$은 $T$의 Inorder traversal이다.
그렇지 않다면 $r$에서 왼쪽에서 오른쪽으로 $T_1, T_2,\dots, T_n$의 Subtree가 있다고 가정할 시 Inorder traversal은 $T_1$을 Inorder traversal한 후 $r$ 방문하고 그 이후 $T_2, T_3,\dots,T_n$을 Inorder traversal하는 방식으로 진행된다.

팁

Example

위 Ordered rooted tree $T$를 Inorder traversal했을 경우 Vertex 방문 순서

• Solution
  $j,e,n,k,o,p,b,f,a,c,l,g,m,d,h,i$ 순서이다.

$T$를 Root $r$을 가진 Ordered rooted tree라고 할 때 $T$가 $r$로만 구성되어 있다면, $r$은 $T$의 Postorder traversal이다.
그렇지 않다면 $r$에서 왼쪽에서 오른쪽으로 $T_1,T_2,\dots,T_n$의 Subtree가 있다고 가정할 시 Postorder traversal은 $T_1,T_2,\dots,T_n$까지 Postorder traversal한 후 $r$을 방문하는 방식으로 진행된다.

팁

Example

위 Ordered rooted tree $T$를 Postorder traversal했을 경우 Vertex 방문 순서

• Solution
  $j,n,o,p,k,e,f,b,c,l,m,g,h,i,d,a$ 순서이다.

Infix, Prefix and Postfix Notation

Expression(Compound propositions, Combinations of sets, Arithmetic expressions)들을 Ordered rooted tree를 사용하여 표현할 수 있다.

팁

Example

$((x+y)\uparrow 2)+((x-y)/3)$을 Ordered rooted tree로 표현

• Solution
  $x+y$의 Expression을 먼저 Subtree로 만들고 $((x+y)\uparrow 2)$의 Subtree로 통합하여 더 큰 Subtree를 반복하여 만든다.\

Binary tree를 나타내는 Inorder traversal을 수행하면 원래의 Expression과 Element, Operator가 순서대로 생성된다.
Operator를 만날 때 마다 Inorder traversal에 괄호를 포함하여 얻어진 Fully parenthesized expression을 Infix form이라고 한다.

Expression의 Rooted tree를 Preorder traversal로 탐색할 때 Expression의 Prefix form이라고 하며 Polish notation이라고도 한다.

Expression의 Rooted tree를 Postorder traversal로 탐색할 때 Expression의 Postfix form이라고 하며 Reverse polish notation이라고도 한다.

Prefix, Postfix form은 괄호를 필요로 하지 않는다.

팁

Example

Prefix form $+\ -\ \cdot\ 2\ 3\ 5\ /\ \uparrow\ 2\ 3\ 4$의 값

• Solution
  Prefix이기에 뒤에서 부터 Operator를 만나면 연산하는 방식으로 해결 가능하다.
  먼저 $\uparrow$를 만났을 때 $2^3$으로 8, $/$를 만나 $8/4$로 2이다.
  이 때 식은 $+\ -\ \cdot\ 2\ 3\ 5\ 2$가 되어 다시 Operator $\cdot$를 만나 $2\cdot 3=6$, $6-5=1$, $1+2=3$으로 정답은 3이다.

팁

Example

Postfix form $7\ 2\ 3\ \cdot\ -\ 4\ \uparrow\ 9\ 3\ /\ +$의 값

• Solution
  Postfix이기에 앞에서 부터 Operator를 만나면 앞 전 두 수를 연산하는 방식이다.
  먼저 $\cdot$을 만나 $2\cdot 3=6$, $7-6=1$, $1^4=1$, $9/3=3$, $1+3=4$로 정답은 4이다.

10.4. Spanning Trees

$G$를 간단한 Graph라고 하면 $G$의 Spanning tree(신장 트리)는 $G$의 모든 Vertex들을 포함하는 Tree형태의 Subgraph이다.

정보

Theorem

Simple graph가 Spanning tree를 가진다면 Connected라고 한다.

Depth-First Search

Connected simple graph에 대해 DFS(Depth-First Search)를 사용하여 Spanning tree를 구성할 수 있다.
Spanning tree는 Rooted tree의 Underlying undirected graph가 된다.
Graph의 Vertex 중 하나를 임의의 Root로 설정하면 이 Vertex에서 시작하여 점차적으로 Vertex와 Edge를 추가하여 Path를 형성한다.
각 새로운 Edge는 Path의 마지막 Vertex와 아직 Path에 포함되지 않은 Vertex와 Connect된다.
Path를 가능한 한 오래 유지하며 Vertex와 Edge를 계속 추가해 Path가 Graph의 모든 Vertex를 통과할 경우 이 Path로 구성된 Tree가 Spanning tree가 된다.
Path가 모든 Vertex를 통과하지 못했다면 더 많은 Vertex와 Edge를 추가해야 한다.
Path의 마지막에서 두 번째 Vertex로 돌아가 방문 하지 않은 Vertex를 통과하는 것으로 새로운 Path를 만드는 데 이 작업이 불가능 할 때 다시 두 Vertex 뒤로 이동해 다시 시도하게 된다.

위 Procedure를 반복하여 마지막으로 방문한 Vertex에서 시작해 Path를 따라 한 Vertex씩 뒤로 이동하고 가능한 긴 새로운 Path를 형성해 더 이상 Edge를 추가할 수 없을 때 까지 진행한다.
Graph는 Finite edge를 가지고 있으며 Connect되어 있기에 이 과정은 Spanning tree를 생성하는 것이다.
Algorithm의 Step에서 PAth가 끝나는 각 Vertex는 Rooted tree에서 Leaf가 되며 이 Vertex에서 시작하는 Path가 구성되는 각 Vertex는 Interior vertex가 된다.

Graph의 DFS에 의해 선택된 Edge를 Tree edge라고 한다.
Graph의 다른 모든 Edge는 이 Vertex의 Ancestor나 Descendant과 Vertex를 Connect해야 한다.
이러한 Edge를 Back edge라고 한다.

팁

Example

위 Graph에서 Bold line이 Tree edge이고, Thinner edge $(e,f), (f,h)$는 Back edge이다.

정보

Pseudocode

Algorithm Depth-First Search

procedure $DFS$($G$: connected graph with vertices $v_1, v_2,\dots,v_n$)
$T$ := tree consisting only of the vertex $v_1$
$visit(v_1)$
procedure $visit$($v$: vertex of $G$)
for each vertex $w$ adjacent to $v$ and not yet in $T$
begin
add vertex $w$ adjacent to $v$ and not yet in $T$
$visit(w)$
end

DFS algorithm의 Computational complexity는 각 Vertex $v$에 대해 $visit(v)$ Procedure가 Search 중 Vertex $v$를 처음 만날 때 호출되며 다시 호출되지 않는다는 것과 $G$의 Adjacent list가 제공될 때 $v$에 Adjacent list를 찾기 위해 추가적인 Operation이 필요하지 않음을 고려하여 Edge가 Tree에 추가할 지 결정하기 위해 각 Edge를 최대 2번 검사하므로 $G$의 Edge 수 $e$와 Vertex 수 $n$에 대해 $O(e)$나 $O(n^2)$ Step으로 Spanning tree를 구성한다.

DFS의 경우 Graph에서 Path와 Circuit을 찾거나 Graph의 Connect element를 결정하거나 Graph의 Cut vertex를 찾는 데 활용될 수 있다.

Breadth-First Search

Simple graph의 Spanning tree를 만들기 위해 BFS(Breadth-First Search)를 사용할 수 있다.
Rooted tree를 구성해 이 Root가 있는 Tree의 Underlying undirected graph가 Spanning tree를 형성한다.
Graph의 Vertex 중 임의로 Root를 선택해 이 Vertex에 가능한Adjacent edge를 모두 추가한다.
이 Step에서 새로 추가된 Vertex들은 Spanning tree에서 Level 1인 Vertex들이 되고 임의로 정렬해 Level 1의 Vertex들은 순차적으로 방문해 이 Vertex에 Simple circuit이 생성되지 않게 Adjecent edge를 추가한다.
위 Procedure를 반복하여 Graph의 Finite edge로 종료가 되면 모든 Vertex를 포함하는 Tree를 생성했기에 이 Tree는 Spanning tree가 된다.

팁

Example

위 Graph의 Spanning tree를 찾기 위해 BFS 사용

• Solution
  BFS의 시작으로 Vertex $e$를 Root로 두고 $e$의 Adjacent vertex들의 모든 Edge를 추가하여 Spanning tree의 Level 1 vertex인 $b,d,j,i$를 추가한다.
  위 과정을 Level 1 vertex에게 반복하여 적용하면 Level 2 vertex는 $a,c,h,j,g,k$가 추가된다.
  마지막으로 $l, m$이 추가되며 모든 Vertex들이 Tree에 포함되었으므로 Spanning tree를 형성하였다.\

정보

Pseudocode

Algorithm Breadth-First Search

procedure $BFS$($G$: connected graph with vertices $v_1, v_2, \dots, v_n$
$T$ := tree consisting only of vertex $v_1$
$L$ := empty list
put $v_1$ in the list $L$ of unprocessed vertices
while $L$ is not empty
begin
remve the first vertex, $v$, from $L$
for each neighbor $w$ of $v$
if $w$ is not in $L$ and not in $T$ then
begin
add $w$ to the end of the list $L$
add $w$ and edge $\{v,w\}$ to $T$
end
end

BFS algorithm의 Computational complexity는 Graph의 각 Vertex $v$에 대해 $v$와 Adjacent인 모든 Vertex를 조사하고 아직 방문하지 않은 Vertex를 Tree $T$에 추가하는 것이며 Adjacent list가 준비되어 있다고 가정할 때 주어진 Vertex에 Adjacent vertex를 결정하는 데 추가적인 Operation이 필요하지 않으므로 각 Edge는 최대 두 번 검사하여 이 Edge와 Tree에 포함되지 않은 Vertex를 추가해야하는 지 판단해야 하므로 $O(e)$, $O(n^2)$ 만큼의 Operator를 사용함을 알 수 있다.

Backtracking Applications

모든 가능한 Solution을 Exhaustive search(철저한 탐색)으로 Solving 할 수 있는 문제들이 있는데 Solution을 체계적으로 찾기 위해 Decision tree를 사용할 수 있다.
각 Interior vertex는 Dicision을 나타내고 각 Leaf는 가능한 Solution을 나타내게 된다.
Backtracking을 통해 Solution을 찾기 위해 Solution에 도달하기 위한 일련의 Decision을 내리며 가능할 때 까지 이 과정을 진행한 이후 더 이상 어떤 Solution도 도출되지 않을 때 현재 Vertex의 Parent로 가 다른 일련의 Decision을 통해 가능한 다른 Solution을 찾는다.
위 Procedure를 Solution이 더 이상 존재하지 않을 때까지 반복하며 진행한다.

팁

Example

위 Graph를 Coloring하귀 위해 몇 가지의 색상이 필요한 지 Backtracking을 통해 찾음

• Solution
  어떤 Vertex를 선택한 후 Color 1을 할당하고 두 번째 Vertex를 선택하고 이미 선택한 Vertex와 Adjacency라면 다른 Color 2를, 그렇지 않다면 이미 사용한 Color를 할당하는 것을 반복하여 구할 수 있다.
  
  이를 반복하여 위와 같이 구할 수 있으나 이 문제의 경우 Backtracking을 사용하는 것이 비효율적이다.

팁

Example

Positive integer set $x_1,x_2,\dots,x_n$이 주어졌을 때 Subset의 Sum이 $M$이 되는 것을 찾는 문제에서 Backtracking 이용 가능 여부

• Solution
  Term이 없는 Sum으로 시작하여 Integer를 차례로 추가하여 Sum을 구성한다.
  Sequence의 Integer는 이 Integer를 Sum에 추가했을 때 $M$보다 Sum이 작으면 포함한다.
  만약 어떤 Term을 추가하였을 때 $M$보다 커지면 마지막 Term을 제거한 후 Backtracking을 할 수 있다.
  예시로 Set $\{31, 27, 15, 11, 7,5\}$의 Subset 중 Sum이 39인 것을 찾는 문제에 대한 Backtracking solution은 아래와 같다.\

Depth-Fisrt Search in Directed Graphs

DFS, BFS를 사용하여 Digraph를 탐색할 수 있다.
허나 Output이 Spanning tree가 아니라 Spanning forest가 될 수도 있다.

팁

Example

위 Graph의 DFS 결과

• Solution
  
  Backtracking을 통해 위와 같은 결과를 얻을 수 있다.

팁

Example

Website를 Indexing 하기 위해 Google과 같은 Search engine은 알려진 Site에서 시작하여 체계적으로 Web을 Search한다.
이러한 Search engine은 Website를 방문하고 그 내용을 분석하는 Program인 Web spider를 사용한다.
Web spider는 Index를 생성하기 위해 DFS와 BFS를 모두 사용한다.
Web page와 그 사이 Link는 Web graph라는 Digraph로 Modeling 가능하다.
Web page를 Vertex, Link를 Directed edge로 표현하여 DFS를 사용하여 Inital web page에서 진행하여 Backtracking 기법을 사용하여 Link를 Page 별로 따라가는 구조로 동작한다.

10.5. Minimum Spanning Trees

Algorithms for Minimum Spanning Trees

Minimum spanning tree는 Connected weighted graph 의 Spanning tree 중 Weight의 Sum이 가장 작은 Spanning tree를 의미한다.
Minimum spanning tree를 구성하기 위한 Algorithm 중 Greedy algorithm과 Prim's algorithm, Kruskal's algorithm을 이후 설명한다.

Greedy는 각 Step에서 최적화를 해도 최종적으로 최적의 Solution이 보장되지 않는다.

Prim's algorithm의 경우 가장 작은 Weight를 가진 Edge를 선택하여 Spanning tree에 추가한 후 그 다음 Weight를 가진 Edge를 선택해 Spanning tree에 추가할 수 있는 지(Circuit을 만들 지 않는 지)를 확인하고 추가 가능하다면 추가하여 반복해 Minimun spanning tree를 생성한다.

정보

Pseudocode

Algorithm Prim's Algorithm

procedure $Prim$($G$: weighted connected undirected graph with $n$ vertices)
$T$ := a minimum-weight edge
for $i$ := 1 to $n-2$
begin
$e$ := an edge of minimum weight incident to a vertex in $T$ and not forming a simple circuit in $T$ if added to $T$
$T$ := $T$ with $e$ added
end {$T$ is a minimum spanning tree of $G$}

팁

Example

Graph의 모든 Vertex를 연결하는 최소 비용 통신 네트워크를 설계

• Solution
  Minimum spanning tree를 생성하면 되기에 먼저 700 달러 {Chicago, Atlanta}를 먼저 Spanning tree에 추가한 후 {Atlanta, New York}, {Chicago, San Fransisco}, {San Francisco, Denver}를 선택하여 Minimum spanning tree를 생성하여 해결할 수 있었다.

Kruskal's algorithm의 경우 Graph에서 Minimum weight edge를 선택한 후 Edge들과 Simple circuit을 생성하지 않는 Minimum weight edge를 순차적으로 추가하여 $n-1$개의 Edge가 선택된 후 멈추게 된다.

정보

Pseudocode

Algorithm Kruskal's Algorithm

procedure $Kruskal$($G$: weighted connected undirected graph with $n$ vertices)
$T$ := empty graph
for $i$ := 1 to $n-1$
begin
$e$ := any edge in $G$ with smallest weight that does not form a simple circuit when added to $T$
$T$ := $T$ with $e$ added
end {$T$ is a minimum spanning tree of $G$}

팁

Example

Kruskal's algorithm을 사용하여 위 Graph의 Minimum spanning tree 생성

• Solution
  Weight 순서대로 먼저 Edge들을 배치한다.
  1: $\{c,d\} , \{b,f\} , \{k,l\}$
  2: $\{a,b\}, \{c,g\}, \{f,j\}$
  3: $\{a,e\},\{f,g\},\{g,h\},\{i,j\},\{j,k\}$
  4: $\{e,f\}, \{e,i\}, \{g,k\}$
  5: $\{d,h\}$
  위를 이용하여 먼저 임의로 $\{c,d\}$를 선택하고 다음으로 Weight가 적으며 Simple circuit을 생성하지 않는 Edge들을 추가하면 아래 그림과 같이 Minimum spanning tree를 생성할 수 있다.
  
  Prim's algorithm을 사용한 결과물은 아래와 같다.\

Graph에서 $e$개의 Edge와 $v$ 개의 Vertex를 가진 Minimum spanning tree를 찾기 위해 Kruskal's algorithm은 $O(e \log e)$의 Operation를 사용하여 수행하며 Prim's algorithm은 $O(e \log v)$의 Operation을 사용하는 것을 알 수 있다.
Edge $e$가 Vertex $v$에 비해 작은 경우 Kruskal's algorithm을 그렇지 않은 경우 Prim's algorithm을 사용하는 것이 바람직하다.