Graph
여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조
Vertax - 정점
Edge - 간선
직접적인 관계 - 두점사이를 이어주는 간선이 있다
간접적인 관계 - 몇개의 점과 선에 걸쳐 이어진다.
무(방)향 그레프 (undirected graph)
단방향 그레프
두개의 Vertax사이에 양쪽으로 Edge가 이어져 있는 것이 아닌 한쪽만 이어져 있는 경우
진입차수(id-degree) / 진출자수(out-degree)
함 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇개인지 나타낸다.
인접(adjacency)
두 정점 간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점이다.
자기루프(self loop)
정점에서 진출하는 간선이 곧 바로 자기 자신에게 집입하는 경우, 자기 루프를 가졌다 라고 표현한다.
다른 정점을 거치지 않는 다른 것이 특징이다.
사이클(Cycle)
한 정점에서 출발하여 다시 해당 정점으로 돌아 갈 수 있다면 사이클이 있다고 표현 한다.
ex) 네비게이션 (서울 -> 대전 -> 부산 -> 서울)
인접 행렬
서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열로 나타낸다.
- 두 정점 사이에 관계가 있는지, 없는지 확인 하기에 용이 하다.
ex) A에서 B로 진출하는 간선이 있는지 파악하기 위해선 0번째 줄의 1번째 열에 어떤 값이 저장 되어 있는 지 바로 확인 가능하다.
정점이 이어져 있다면 1
정점이 이어져 있지 않다면 0
// 그 외 true or false 등으로 표현할 수 있다
인접 리스트
각 정점이 어떤 점점과 인접한지를 리스트의 현태로 표현
각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담고 있다.
Graph를 인접리스트로 구현 할 때, 정점별로 살펴봐야 할 우선순위를 고려해 구현할 수 있다.
이때 리스트에 담겨진 정점들을 우선순위 별로 정렬할 수 있다.
우선 순위가 없다면, 연결된 정점들을 단순하게 나열한 리스트가 된다.
우선순위를 다뤄야 한다면 더 적합한 구조를 사용하는 것이 합리적이다.
따라서 보통은 중요하지 않다.
메모리를 효율적으로 사용하고 싶을때 인접리스트를 사용한다.
인접행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지 한다.
Tree
- 무방향 그래프 구조로 하나의 뿌리고 가지가 사바응로 뻗은 형태
- 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조
- 트리구조는 계층적으로 표현되고, 아래로만 뻗어 나가기 때문에 사이클이 없다
Tree 자료구조는 깊이와 높이, 레벨 등을 측정할 수 있다.
- 깊이 (depth)
트리구조에서는 루트로 부터 하위 계층의 특정 노드까지의 깊이(depth)를 표현할 수 있다.
- 레벨 (level)
같은 깊이를 가지고 있는 노드를 묶어서 레벨로 표현할 수 있다.
같은 레벨을 나란히 있는 노드를 현제 노드(sibling Node)라고 한다.
- 높이 (height)
트리구조에서 리프노드를 기준으로 루트까지의 높이를 표현할 수 있다.
- 서브트리 (sub tree)
큰 트리 내부에 작은 트리 구조를 갖춘 것
ex) 컴퓨터 디렉토리 구조, 대진표, 가계도, 조직도
자료구조는 자료의 집합을 구조화 하고, 이를 표현하는 데에 초점이 맞춰져 있다.
사람이 사용하기에 편리하고, 사용하기 좋으려고 만들어진 것이 자료구조이다.
트리구조는 편리한 구조를 전시하는 것 외에 효율적인 탐색을 위해 사용한다.
이진트리(binary tree) // 이진탐색트리(binary search tree)
자식노드가 최대 두개인 노드들로 구성된 트리
정이진트리 (Full binary tree)
각 노드가 0개 혹은 2개의 자식노드를 갖는다
포화이진트리 (Perfect binary tree)
정이진 트리이면서 완전 이진트리인 경우
모든 리프 레벨이 동일하고, 모든 레벨이 가득 채워져 있다는 트리
완전이진트리 (Complete binary tree)
마지막 레벨을 제외한 모든 노드가 가득차 있어야 하고, 마지막 레벨의 노드는 전부 차있지 않아도 왼쪽이 채워져 있어야 한다.
이진탐색트리 (Binary Search Tree)
이진탐색트리는 모든 왼쪽 자식의 값이 루트나 부모보다 작고 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징이 있다.
트리 순회 (Tree Traversal)
- 특정 목적을 위해 트리의 모든 노드를 한번씩 방문 하는 것
- 트리 구조는 계층적구조라는 특별한 특징을 가지고 있다.
- 전위, 중위, 후위 순회시 트리구조에서는 노드를 순차적으로 조회 할 때의 순서는 항상 왼쪽부터 오른쪽이다.
전위 순회 (preoder)
가장 먼저 root를 방문 -> root를 시작으로 왼쪽의 노드들을 순차적으로 둘러 본 뒤 -> 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색 한다.
중위 순회 (inoder)
- root를 가운데 두고 순회 한다
- 제일 왼쪽의 노드부터 순회하기 시작 -> root 기준으로 왼쪽의 노드의 순회가 끝나면 루트를 거쳐 오른쪽의 노드를 이동하여 마저 탐색
후위 순회 (postoroder)
- root를 가장 마지막에 순회
제일 왼쪽 끝에 있는 노드부터 순회 -> 루트를 거치지 않고 오른쪽으로 이동해 순회한 뒤 -> 제일 마지막 로트를 방문
BFS / DFS
- 그래프 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한번씩 방문(탐색) 하는 것이 목적이다.
- 그래프의 데이터는 배열처럼 정렬이 되어 있지 않다. 그래서 원하는 자료를 찾으려면 하나씩 모두 방문하여 찾아야 한다.
BFS (Breadth - First Search) / 너비우선탐색
주로 두 정점 사이의 최단 경로를 찾을 때 사용한다. 만약 경로를 하나씩 전부 방문 한다면 최악의 경우에는 모든 경로를 다 살펴 보아야 한다.
ex) 추가로 넣을 예정
DFS (Depth - First Search) / 깊이 우선 탐색
- 깊이를 우선적으로 탐색 하는 방법
- 한 정점에서 시작해서 다음 경로로 넘어가기전에 해당 경로를 완벽하게 탐색할 때 사용
- BFS보다 탐색시간은 조금 오래 걸릴 지라도 모든 노드를 완벽하게 탐색할 수 있다.
- 만약 BFS로 탐색하게 된다면 제일 첫번째 경로가 미국 행이라도 다른 모든 경로를 살펴 보아야 한다.
ex) 추가로 넣을 예정
DFS와 BFS는 모든 정점을 한번만 방문한다는 공통점을 가지고 있지만, 사용할때의 장단점은 분명하기 때문에 해당 상황에 맞는 탐색 기법을 사용해야 한다.
Class 키워드를 이용한 Graph / Tree 구현
GithupTIL
