1. 그래프
트리는 그래프의 한 종류이며 그래프는 방향과 들어오는 입구에 제약이 없다.
- Directed : 방향이 있는
- Undirected : 방향이 없는
- cyclic: 하나 이상의 순환을 갖고 있는
- Acyclic: 순환이 없는
2. Graph를 표현하는 방법
- Adjacency Matrix : 이차원 배열
- Adjacency List: 노드 & 링크드로 연결
3. 그래프 검색
3.1 깊이우선검색(DFS: Depth-First Search)
기본개념
깊이우선탐색은 자식들이 우선순위이다. 부모로 부터 자식까지 아래로 쭉 훑고, 그 옆의 부모 노드로 방문이 넘어가게 된다.
회사 조직도에서 깊이우선탐색은 부서 단위라고 보면 좋을 것 같다. 회사의 조직도에서 사장 다음에 영업부서, 개발부서, 디자인부서가 있다고 한다면, 각각의 부서에서는 부장-대리-사원이 있다. 이 회사의 구성원들을 깊이우선탐색으로 이름을 나열하면, 영업부서의 부장-대리-사원, 개발부서의 부장-대리-사원, 디자인부서의 부장-대리-사원 순으로 이름이 나열될 것이다.
순회방법
- inorder
- preorder
- postorder
재귀호출을 하면 깔끔하다.
3.2 넓이우선검색(BFS: Breadth-First Search)
기본개념
너비(=층)의 순서대로 정보를 확인한다. 트리의 가장 최상위 부모부터 자식들의 정보가 궁금할 때 사용한다. 트리 자료구조가 사용되는 일상의 또 다른 예로는 회사의 사내 조직도 인데, 가장 높으신 분(?) 으로 부터 일반 평사원까지의 정보를 알고 싶다면, 층을 따라서 위에서 부터 아래로 내려오면 된다. 사장-부장-대리-사원 이런식으로 층을 따라 사장, 부장, 대리, 이름을 쭉 나열하고, 그 다음 평사원의 이름을 쭉 나열하면 된다. 탐색을 하는데 있어서 우선순위가 너비=층 이 된다는 것이 핵심이다.
4. 검색 방법
5. 코드
5.1 그래프
class Node {
constructor(data) {
this.data = data; // 다른 노드와 차별점을 두는 데이터
this.children = []; // 자식들과의 정보(주소)를 담을 배열
}
add(data) { // 자식 추가하는 메소드
this.children.push(new Node(data)); // 자식 노드를 생성하고 바로 배열에 저장한다. (주소를 저장하는 행위)
}
remove(data) { // 자식의 정보를 지우는 메소드
this.children = this.children.filter(child => child.data === data ? false : true); // filter 를 거쳐서 해당하는 자식의 정보를 배열에서 빼주면 된다.
}
}
class Tree() {
constructor() {
this.root = null;
}
}
const t = new Tree(); // 빈 트리를 생성 해 주고
t.root = new Node('a'); // 루트가 node 'a'의 주소를 가리키면 'a' 의 자식들까지 접근 가능하다.
t.root.add('b'); // a의 자식 'b', 'c'
t.root.add('c');
t.root.children[0].add('d'); // 'b' 의 자식으로 'd'가 추가된다.5.2 DFS
class Tree {
constructor() {
this.root = null;
}
DFS(fn) {
if(this.root === null) return;
const unvisitedList = [this.root];
while(unvisitedList.length !== 0) {
const current = unvisitedList.shift();
unvisitedList.unshift(...current.children); // list 앞에다 넣어준다. (우선순위: 내 자식들이 먼저야! )
fn(current);
}
}
}5.3 BFS
class Tree{
constructor() {
this.root = null;
}
BFS(fn) { // 인자로 callback 함수를 받는다.
if(this.root === null) return;
const unvisitedQueue = [this.root];
while(unvisitedQueue.length !== 0){
const current = unvisitedQueue.shift(); // dequeue
unvisitedQueue.push(...current.children); // 현재 부모 노드의 자식들을 모두 다 큐에 담는다.
fn(current); // 현재 노드를 가지고 callback 함수 실행
}
}
}5.4 실행코드
const lettersBFS = [];
const lettersDFS = [];
const t = new Tree();
t.root = new Node('a');
t.root.add('b');
t.root.add('d');
t.root.children[0].add('c');
t.BFS(node => lettersBFS.push(node.data));
t.DFS(node => lettersDFS.push(node.data));5.5 결과
삭제 관련해서는 추후에 알아보겠다.
DFS 출력할 때 방문체크 / BFS Queue에 넣을 때 방문 체크
참고자료
멋진 프론트엔드 개발자를 위하여!