js에서 트리의 깊이 우선 순회 및 너비 우선 순회 알고리즘 구현-JS 튜토리얼-php.cn

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

不言

풀어 주다： 2018-08-20 14:50:15

원래의

3307명이 탐색했습니다.

이 글의 내용은 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();
}

로그인 후 복사