TIL_20210121
Graph
그래프는 노드(node, 정점(vertex)), 그리고 노드와 노드를 연결하는 간선(edge, 아크라고도 부릅니다) 으로 구성됩니다.
그래프는 노드간에 여러개의 엣지가 존재할 수 있습니다.
다른 노드로부터 오는 엣지의 개수를 진입 차수(in-degree), 노드에서 다른 노드로 가는 엣지의 개수를 진출 차수(out-degree)라고 부릅니다.
방향성을 띄고 있는지에 따라 방향 그래프와 무방향 그래프로 나뉩니다.
그래프의 성향이 무방향(undirected)일 때는 엣지에 의해 연결된 2개의 노드가 대칭일 수 있다는 의미입니다.
반대로 그래프가 어느 한 쪽으로만 향하는 방향성을 가졌다면 비대칭 관계를 의미합니다.
그래프를 코드로 표현하는 방법은 크게 두 가지가 있습니다.
1. 이차원 배열(인접 행렬)을 사용하는 방법
공간은 많이 차지하지만 간단합니다. 노드의 개수(v)의 제곱에 해당하는 공간을 차지합니다. 노드의 수가 적으면 이차원 배열을 사용하는 게 효율적입니다.
노드의 개수가 N인 그래프를 이차원 배열로 표현하면 엣지의 수와 무관하게 항상 N^2의 메모리 공간이 필요합니다.
기본적으로 배정되는 메모리 공간이 클 수밖에 없기 때문에 인접 리스트를 사용하는 것에 비해 효율성이 조금 떨어지는 편입니다.
이차원 배열에서는 인접한 노드를 찾기 위해서 모든 노드를 순회해야 합니다.
장점_
두 노드를 연결하는 엣지의 존재 여부를 O(1)안에 즉시 알 수 있습니다. (해당 노드들의 저장위치를 이미 알기 때문에)
노드의 차수를 O(노드의 수)안에 알 수 있습니다. (이차원 행렬의 i번째 행 또는 열을 모두 더합니다)
단점_
어떤 노드에 인접한 노드들을 찾기 위해서는 모든 노드를 전부 순회해야 합니다.
그래프에 존재하는 모든 엣지의 수는 O(노드의 수^2)안에 알 수 있습니다.
2. 연결 리스트(인접 리스트)를 사용하는 방법
공간은 적게 차지하지만 복잡합니다. 노드의 개수와 엣지의 개수의 합에 해당하는 공간만 차지합니다. 노드의 개수가 많을 때는 연결 리스트를 사용하는 게 효율적입니다.
모든 노드를 연결 리스트에 저장합니다. 노드의 번호만 알면 해당 번호를 배열의 인덱스로 하여 각 노드의 리스트에 쉽게 접근할 수 있습니다.
장점_
어떤 노드에 인접한 노드들을 쉽게 찾을 수 있습니다.
그래프에 존재하는 모든 엣지의 수는 O(노드의 수 + 엣지의 수) 안에 찾을 수 있습니다.
단점_
엣지의 존재 여부와 노드의 차수를 알아보는 데 노드 i 의 리스트에 있는 노드의 수(노드의 차수) 만큼의 시간이 필요합니다.
그래프의 탐색 방법으로는 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) 방법이 있습니다.
깊이 우선 탐색(DFS)
루트 노드(혹은 임의의 노드) 에서 시작해서 다음 분기(branch)로 넘어가기 이전에 해당 분기를 완벽하게 탐색하는 방법입니다.
깊이를 우선하여 탐색합니다. 어떤 노드의 자식 노드가 있으면 해당 자식 노드부터 모두 탐색 후 같은 순위의 다음 노드 탐색을 진행합니다.
모든 노드를 방문하고자 하는 경우에 선택합니다.
너비 우선 탐색(BFS)
루트 노드(혹은 임의의 노드) 에서 시작해서 인접한 노드를 먼저 탐색합니다. 깊이보다 넓게 탐색하는 것이 우선시됩니다.
어떤 노드의 인접 노드가 있으면 인접 노드를 모두 탐색 후 자식 노드를 탐색합니다.
두 노드 사이의 최단 경로 / 임의의 경로를 찾고 싶을 때 선택합니다.
Tree
방향성이 있는 비순환 그래프(DAG_Directed Acyclic Graph)의 한 종류인 트리는 노드로 이루어진 자료 구조입니다.
(최소 연결 트리라고도 불립니다)
트리는 하나의 루트 노드를 갖습니다. 루트 노드는 0개 이상의 자식 노드를 가집니다.
각각의 자식 노드 또한 0개 이상의 자식 노드를 가지고 있고, 이는 반복적으로 정의됩니다.
트리는 노드들과 노드들을 연결하는 간선(edge)로 구성되어 있습니다.
트리는 사이클이 없는 하나의 연결 그래프입니다. 부모 노드와 자식 노드로 구성되어 있기 때문입니다. (부모가 다른 자식 노드들은 직접적으로 연결될 수 없고 부모를 거쳐서만 연결될 수 있습니다)
노드가 N개인 트리는 항상 N-1개의 간선(edge)를 가집니다.
루트 노드에서 어떤 노드로 가는 경로는 유일합니다_임의의 두 노드간의 경로도 유일합니다.
한 개의 루트 노드만 존재하며 모든 자식 노드는 한 개의 부모 노드만 가질 수 있습니다.
트리의 노드들은 특정 순서로 나열될 수도 있고 그렇지 않을 수도 있습니다.
각 노드들은 부모 노드로의 연결이 있을수도 있고 없을 수도 있습니다.
각 노드들은 어떤 자료형으로도 표현 가능합니다.
트리의 종류로는 이진 트리, 이진 탐색 트리, 균형 트리(AVL 트리, red-black 트리), 이진 힙(최대 힙, 최소 힙) 등이 있습니다.
완전 이진 트리 - 왼쪽 자식 노드부터 채워지며 마지막 레벨을 제외하고는 모든 자식노드가 채워져있습니다.
정 이진 트리 - 모든 노드가 2개 혹은 0개의 자식 노드를 가집니다.
포화 이진 트리 - 모든 노드가 0개 혹은 2개의 자식 노드를 가지며 모든 리프 노트가 똑같은 레벨에 있습니다.
비선형 자료구조(하나의 자료 뒤에 여러개의 자료가 존재하는 형태)로 계층적 관계를 표현합니다.
트리 자료구조에서 사용되는 단어의 정리
루트 노드(root node) : 제일 최고 부모 노드. 트리는 하나의 루트 노드만을 가집니다.
단말 노드(leaf node) : 자식이 없는 노드. ‘말단 노드’ 또는 ‘잎 노드’라고도 불립니다.
내부 노드(internal node) : 단말 노드가 아닌 노드
간선(edge) : 노드를 연결하는 선 (link, branch 라고도 부릅니다)
형제(sibiling) : 같은 부모를 가지는 노드
노드의 크기 (size) : 자신을 포함한 모든 자손 노드의 개수
노드의 깊이 (depth) : 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
노드의 레벨 (level) : 트리의 특정 깊이를 가지는 노드의 집합
노드의 차수 (degree) : 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
트리의 차수 (degree of tree) : 트리의 최대 차수
트리의 높이 (height) : 루트 노드에서 가장 깊숙히 있는 노드의 깊이
이진 탐색 트리 (Binary Search Tree)
이진 탐색 트리란 이진 탐색(Binary Search)과 연결 리스트를 결합한 자료구조의 일종입니다.
이진 탐색의 호율적인 탐색 능력 / 자료 입력과 삭제가 용이한 연결 리스트의 장점을 결합하여 고안되었습니다.
이진 탐색 트리의 특징
각 노드의 왼쪽 서브 트리에는 해당 노드의 값보다 작은 값을 지닌 노드들로 이루어져 있습니다.
각 노드의 오른쪽 서브 트리에는 해당 노드의 값보다 큰 값을 지니 노드들로 이루어져 있습니다.
중복된 노드는 없어야 합니다.
왼쪽 서브 트리와 오른쪽 서브트리 또한 이진 탐색 트리의 방식을 따라 구현됩니다.
그래프와 트리의 차이
트리는 루트가 있고 진입 차수(in-degree)가 1인 방향 그래프입니다.
트리의 노드가 1의 진입 차수만 가지는 반면, 그래프의 노드는 하나 이상의 진입 차수를 가질 수 있습니다.
양쪽으로 모두 이어지는 무방향 그래프의 경우 연결된 간선의 수에 따라 x개의 차수가 있다고 말합니다.
모든 노드가 간선으로 연결된 그래프는 완전 그래프라고 부르고, 그래프의 부분집합을 부분 그래프라고 부릅니다.
트리에서는 특정 노드 하나(루트 노드) 에서 다른 노드로 접근이 가능합니다 (Class가 불필요합니다)
그래프에선 특정 노드에서 다른 모든 노드로 접근이 가능하지는 않습니다 (Class가 필요합니다)