728x90
자바스크립트로 구현한 Tree, BFS, DFS
Tree
class Node{
constructor(data){
this.data = data; //노드의 정보
this.children = []; // 자식'노드'가 들어있는 배열
}
addChild(data){
this.children.push(new Node(data));
}
removeChild(data){
this.children = this.children.filter(child => child.data === data ? false: true);
}
}
class Tree{
constructor(){
this.root = null; // root도 노드이다.
}
}
const t = new Tree();
t.root = new Node('a');
t.root.addChild('b');
t.root.addChild('c');
t.root.children[0].addChild('d');
위의 결과로 아래와 같은 tree가 만들어진다.
// Tree
{
root:{
data:'a',
children:[
{
data:'b',
children:[
{
data:'d',
children:[]
}
]
},
{
data:'c',
children:[]
}
]
}
}
그래프탐색 알고리즘 BFS, DFS
너비 우선 탐색(Breadth First Search)
한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들(형제 노드들)을 먼저 순회함
A-B-C-D-G-H-I-E-F-J
깊이 우선 탐색(Depth First Search)
한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타고 내려가면서 순회함
A-B-D-E-F-C-G-H-I-J
출처 : https://saegeullee.github.io/algorithm/bfs-dfs
자바스크립트로 구현한 BFS
class Node{
constructor(data){
this.data = data; //노드의 정보
this.children = []; // 자식'노드'가 들어있는 배열
}
addChild(data){
this.children.push(new Node(data));
}
removeChild(data){
this.children = this.children.filter(child => child.data === data ? false: true);
}
}
class Tree{
constructor(){
this.root = null; // root도 노드이다.
}
BFS(){ // unvisitedQueue 큐와 visitedQueue 큐, 두 개의 큐를 활용하여 알고리즘을 구현한다.
if(this.root === null) return;
const unvisitedQueue = [this.root];
const visitedQueue = [];
while(unvisitedQueue.length !== 0){
const current = unvisitedQueue.shift(); // dequeue
unvisitedQueue.push(...current.children); // 형제 뒤에 자식들을 넣는다.
visitedQueue.push(current.data);
}
return visitedQueue;
}
}
const t = new Tree();
t.root = new Node('a');
t.root.addChild('b');
t.root.addChild('c');
t.root.children[0].addChild('d');
t.BFS(); //['a', 'b', 'c', 'd']
자바스크립트로 구현한 DFS
class Node{
constructor(data){
this.data = data; //노드의 정보
this.children = []; // 자식'노드'가 들어있는 배열
}
addChild(data){
this.children.push(new Node(data));
}
removeChild(data){
this.children = this.children.filter(child => child.data === data ? false: true);
}
}
class Tree{
constructor(){
this.root = null; // root도 노드이다.
}
DFS(){ // unvisitedStack 스택과 visitedQueue 큐, 스택과 큐 한개씩을 사용하여 알고리즘을 구현한다.
if(this.root === null) return;
const unvisitedStack = [this.root];
const visitedQueue = [];
while(unvisitedStack.length !== 0){
const current = unvisitedStack.shift();
unvisitedStack.unshift(...current.children); // 자식들을 앞에 넣는다.
visitedQueue.push(current.data);
}
return visitedQueue;
}
}
const t = new Tree();
t.root = new Node('a');
t.root.addChild('b');
t.root.addChild('c');
t.root.children[0].addChild('d');
t.DFS();//['a', 'b', 'd', 'c']
그래프로 구현한 DFS
var graph = {100: new Set([67, 66]),
67: new Set([100, 82, 63]),
66: new Set([100, 73, 69]),
82: new Set([67, 61, 79]),
63: new Set([67]),
73: new Set([66]),
69: new Set([66, 65, 81]),
61: new Set([82]),
79: new Set([82, 87, 77]),
65: new Set([69, 84, 99]),
81: new Set([69]),
87: new Set([79, 31, 78]),
77: new Set([79]),
84: new Set([65]),
99: new Set([65]),
31: new Set([87]),
78: new Set([87])};
function dfs(graph, start){
let visit = [];
let stack = [start];
while(stack){
let n = 0;
n = stack.pop();
if(!visit.includes(n)){
visit.push(n);
let minus_set = new Set([...graph[n]].filter(x => !(new Set(visit).has(x))));
for (var v of minus_set){
stack.push(v);
}
}
if(stack.length == 0){
break;
}
}
return visit
}
console.log(dfs(graph, 100));
//[100, 66, 69, 81, 65, 99, 84, 73, 67, 63, 82, 79, 77, 87, 78, 31, 61]
최대값을 찾는 DFS
function dfs_max(graph, start){ // 깊이 우선 탐색 최대값을 찾아라
let visit = [];
let stack = [start];
while(stack){
let n = 0;
n = stack.pop();
if(!visit.includes(n)){
visit.push(n);
let minus_set = new Set([...graph[n]].filter(x => !(new Set(visit).has(x))));
if([...minus_set].length == 0){
break;
}
stack.push(Math.max(...minus_set));
}
if(stack.length == 0){
break;
}
}
return visit
}
console.log(dfs_max(graph, 100));
// [ 100, 67, 82, 79, 87, 78 ]
최소값을 찾는 DFS
function dfs_min(graph, start){ // 깊이 우선 탐색 최소값을 찾아라
let visit = [];
let stack = [start];
while(stack){
let n = 0;
n = stack.pop();
if(!visit.includes(n)){
visit.push(n);
let minus_set = new Set([...graph[n]].filter(x => !(new Set(visit).has(x))));
if([...minus_set].length == 0){
break;
}
stack.push(Math.min(...minus_set));
}
if(stack.length == 0){
break;
}
}
return visit
}
console.log(dfs_min(graph, 100));
//[ 100, 66, 69, 65, 84 ]
728x90
'프론트엔드 > 자료구조 알고리즘' 카테고리의 다른 글
자바스크립트로 구현한 Max Heap (0) | 2022.03.12 |
---|---|
자바스크립트로 구현한 hash table (0) | 2022.03.11 |
단일연결리스트로 구현한 Stack, Queue (0) | 2022.03.10 |