Rumah >hujung hadapan web >tutorial js >js中tree的深度优先遍历与广度优先遍历的算法实现
本篇文章给大家带来的内容是关于js中tree的深度优先遍历与广度优先遍历的算法实现,有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。
// 深度优先遍历
算法描述:
(1)访问结点v。
(2)找到v的第一个邻接点w。
(3)如果邻接点w存在且未被访问,则从w出发深度优先遍历图;否则,结束。
(4)找顶点v关于w的下一个邻接点,转(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对象再遍历_javascript技巧
Atas ialah kandungan terperinci js中tree的深度优先遍历与广度优先遍历的算法实现. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!