Graph
그래프는 노드(Node, 또는 정점), 그리고 노드와 노드를 연결하는 간선(edge)으로 구성된다.
그래프는 무방향(undirected) 일(undirected) 수 있습니다. 이는 간선에 의해 연결된 2개의 노드가 대칭일 수 있다는 의미이며
한편 방향성(directed)을 가질 수도 있는데, 이는 비대칭 관계를 의미한다.
이를 무방향 그래프와 방향 그래프라고 말할 수 있는데 이를 비교해보자
<무방향 그래프 VS 방향 그래프>
무방향 그래프(Undirected Graph)
무방향 그래프의 간선은 간선을 통해서 양 방향으로 갈 수 있다.
정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다.
(A, B)는 (B, A) 동일
Ex) 양방향 통행 도로
방향 그래프(Directed Graph)
간선에 방향성이 존재하는 그래프이며
A -> B로만 갈 수 있는 간선은 <A, B>로 표시한다.
<A, B>는 <B, A>와 다르다.
Ex) 일방 통행
[그래프(Graph)와 관련된 용어]
정점(vertex): 위치라는 개념. (node라고도라고도 부름)
간선(edge): 위치 간의 관계. 즉, 노드를 연결하는 선 (link, branch라고도라고도 부름)
인접 정점(adjacent vertex): 간선에 의 해 직접 연결된 정점
정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배
진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수 (내차수라고도 부름)
진출 차수(out-degree): 방향 그래프에서 외부로 향하는 간선의 수 (외 차수라고도 부름)
방향 그래프에 있는 정점의 진입 차수 또는 진출 차수의 합 = 방향 그래프의 간선의 수(내차수 + 외차수)
경로 길이(path length): 경로를 구성하는 데 사용된 간선의 수
단순 경로(simple path): 경로 중에서 반복되는 정점이 없는 경우
사이클(cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우
[그래프(Graph)의 특징]
- 그래프는 네트워크 모델이다.
- 2개 이상의 경로가 가능하며 즉 노드들 사이에 무방향/방향에서 양방향 경로를 가질 수 있다.
- self-loop 뿐 아니라 loop/circuit 모두 가능하다.
- 루트 노드라는 개념이 없다.(tree구조에서 나옴)
- 부모-자식 관계라는 개념이 없다.(tree구조에서 나옴)
- 순회는 DFS(깊이 우선 탐색 Depth-First Search) 나 BFS(너비 우선 탐색로 이루어진다.
- 그래프는 순환(Cyclic) 혹은 비순환(Acyclic)이다.
- 그래프는 크게 방향 그래프와 무방향 그래프가 있다.
- 간선의 유무는 그래프에 따라 다르다.
[인접 리스트와 인접 행렬 중 선택 방법]
인접 리스트 (그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(Sparse Graph)의의 경우)
장점 : 어떤 노드에 인접한 노드들을 쉽게 찾을 수 있다.
그래프에 존재하는 모든 간선의 수는 O(N+E) 안에 알 수 있다. (인접 리스트 전체를 조사)
단점 : 간선의 존재 여부와 정점의 차수: 정점 i의 리스트에 있는 노드의 수 즉, 정점 차수만큼의 시간이 필요
인접 행렬 (그래프에 간선이 많이 존재하는 밀집 그래프(Dense Graph)의의 경우)
장점 : 두 정점을 연결하는 간선의 존재 여부 (M [i][j])를 O(1) 안에 즉시 알 수 있다.
정점의 차수는 O(N) 안에 알 수 있다. : 인접 배열의 i번 째 행 또는 열을 모두 더한다.
단점 : 어떤 노드에 인접한 노드들을 찾기 위해서는 모든 노드를 전부 순회해야 한다.
그래프에 존재하는 모든 간선의 수는 O(N^2) 안에 알 수 있다. : 인접 행렬 전체를 조사한다.
tree
트리는 노드로 구성된 계층적 자료구조로 최상위 노드(루트)를 만들고, 루트 노드의 child를 추가하고, 그 child에 또 child를 추가하는 방식으로 트리 구조를 구현한다.(얼핏 DOM의 트리구조가 생각이 났다.)
- A, B, C, D 등 트리의 구성요소를 노드(node) 라고 합니다.
- 위 그림의 A처럼, 트리 구조에서 최상위에 존재하는 노드를 root라고 합니다.
- 루트를 기준으로, 다른 노드로의 접근하기 위한 거리를 depth 라고 합니다.
- 같은 부모를 가지면서 같은 depth에 존재하는 노드들은 sibling 관계에 있습니다.
- 그림에서 A는 B와 C의 부모(parent) 이고, B와 C는 A의 자식(child) 입니다.
- 노드와 노드를 잇는 선을 edge 라고 합니다.
- 자식이 없는 노드는 leaf 라고 합니다.
트리 구조에서의 깊이(depth) 높이(height)는 어떻게 다를까?
아래 그림을 보면 노드의 depth는 노드에서 트리의 루트 노드까지의 가장자리 수이며
노드의 height는 노드에서 잎까지 가장 긴 경로의
앞서 배운 그래프와 트리의 차이점은 뭐가 있을까?
- 트리는 두 개의 정점 사이에 하나의 경로만 존재하는 반면에 그래프는 노드 사이에 단방향 및 양방향 경로를 가질 수 있다.
- 트리는 정확하게 하나의 루트 노드가 있으며 모든 자식은 단 하나의 부모만 가질 수 있지만 그래프는 루트 노드의 개념이 존재하지 않는다.
- 그래프에는 루프와 자체 루프가 있을 수 있지만 트리에는 루프와 자체 루프가 있을 수가 없다.
- 그래프는 루프와 자체 루프를 가질 수 있기 때문에 더욱 복잡하고 트리는 그래프에 비해 단순하다.
- 트리는 선주문, 순차 및 후행 기술을 사용하여 가로지르지만 그래프 트래버 설에서는 BFS (Breadth First Search)와 DFS (Depth First Search)를 사용한다.
- 나무는 n-1 개의 모서리를 가질 수 있지만 그래프에는 미리 정의된 수의 엣지가 없으며 그래프에 따라 다르다.
- 트리는 계층 적 구조로 이루어져 있지만 그래프에는 네트워크 모델로 이루어져 있다고 볼 수 있다.
Binary Search Tree
트리의 구조이지만 특징인 부분은 최대 2개의 자식만 갖는 트리라고 볼 수 있다.
트리 구조는 재귀적이므로, 자식 노드 역시 최대 2개의 자식을 가지며 노드의 값이 정렬 방법에 따라 순서가 존재한다.
노드의 왼쪽 서브 트리에는 노드의 값보다 작은 값이, 오른쪽 서브트리에는 노드의 값보다 같거나 큰 값이 존재한다.
순회 알고리즘은 그래프·트리에 저장된 모든 값을 중복이나 빠짐없이 살펴보고 싶을 때 사용하게 되는데 순회 방법 중 깊이 우선 탐색(DFS, Depth First Search)으로는 전위 순회(Pre-order traversal), 정위 순회(In-order traversal), 후위 순회(Post-order traversal)가 있으며, 너비 우선 탐색(BFS, Breadth First Search)으로는 레벨 순회가 있다.
1. 깊이 우선 탐색(DFS, Depth-First Search)
루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법이라고 보면 된다.
즉 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하고 모든 노드를 방문하고자 하는 경우에 이 방법을 선택하면 된다.
깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하지만 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.
자기 자신을 호출하는 순환 알고리즘의 형태를 지니며 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다는 것 (이를 검사하지 않을 경우 무한루프에 빠질 위험이 있음)
※ 깊이 우선 탐색(DFS)의 시간 복잡도
- DFS는 그래프(정점의 수 : N, 간선의 수: E)의 모든 간선을 조회함
* 인접 리스트로 표현된 그래프 : O(N+E)
* 인접 행렬로 표현된 그래프 : O(N^2)
2. 너비 우선 탐색(BFS, Breadth-First Search)
루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이며 깊게(deep) 탐색하기 전에 넓게(wide) 탐색한다. 보통 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택하면 유용하다.
BFS는 앞서 말한 DFS와는 다르게 재귀적으로 동작하지 않으며, 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다는 것이다 이를 검사하지 않을 경우 무한 루프에 빠질 위험이 있다.
BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용하며 선입선출(FIFO) 원칙으로 탐색한다.
앞서 말한 순회 방법 중 깊이 우선 탐색(DFS, Depth First Search)의 전위 순회(Pre-order traversal), 정위 순회(In-order traversal), 후위 순회(Post-order traversal)는 아래와 같이 순회하게 된다.
전위 순회(Preorder Traversal): 부모 → 좌 → 우
중위 순회(Inorder Traversal): 좌 → 부모 → 우
후위 순회(Postorder Traversal): 좌 → 우 → 부모
이진 탐색 트리의 종류에도 여러 가지가 있는데
- 정 이진트리(Full Binary Tree)
트리의 모든 노드가 0개 혹은 2개의 자식을 가지는 경우이다. 즉 자식을 하나만 가진 노드가 없어야 한다.
- 완전 이진트리(Complete Binary Tree)
마지막 레벨을 제외한 나머지 노드가 꽉 차 있어야 하며, 마지막 레벨의 노드도 왼쪽으로 몰려 있어야 한다.
- 포화 이진트리(Perfect Binary Tree)
모든 레벨에서 노드가 꽉 차있는 트리를 의미한다. 즉 Perfect Binary Tree는 Complete이면서 Full인 이진트리이다.
'개념정리' 카테고리의 다른 글
| 9/9 [TIL] Inheritance Patterns (0) | 2020.09.09 |
|---|---|
| 9/9 [TIL] OOP(Object Oriented Programming) (0) | 2020.09.09 |
| 9/4[TIL]Linked List, Hash Table (0) | 2020.09.07 |
| 9/3[TIL] Stack & Queue (0) | 2020.09.04 |
| 9/2[TIL] ESLint (0) | 2020.09.03 |
