Graph
그래프는 노드(Node, 또는 정점 -vertex- 이라고도 부릅니다), 그리고 노드와 노드를 연결하는 간선(edge)으로 구성되어있다.그래프는 무방향(undirected)일 수 있습니다. 이는 간선에 의해 연결된 2개의 노드가 대칭일 수 있다는 의미입니다. 한편 방향성(directed)을 가질 수도 있는데, 이는 비대칭 관계를 의미합니다.
Graph에서 알아야할 용어
- 진입 차수(in-degree) : 방향 그래프에서 외부에서 오는 간선
- 진출 차수(out-degree) : 방향 그래픙에서 외부로 향하는 간선
- 경로 길이(path length) : 경로를 구성하는 데 사용된 간선의 수
- 사이클(cycle) : 단순 경로의 시작 정점과 종료 정점이 동일한 경우
그래프(Graph)의 특징
- 그래프는 네트워크 모델이다.
- 2개 이상의 경로가 가능하다.(방향성과 무방향성)
- self-loop가 가능하다. (자기 자신을 가르키는것)
- 순환(Cyclic)과 비순환(Acyclic)있다.
그래프를 구현하는 2가지 방법
1. 인접 행렬 방식(Adjacency List) :
- 노드의 개수가 N인 그래프를 인접 행렬로 표현한것이다.
- 간선의 수와 무관하게 항상 n^2 개의 메모리 공간이 필요하다.
(시간 복잡도) - 인접 행렬은 조금 효율성이 떨어진다.
- 인접 행렬에서 노드를 찾기 위해 모든 노드를 전부 순회해야 한다.
2. 인접 리스트 방식(Adjacency Matrix) :
- 모든 노드들을 주로 연결 리스트(linked list)를 사용하여 관리하는방법이다.
- 연결 리스트처럼 추가 및 삭제하는것은 매우 효율적으로 할 수 있다.
(이 방법을 주로 많이 씀) - 모든 간선의 수는 O(N+E)이다.
Tree
트리는 노드로 구성된 계층적 자료구조입니다. 최상위 노드(루트)를 만들고, 루트 노드의 child를 추가하고, 그 child에 또 child를 추가하는 방식으로 트리 구조를 구현할 수 있습니다.
트리 구조 특징
- A, B, C, D 등 트리의 구성요소를 노드(node) 라고 합니다.
- 아래 그림의 A처럼, 트리 구조에서 최상위에 존재하는 노드를 root라고 합니다.
- 루트를 기준으로, 다른 노드로의 접근하기 위한 거리를 depth 라고 합니다.
- 같은 부모를 가지면서 같은 depth에 존재하는 노드들은 sibling 관계에 있습니다.
- 그림에서 A는 B와 C의 부모(parent) 이고, B와 C는 A의 자식(child) 입니다.
- 노드와 노드를 잇는 선을 edge 라고 합니다.
- 자식이 없는 노드는 leaf 라고 합니다.
- 노드가 N개인 트리는 항상 N-1개의 간선(edge)을 가진다.
즉, 간선은 항상 (정점의 개수 - 1) 만큼을 가진다. - 한 개의 루트 노드만이 존재하며 모든 자식 노드는 한 개의 부모 노드만을 가진다.
트리에 관한 용어
- 루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
- 단말 노드(leaf node): 자식이 없는 노드, ‘말단 노드’ 또는 ‘잎 노드’라고도 부른다.
- 간선(edge): 노드를 연결하는 선
- 형제(sibling): 같은 부모를 가지는 노드
- 노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수
- 노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
- 노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합
- 노드의 차수(degree): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
- 트리의 차수(degree of tree): 트리의 최대 차수
- 트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이
Binary Search Tree
이진 탐색 트리는 최대 2개의 자식만 갖는 트리이다. 자식 노드 역시 최대 2개의 자식을 갖는다. 이진 탐색 트리에서는 노드의 값이 정렬 방법에 따라 순서가 존재한다. 노드의 왼쪽에는 노드의 값보다 작은 값이, 오른쪽 서브트리에는 노드의 값보다 같거나 큰 값이 존재합니다. 이진 탐색 트리를 순회하는 방법은 크게 깊이 우선 탐색 (DFS, Depth-First Search)와 너비 우선 탐색 (BFS, Breadth-First Search) 알고리즘이 존재한다.
이진 탐색 트리의 종류
- Full Binary Tree(정 이진트리)
Full binary tree는 모든 노드가 0개 or 2개의 자식만을 가지는 경우이다. 다시말해 노드의 자식이 하나만 가진 노드가 있으면 안된다.
Complete Binary Tree(완전 이진트리)
Complete Binary Tree(완전 이진트리)는 마지막 레벨을 뺀 모든 노드들은 자식을 가지고 있어야 하고, 마지막 레벨의 노드도 왼쪽으로 몰려 있어야 한다.
Perfect Binary Tree(포화 이진트리)
Perfect Binary Tree(포화 이진트리)는 모든 레벨에서 노드가 꽉 차있는 트리를 의미한다. 즉 Perfect Binary Tree는 Complete이면서 Full인 이진트리이다.
이진 트리 순회하는 방법
- 전위 순회(Pre-order Traversal): 부모 → 좌 → 우
- 중위 순회(In-order Traversal): 좌 → 부모 → 우
- 후위 순회(Post-order Traversal): 좌 → 우 → 부모
1.깊이 우선 탐색(DFS, Depth-First Search)
루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다.
사용하는 경우: 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다.
깊이 우선 탐색이 너비 우선 탐색보다 좀 더 간단하다.
2.너비 우선 탐색(BFS, Breadth-First Search)
루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.
사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.
Ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우
깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모른다.
너비 우선 탐색의 경우 - Ash와 가까운 관계부터 탐색
