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技巧

#JavaScript實作二元樹的先序、中序及後序遍歷方法

以上是js中tree的深度優先遍歷與廣度優先遍歷的演算法實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！