ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 자바스크립트로 구현한 Tree, BFS, DFS
    프론트엔드/자료구조 알고리즘 2022. 3. 12. 01:07
    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

    bfs, dfs

    출처 : 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 구현하기

    이제는 정리하고 넘어가야 할 때가 되었다.

    jun-choi-4928.medium.com

     

    그래프로 구현한 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
Designed by Tistory.