js에서 트리의 깊이 우선 순회 및 너비 우선 순회 알고리즘 구현

이 글의 내용은 js에서 트리의 깊이 우선 순회와 너비 우선 순회 알고리즘 구현에 관한 것입니다. 필요한 친구들이 참고할 수 있기를 바랍니다.

// 깊이 우선 탐색

알고리즘 설명:

(1) 노드 v를 방문하세요.

(2) v의 첫 번째 인접점 w를 찾습니다.

(3) 인접 지점 w가 존재하고 방문하지 않은 경우 w에서 시작하여 그래프 깊이부터 탐색하고 그렇지 않으면 끝납니다.

(4) w를 기준으로 정점 v의 다음 인접점을 찾고 (3)으로 이동합니다.

function dfs (node) {
console.log(node); // 访问node
for(var i=0;i<node.children.length;i++) {
dfs(node.children[i]);
}
}

//너비 우선 순회

알고리즘 설명:

(1) 그래프 G의 초기 상태가 모든 정점을 방문하지 않은 것이라고 가정하고 보조 큐 Q를 설정하고 큐 Q가 비어 있습니다.

(2) 방문하지 않은 정점 v를 순회 시작점으로 선택합니다.

(3) v를 방문하여 v를 대기열에 넣고 v를 방문한 것으로 표시합니다.

(4) 큐 Q가 비어 있지 않으면 정점 v를 꺼냅니다.

(5) v의 방문하지 않은 모든 인접 점 vi를 찾아 액세스하고 큐에 병합한 후 큐가 빌 때까지 (4)로 이동합니다.

(6) 이때 아직 방문하지 않은 노드가 있으면 (2)로 이동하고, 그렇지 않으면 종료합니다.

var visited = []; // 访问过的
var arr = []; // 辅助队列,记录本层遍历的
var nextRound = []; // 下一层需要的遍历
function bfs () {
arr = nextRound;
nextRound = [];
for(var i=0;i<arr.length;i++) {
visited.push(arr[i]); // 访问arr[i]
for(var j=0;j<arr[i].children.length;i++) {
nextRound.push(arr[i].children[j]);
}
}
}
while(nextRound.length) {
bfs();
}

관련 권장 사항:

JS는 Json 문자열의 키-값 쌍을 순회하고 먼저 이를 JSON 객체로 변환한 다음 traverse_javascript 기술

JavaScript는 선주문, 순차 및 후순 순회를 구현합니다. 이진 트리의 방법

위 내용은 js에서 트리의 깊이 우선 순회 및 너비 우선 순회 알고리즘 구현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!