JANGUN


자료 구조


지음 : 정광용



목차

제1장 자료구조란 무엇인가
제2장 배 열
제3장 스 택
제4장 큐
제5장 연결 리스트
제6장 연결 리스트의 응용
제7장 트 리
제8장 스레드 트리
제9장 힙
제10장 선택트리, 숲, 이진 트리 개수
제11장 BS, Splay, AVL, BB
제12장 멀티웨이 탐색 트리 Ⅰ
제13장 멀티웨이 탐색 트리 Ⅱ
제14장 그래프 Ⅰ
제15장 그래프 Ⅱ


제1장 자료구조란 무엇인가

- 자료’는 현실 세계에서 관찰이나 측정을 통해서 수집된 값(value)이나 사실(fact)입니다.
- ‘정보’는 어떤 상황에 대해서 적절한 의사결정(decision)을 할 수 있게 하는 지식(knowledge)으로서 자료의 유효한 해설(interpretation)이나 자료 상호 간의 관계(relationship)를 표현하는 내용이라고 할 수 있습니다.
- ‘정보’는 어떠한 상황에 적절한 결정이나 판단에 사용될 수 있는 형태로 가공되거나 분류되기 위해 ‘처리 과정’을 거쳐서 정리되고 정돈된 ‘자료’의 2차 처리 결과물이다. 정보는 자료를 처리(process)해서 얻어진 유용한 결과(result)라고 할 수 있습니다.
- 자료 사이의 논리적 관계를 컴퓨터나 프로그램에 적용하기 위해서는 자료의 추상화가 필요하며 추상화를 통해 자료의 논리적 관계를 구조화한 것을 자료구조(data structure)라고 합니다.
- 알고리즘이란 컴퓨터에 의해 수행되기 위해 필요한 명령어들의 유한 집합이 사람의 머릿속에 추상화되어 존재하는 것 입니다.
- 자료의 추상화와 구조화가 적절히 이루어지지 못하면 소프트웨어는 비효율적으로 수행되거나 소프트웨어의 확장성에 문제가 생길 수 있습니다.
- 추상화란 공통적인 개념을 이용하여 같은 종류의 다양한 객체를 정의하는 것입니다.
- 자료구조는 입력값의 추상화된 상태라면, 알고리즘은 컴퓨터가 수행해야할 명령의 추상화입니다.
- ‘미리 정의된 자료구조’는 프로그래밍 언어를 개발하는 개발자에 의해 정의되고 추상화되었고, 이를 컴퓨터내부에서 프로그래밍 언어의 형태로 구현된 자료구조를 의미합니다.
- ’미리 정의된 자료구조‘는 프로그래밍 언어 개발자가 프로그램 개발자를 위해 미리 정의하지만, ’사용자 정의 자료구조‘는 프로그램 개발자가 자신의 프로그램 개발 방향에 따라 프로그래밍 언어로 새롭게 정의하여 사용하는 자료구조입니다.
- 알고리즘이 가지고 있어야 할 조건들 ① 출력, ② 유효성, ③ 입력, ④ 명확성, ⑤ 유한성 등이 있습니다.
- 알고리즘을 실행하는데 필요한 시간과 공간을 추정하여 알고리즘의 성능을 분석(performance analysis)을 합니다. 그리고 컴퓨터가 실제로 프로그램을 실행하는데 걸리는 시간을 측정하여 알고리즘의의 성능을 측정(performance measurement)합니다.



제2장 배 열

- 배열은 인덱스와 원소값( <index, value> )의 쌍으로 구성된 집합으로서, 정의된 각 인덱스는 그 인덱스와 관련된 값을 갖습니다.
- 배열의 순서는 메모리 공간에서 저장되는 ‘원소값의 물리적 순서’를 의미합니다.
- 배열의 각 원소의 물리적인 위치(메모리 주소)의 순서가 배열의 인덱스의 순서(논리적인 순서)와 일치합니다.
- 배열의 인덱스값을 이용해서 배열의 원소값에 접근하기 때문에 직접 접근(direct access)입니다.
- 배열의 물리적인 저장 순서는 배열의 인덱스에 의해서 결정되며, 그 순서에 따라 메인 메모리에서의 저장 위치의 순서가 됩니다.
- create(n)은 n개의 원소들을 저장할 수 있는 공백 배열(empty array)을 생성합니다. 배열을 생성할 때 n개의 원소들을 저장할 수 있는 공간은 만들어지지만 그 안에 채워진 원소값들이 아직은 없다는 것을 의미합니다.
- 연산 retrieve(a,i)는 배열 a와 인덱스 i를 매개 변수로 전달받아 인덱스 i 위치에 대응되는 원소값 e가 있다면 원소값 e를 반환하고 그렇지 않은 경우 에러 메시지를 반환합니다.
- 연산 store(a, i, e)는 배열 a와 인덱스 i, 원소값 e를 매개 변수로 전달받아 Index를 검사하여 i값이 유효할 경우 쌍이 되게 원소값을 i번째 인덱스에 저장하고 배열 a를 반환합니다.
- 가장 기본적인 배열은 1차원 배열이며, 한줄짜리 배열을 의미하므로 인덱스는 하나입니다. 한줄짜리 배열은 메모리 영역도 한줄로 할당받습니다.
- 2차원 배열의 행우선 저장방식은 하나의 행이 모두 연속적으로 메모리 영역을 할당받고, 다음 행이 메모리 영역을 연속적으로 할당받는 방식이다.
- 원소값이 0인 원소가 그렇지 않은 원소보다 상대적으로 많은 행렬을 희소행렬(sparse matrix)이라 합니다.



제3장 스 택

- 스택을 생성하는 연산은 프로그래머가 지정한 크기의 새로운 스택을 생성하는 연산이며, 매개변수인 maxStack은 스택이 저장할 수 있는 최대 개수의 element를 의미합니다.
- IsFull (stack, maxStackSize) 연산은 스택이 가득 찼는지를 확인하며, 저장된 원소의 수가 maxStackSize와 같으면 TRUE (‘스택이 가득 찼다’)를 반환하고 아니면 FALSE (‘스택에 여유 저장 공간이 있다’)를 반환합니다.
- Stack Push (stack, item) 연산은 스택에 새로운 원소를 삽입합니다. 만일 스택이 가득 찼다 (Full)면 더 이상의 원소를 스택에 삽입할 수 없으며, ‘stackFull‘ 메시지를 출력합니다.
- Boolean IsEmpty (stack) 연산은 스택 상태가 빈 상태인지를 확인합니다. 만일 스택이 빈 상태이면 ‘TRUE’ 값을 반환하고, 스택에 하나 이상의 원소라도 있다면 ‘FALSE’ 값을 반환합니다.
- Element Pop (stack) 연산자는 스택이 빈 상태라면 삭제할 원소가 없으므로 ‘stackEmpty‘를 출력합니다. 하지만, 빈 상태가 아니라면 삭제할 원소가 있으므로, 스택의 top이 가리키는 원소를 삭제하고 그 원소를 반환합니다.
- 스택의 추상 자료형에서 정의된 연산은 시스템 개발자에 따라 다르게 정의되고 구현될 수도 있고, 컴파일러 설계자에 따라 프로그래밍 언어에서 다르게 제공될 수도 있습니다.
- 스택은 객체와 그 객체가 저장되는 순서를 기억하는 방법에 관한 추상 자료형입니다.
- 중위 표기법(infix notation)은 연산자를 피연산자의 사이에 표기하는 방법이며 일반적으로 가장 많이 사용되는 표기방법(A+B)입니다.
- 전위 표기법(prefix notation)은 연산자를 피연산자의 앞에 표기하는 방법 (+AB)입니다.
- 후위 표기법(postfix notation)은 연산자를 피연산자의 뒤에 표기하는 방법 (AB+)입니다.



제4장 큐

- 큐는 한쪽에서는 삽입이 발생하고 다른 한쪽에서는 삭제가 발생하도록 정의되었으며, 먼저 삽입된 원소가 먼저 삭제 되므로 선입 선출(First-In-First-Out : FIFO) 또는 선착순 서브(First-Come-First-Serve : FCFS) 알고리즘을 갖는 순서 리스트라고 합니다.
- 큐에서는 원소의 삭제연산이 이루어지는 곳을 앞(front)이라 하고 삽입연산이 이루어지는 끝을 뒤(rear)라고 합니다.
- 큐 생성 함수(Create_q(maxQueueSize))를 호출하기만 하면 프로그래머가 지정한 크기의 새로운 큐를 생성할 수 있습니다. Create_q(maxQueueSize) 함수의 매개변수인 maxQueue는 큐가 저장할 수 있는 최대 개수의 원소(ele-ment)를 의미합니다.
- Boolean IsFull_q(queue, maxQueueSize) 연산은 큐가 가득 찼는지를 확인합니다. 즉, 큐에 저장된 원소(element)의 개수가 maxQueueSize와 같다면, 그 큐는 가득 찼으며 큐에 자료(원소)를 더 이상 저장시킬 수 없다는 것을 의미합니다.
- Queue Add_q(queue, item) 연산은 큐에 새로운 원소를 삽입합니다. 만일 큐가 가득 찼다(Full)면 더 이상의 원소를 큐에 삽입할 수 없으며, ‘queueFull‘ 메시지를 출력합니다.
- Boolean IsEmpty(queue) 연산은 큐 상태가 빈 상태인지를 확인합니다. 만일 큐가 빈 상태이면 ‘TRUE’ 값을 반환하고, 큐에 하나이상의 원소라도 있다면 ‘FALSE’ 값을 반환합니다.
- Element Delete_q(queue) 연산자는 큐가 빈 상태라면 삭제할 원소가 없으므로 ‘queueEmpty‘를 출력합니다. 하지만, 빈 상태가 아니라면 삭제할 원소가 있으므로, 큐의 front가 가리키는 원소를 삭제하고 그 원소를 반환합니다.
- 큐의 추상자료형에서 정의된 연산은 시스템 개발자에 따라 다르게 정의되고 구현될 수도 있고, 컴파일러 설계자에 따라 프로그래밍 언어에서 다르게 제공될 수도 있습니다.
- 원형큐는 파이프의 입구와 출구 부분을 연결시킨 형태입니다. 연결된 부분의 데이터 공간을 연속적으로 사용하기 위해 ‘나머지 연산자‘를 사용합니다.



제5장 연결 리스트

- 리스트의 ‘순서’는 데이터가 저장되는 물리적인 위치와 상관없이 사람들의 머릿속에 인식되는 ‘논리적인 순서’, 혹은 리스트에 나타나는 원소들 간의 ‘의미적인 순서’를 의미합니다.
- 배열을 이용한 리스트의 구현은 실제 IT 서비스 환경에서는 자주 사용되지 않고 있습니다. 자료의 삽입과 삭제가 빈번히 발생하는 상황에서, 리스트를 배열로 구현하는 것은 빈번한 자료 이동으로 인한 비효율적인 컴퓨팅 성능을 유발합니다.
- 포인터를 이용하는 방법은 원소의 자리에는 원소값을 저장하고, 다음 원소를 가리키는 정보의 자리에는 다음 원소가 저장될 위치의 주소값을 저장합니다. 조금 더 ‘프로그램’스럽게 설명하자면, 리스트의 원소의 자리와 다음 원소를 가리키는 정보의 자리를 합쳐서 노드(node)라고 합시다. 노드에는 데이터 요소(원소)와 리스트의 다음 원소를 지시하는 포인터(pointer, 주소)를 가진다고 생각하면 됩니다. 이 포인터는 링크(link)라고도 부릅니다.
- 포인터의 ‘메모리 주소값’이라는 것은 메모리에 저장되는 값의 위치라고 생각하면 됩니다. 메모리에 저장되는 값(데이터)은 저장 위치에 대한 주소를 가지며, 이 저장 위치를 이용해서 리스트의 원소값을 찾아갈 수 있습니다.
- 다양한 데이터형의 변수를 하나의 상자 안에 넣어서 선언하거나 사용하는 C 프로그래밍 문법이 구조체(struct)입니다.



제6장 연결 리스트의 응용

- 단순 연결 리스트는 하나의 링크 부분이 존재하고, 각각의 노드는 후행 노드만을 가리키는 구조이며, 특정 노드의 선행 노드에 대한 접근은 헤드 노드부터 재검색해야 하는 단점을 가집니다.
- 이중 연결 리스트는 선행 노드를 가리키는 링크 부분과 후행 노드를 가리키는 링크 부분을 가집니다.
- 단순 연결 리스트가 사용하지 않는 마지막 노드의 링크 부분을 활용하면서도 프로그램 성능에 도움이 되도록 하기 위해서 제안된 원형 연결 리스트는 한 방향으로 모든 노드가 원형으로 계속 연결되어 있기 때문에 한 노드에서부터 다른 어떤 노드로도 접근할 수 있는 이점이 있습니다.



제7장 트 리

- 트리는 논리적 계층이 있는 구조입니다.
- 트리를 구성하는 항목을 “노드(node)” 혹은 “정점(vertex)”이라고 합니다.
- 트리에서 루트는 부모를 갖지 않은 노드입니다.
- 트리에 있는 어떤 노드에 대해 그 노드로 들어오는 선의 개수를 진입 차수, 나가는 선의 개수를 진출 차수라 합니다.
- 트리에서 각 노드의 차수(degree of a node)는 진출 차수로 정의합니다.
- 트리의 차수(degree of a tree)는 트리내의 각 노드의 차수 가운데 최대 차수로 정의합니다.
- 루트도 잎도 아닌 노드를 내부 노드라 하고 같은 부모를 갖는 노드들을 형제(sibling)라 합니다.
- 트리에서 각 노드의 레벨(level)은 루트로부터 그 노드까지 이어진 경로의 길이로 정합니다.
- 트리는 데이터의 계층 관계, 포함 관계 등을 나타내는 자료구조입니다.
- 트리에 속한 모든 노드의 차수가 2 이하인 트리를 이진 트리라합니다.
- 높이가 k인 이진 트리가 레벨 0부터 k-2까지 다 채우고 마지막 k-1 레벨에서 왼쪽부터 오른쪽으로 노들들이 차례로 채워졌을 때 포화 이진 트리라고 합니다. .
- 루트를 방문하는 순서에 따라 각각 전위(preorder) 순회, 중위(inorder) 순회, 후위(postorder) 순회라고 구분하여 부릅니다.



제8장 스레드 트리

- 정해진 순회 방법에 따른 방문순서를 유지하는 스레드(thread)라는 포인터를 갖는 이진 트리를 스레드 트리라고 합니다.
- 오른쪽 스레드는 정해진 순회 순서에 따른 그 노드의 후속 노드를 가리키고 왼쪽 스레드는 그 노드의 선행 노드를 가리킵니다.
- 스레드를 구현 할 때 스레드를 저장하는 포인터를 추가하는 방법이 있습니다.
- 스레드를 구현 할 때 이진 트리를 위한 연결 리스트의 노드 구조를 그대로 사용하면서, 리프 노드에 있는 사용하지 않는 포인터를 활용하는 방법입니다.
- 노드가 n개인 이진 트리를 연결 리스트로 구현할 때 null 포인터는 항상 2n-(n-1) = n+1개가 존재합니다.
- 리프 노드에 있는 포인터를 활용하는 방법은 각 노드에 대해 포인터가 스레드로 사용 중인지 아니면 서브트리에 대한 포인터인지를 구분하기 위해 tag 필드를 사용해야만 합니다.



제9장 힙

- 힢은 무엇인가를 쌓아놓은 더미이고 항상 가장 위에 있는 것을 우선 꺼내는 구조를 상징합니다. 그리고 힢은 우선순위 큐의 한 종류입니다.
- 힢은 완전 이진트리이며, 최소힢은 루트가 최소값이고 최대힢은 최대값입니다.
- 최대힢은 트리의 모든 노드가 자식 노드보다 큰 값을 갖는 것을 알 수 있습니다.
- 최소힢은 트리의 모든 노드가 자식 노드보다 작은 값을 갖는 것을 알 수 있습니다.
- 힢에서 노드를 삭제한 후에도 완전 이진트리의 모습을 유지해야 하며, 최대힢 혹은 최소힢의 조건을 만족해야 합니다.



제10장 선택트리, 숲, 이진 트리 개수

- 차례로 정렬된 데이터 리스트 k가 있다고 가정할 때 그것들을 완전한 순서를 유지하는 하나의 리스트로 만드는 과정을 합병 정렬이라고 합니다.
- 합병 정렬에 사용하는 특수한 트리가 선택트리입니다.
- 선택트리에는 승자트리와 패자트리 두 종류가 있습니다.
- 승자트리는 각 노드가 두 개의 자식노드 보다 더 작은 값을 갖는 완전 이진트리(실제로는 포화 이진트리)입니다.
- 승자트리 구축과정은 작은 값이 승자로 올라가는 토너먼트 경기와 유사합니다. 즉 트리의 각 내부 노드는 두 자식 노드 값의 승자를 자신의 값으로 합니다.
- 선택트리를 사용하는 경우 트리의 레벨은 log(k+1)이므로 선택트리를 재구성하는 시간은 O(logk)이고 따라서 n개의 데이터를 모두 합병하는데 필요한 계산 복잡도는 O(nlogk)입니다.
- 패자트리는 루트노드 위에 최상위 0번 노드를 갖습니다. 이 0번 노드에는 경쟁에서 이긴 최종 승자를 저장합니다.
- 패자를 부모 노드에 저장하고 승자는 부모의 부모 노드로 올라가서 다시 경쟁합니다. 따라서 루트에는 마지막 토너먼트 패자를 저장하고 최종 승자는 0번 노드에 저장합니다.
- 분리된 트리 모임을 숲이라 부르며, 숲은 n(≥0)개 이상의 분리된 트리 집합입니다.
- 숲을 이진트리로 바꾸려면 먼저 각 트리(Ti)를 이진트리로 바꿉니다(TiBT). 이때 TiBT 의 루트는 왼쪽 서브트리만을 같습니다.
- 다음은 T1BT 의 루트를 최상위 루트로 하고 왼쪽 자식은 그 왼쪽 서브트리(오른쪽 서브트리는 없습니다) 오른쪽 자식은 나머지들의 이진트리(BT2-n)가 되도록 합니다.
- 어떤 이진 트리에 대한 전위-중위 순회 방문 순서가 주어지면 트리 구조를 유일하게(한 개) 정할 수 있습니다.
- 1부터 n까지 수를 스택에 넣었다가 가능한 모든 방법으로 삭제하여 생성할 수 있는 경우의 수와 n개의 노드를 가진 상이한 이진트리의 수가 같습니다.
- 카탈란이라는 수학자가 노드 n개인 서로 다른 이진 트리의 개수가 (2n)! / [n! (n+1)!]과 같음을 증명했습니다.



제11장 BS, Splay, AVL, BB

- 트리에 특정 데이터가 있는지를 검색하고, 노드를 자주 삽입, 삭제하는 응용 문제에 가장 효과적인 이진 트리는 이진 탐색 트리(binary search tree)입니다.
- 키는 각 노드를 식별하기 위해서는 별도의 간단한 이름을 붙여준 것으로 노드의 데이터라고 생각할 수 있습니다.
- 이진 탐색 트리는 전위 순회, 중위 순회 및 후위 순회로 모든 정점을 차례로 순회할 수 있고 트리 내의 특정 정점을 탐색할 수도 있습니다.
- 이진 탐색 트리에서 새 노드는 항상 잎으로 삽입합니다. 즉, 루트부터 킷값을 비교하며 자기가 삽입될 위치가 왼쪽이냐 오른쪽이냐를 정하며 내려갑니다.
- Splay 트리는 자주 탐색하는 키를 가진 노드를 루트에 가깝게 위치하도록 구성한 이진 탐색 트리입니다.
- Splay 트리는 Splay 연산을 적용하여 최근에 사용하려고 접근한 노드 x를 루트에 위치시켜 트리를 재구성합니다.
- AVL 트리는 노드 vi의 왼쪽 서브트리 높이와 vi의 오른쪽 서브트리 높이가 최대 1만큼 차이가 난다는 조건을 만족하는 트리입니다.
- 트리의 높이란 노드가 가질 수 있는 가장 높은 레벨에 1을 더한 값으로 루트로부터 잎까지 가장 긴 경로 길이를 말합니다.
- 트리의 무게는 트리에 속한 잎 노드의 개수로 정의합니다.
- 무게가 균형 잡힌 트리란 각 노드의 양쪽 서브트리 무게가 균형을 유지하는 트리입니다. 이 트리를 무게가 균형 잡힌 트리(weight-balanced tree) 또는 BB-트리(bound-balanced)라고 부릅니다.
- AVL 또는 BB 트리에 대하여 각각 높이 또는 크기 제한 조건을 만족시키는데 드는 비용은 트리를 완전히 균형 잡히게 유지하는 비용이나 노력보다 훨씬 작습니다.
- 삽입이나 삭제 후에 트리를 완전히 균형 잡히게 유지하기 위해서는 O(n)개의 노드를 옮겨야 하는 반면에 AVL 또는 BB 트리는 O(log2n)개의 노드를 옮기면 되는 것으로 알려졌습니다.



제12장 멀티웨이 탐색 트리 Ⅰ

- 트리의 노드가 m개 이하의 가지를 가질 수 있는 탐색 트리를 m원 탐색 트리라고 합니다.
- m 원 탐색 트리는 이진 탐색 트리를 확장한 것으로 탐색 트리의 제한을 따르되 2개 이상(m 개 이하) 자식을 가질 수 있습니다.
- 인덱스 구조를 구현하는데 가장 일반적으로 사용하는 방법으로 차수가 m 인 B 트리가 있습니다.
- B 트리는 루트와 잎 노드를 제외한 트리의 각 노드는 최소 [m/2]개의 서브트리를 갖습니다.
- B 트리의 루트는 최소한 2개의 서브트리를 갖습니다.
- B 트리의 모든 잎 노드는 같은 레벨에 있습니다.
- B 트리의 삽입 연산에서 노드가 꽉 차있는 경우는 분리해서 키값과 포인터를 재분배해야 합니다.
- B 트리 삭제 연산에서 삭제 결과 개수가 부족하면 그 노드를 다른 노드와 묶어야 합니다.
- 노드의 약 2/3 이상이 차야하는 B 트리를 B* 트리라고 합니다.
- B* 트리는 노드가 꽉 차면 분리하지 않고, 키와 포인터를 재배치하여 다른 형제 노드로 옮깁니다.
- B+ 트리는 인덱스된 순차 파일을 구성하는데 사용합니다. 인덱스된 순차 파일은 데이터를 차례로 처리하는 순차 처리와 특정 데이터를 직접 찾아 처리하는 두 가지를 모두 효율적으로 할 수 있는 구조입니다.
- B+ 트리는 잎 노드의 마지막 포인터는 다음 키값을 갖는 노드를 가리킵니다. 따라서 순차 처리를 할 때는 이 포인터를 이용해서 차례로 다음 데이터에 접근해서 처리할 수 있습니다.
- B+ 트리에서는 모든 키값이 잎 노드에 있고 그 키값에 대응하는 실제 데이터에 대한 주소를 잎 노드만이 가지고 있습니다.



제13장 멀티웨이 탐색 트리 Ⅱ

- 차수가 2인 노드를 2-노드, 3인 노드를 3-노드라 합니다.
- 2-노드와 3-노드만으로 구성한 트리를 2-3 트리라 합니다. 이 트리는 균형이 잡힌 B 트리 계열과 거의 같은 성능을 유지하면서도 상대적으로 삽입과 삭제가 용이합니다.
- 2-노드, 3-노드, 및 4-노드만으로 구성한 트리를 2-3-4 트리라 합니다. 이 트리는 2-3트리와 같은 특성을 갖습니다. 대신 같은 수의 노드를 더 낮은 레벨로 구축할 수 있습니다.
- 2-3-4 트리는 4노드를 갖기 때문에 경우에 따라서는 기억 장소를 낭비할 수 있습니다. 기억장소를 효율적으로 사용하기 위해 2-3-4 트리를 이진 트리로 나타낸 것이 레드 블랙 트리입니다.



제14장 그래프 Ⅰ

- 정점 집합 V 와 간선 집합 E 에 대하여 그래프는 G=(V,E)는 입니다. 즉, 대상(V)과 그 대상들의 관계(E)를 나타내는 수단입니다.
- 방향 그래프는 간선의 방향이 유의미한 그래프로 예를 들어 부자 관계를 그래프로 나타내면 간선은 유의미 합니다.
- 무방향 그래프는 간선의 방향이 무의미한 그래프로 예를 들어 두 지점 사이에 도로가 있는 지 아닌지를 그래프로 나타내면 간선은 무의미합니다. 단, 도로가 일방통행로라면 간선의 방향은 의미를 갖고 그 그래프는 방향 그래프로 나타내야 합니다.
- 두 정점쌍이 간선을 여러 개 가질 수 있는 그래프를 다중 그래프라 합니다. 예를 들어 두 지점사이에 여러 교통수단이 있다면 다중 그래프로 나타 낼 수 있습니다.
- 두 정점을 잇는 간선이 중요도나 비용 등을 나타내는 가중 값을 갖는 그래프를 가중 그래프라고 합니다. 예를 들어 두 지점 사이를 연결 하는 도로의 거리가 중요한 의미를 갖는 문제라면 그 그래프는 가중 그래프로 표현해야 합니다.
- 두 정점을 잇는 간선 열을 경로라 합니다. 그리고 경로에 있는 간선의 수를 그 경로의 경로 길이로 정의합니다.
- 한 정점에서 출발하여 자신으로 연결하는 간선을 루프라고 합니다. 예를 들어 입력에 따라 상태가 변하는 시스템을 그래프로 나타내는 경우 어떤 입력에 대해서는 상태가 변하지 않는다면 루프로 표현할 수 있습니다.
- 시작점과 끝점이 같은 경로를 사이클이라 합니다. 그리고 하나 이상의 사이클을 갖는 그래프를 사이클이 있는 그래프 혹은 사이클 그래프라 하고 사이클이 없는 그래프를 무 사이클 그래프 혹은 트리라고 합니다.
- 두 정점이 간선으로 연결되었을 때 두 정점이 인접한다고 표현합니다. 두 정점이 잇는 경로가 있다는 것과 반드시 구분해야 합니다.
- 그래프의 표현방법의 하나로 정점 사이의 인접성을 행렬로 나타낸 것을 인접행렬 표현법이라 하고 정점 사이의 인접성을 연결 리스트로 나타낸 것을 인접 리스트 표현법이라 합니다. 그래프가 정점 개수에 비하여 간선 개수가 적으면 연결 리스트로 나타내야 기억 장소를 효율적으로 사용할 수 있습니다.



제15장 그래프 Ⅱ

- 그래프 내 특정 정점을 찾는 연산을 그래프 탐색이라 합니다. 그래프는 트리와 다르게 루트노드가 없으므로 시작을 나타내는 특정 정점이 주어집니다. (트리에서 노드로 부르는 것을 그래프에서는 보통 정점이라 합니다. 이 책은 그렇게 용어를 사용했습니다.)
- 특정 정점에서 시작하여 그래프의 모든 정점을 빠짐없이 그리고 중복 없이 방문하는 것을 그래프 순회라고 합니다. 그래프 탐색은 순회를 통하여 정점을 방문하다가 정해진 정점을 만나면 탐색 성공이고 모든 정점을 방문해도 정해진 정점을 만나지 못하면 실패입니다.
- 깊이 우선 탐색은 특정 점정에서 시작하여 자손을 먼저 방문 한 후 (더 이상 방문 할 자손이 없으면) 전 단계 형제를 방문하는 알고리즘입니다. 그래프는 루트가 없고 간선에 방향도 없으므로 어려워합니다. 시작 정점을 위에 올려놓고 생각하면 다소 쉬워집니다. 특히 시각적으로 더 위에 있는 것이 더 깊은 곳일 수 도 있음을 받아들이면 이해에 도움이 됩니다.
- 너비 우선 탐색은 특정 정점에서 시작하여 모든 형제를 방문한 후 자손을 방문하는 순서를 따릅니다. 자식이 여러 개인 경우 그것들의 순서를 정하는 규칙만 정하면 역시 어렵지 않게 이해 할 수 있습니다.
- 그래프의 모든 정점을 포함하는 사이클이 없는 부분 그래프 즉, 트리를 신장트리라 합니다. 그리고 가중 그래프에서 비용이 최소인 신장 트리를 최소 비용 신장 트리라 합니다. 대표적으로 프림, 크루스컬, 및 솔린 알고리즘을 사용합니다. 모두 사람 이름입니다.
- 프림 알고리즘은 최소비용을 갖는 간선을 차례로 추가하는 방법으로 트리를 구축합니다. 물론 사이클이 형성되면 해당 간선은 포기합니다. 비용이 적은 것을 합치면 그들의 합이 최소가 될 것이라는 (항상 옳지는 않은) 가정을 근거로 합니다.
- 크루스컬 알고리즘은 프림 알고리즘처럼 현재 완성한 트리에 간선을 붙여 트리를 키워나가는 것이 아닙니다. 이 알고리즘은 매 단계 최소 비용 간선을 선택해 사이클만 형성하지 않으면 받아 들이는 것입니다. 그러니까 중간 과정은 (트리가 아니고) 숲 일 수 있습니다.
- 솔린 알고리즘은 앞 두 방법과 다르게 매 단계에 다수의 간선을 선택합니다. 먼저 간선이 하나도 없고 그래프의 모든 정점들로 구성된 숲에서 시작합니다. 그리고 단계가 거듭되면서 숲 내의 트리를 최소 비용을 갖는 간선으로 연결합니다. 이 과정을 남은 간선이 없거나 완전한 트리가 생성될 때까지 반복하면 신장 트리를 얻습니다.