[etc] DFS , BFS


DFS - 깊이 우선 탐색 -statck

현재 정점에서 한 방향으로 가면서 검사하기

막힌 정점은 포기하고 마지막에 따라온 간선으로 되돌아감.

img


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 방문 = [];
 let stack = [start];

 while(stack){
    let n = 0 ; // 다음 방문할 노드

    n = stack.pop();
    if( !방문.includes(n) ){
        방문.push(n);
        let 차집합 = new Set( [...graph[n]].filter(function(data){
            if( 방문.indexOf(data) == -1 ) return data;
        }) );

        for( var v of 차집합){
            stack.push(v)
        };
        console.log(`방문 : ${방문}`)
        console.log(`stack : ${stack}`)
    }
    if( stack.length == 0 ){
        break;
    }
    
 }
 return 방문;
}


console.log( DFS_(graph , 100 ))

BFS - 너비우선탐색 - Queue

가까운 정점을 먼저 방문, 먼정점은 나중에 방문




© 2017. by isme2n