Algorithm implementation of depth-first traversal and breadth-first traversal of tree in js

The content of this article is about the algorithm implementation of depth-first traversal and breadth-first traversal of tree in js. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

//Depth-first traversal

Algorithm description:

(1) Visit node v.

(2) Find the first adjacent point w of v.

(3) If the adjacent point w exists and has not been visited, start from w and traverse the graph depth-first; otherwise, end.

(4) Find the next adjacent point of vertex v with respect to w, and go to (3).

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

// Breadth-first traversal

Algorithm description:

(1) Assume that the initial state of graph G is that all vertices have not been visited, set auxiliary queue Q, queue Q Is empty.

(2) Select an unvisited vertex v as the starting point for traversal.

(3) Access v, put v into the queue, and mark v as visited.

(4) If the queue Q is not empty, take out a vertex v.

(5) Find all unvisited adjacent points vi of v and access them, merge them into the queue, and go to (4) until the queue is empty.

(6) If there are still unvisited nodes at this time, go to (2), otherwise end.

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();
}

Related recommendations:

JS traverses the key-value pairs in the Json string and first converts it to a JSON object and then traverses_javascript skills

JavaScript implements pre-order, in-order and post-order traversal methods of binary trees

The above is the detailed content of Algorithm implementation of depth-first traversal and breadth-first traversal of tree in js. For more information, please follow other related articles on the PHP Chinese website!