[etc] DFS , BFS
DFS - 깊이 우선 탐색 -statck
현재 정점에서 한 방향으로 가면서 검사하기
막힌 정점은 포기하고 마지막에 따라온 간선으로 되돌아감.
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
가까운 정점을 먼저 방문, 먼정점은 나중에 방문