자바스크립트로 구현한 Tree, BFS, DFS

자바스크립트로 구현한 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']

출처 : https://jun-choi-4928.medium.com/javascript%EB%A1%9C-%ED%8A%B8%EB%A6%AC-bfs-dfs-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0-e96bcdadd1f3

JavaScript로 트리, BFS, DFS 구현하기

 

그래프로 구현한 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 ]