資訊專欄INFORMATION COLUMN
摘要：增加刪除獲取隊(duì)首元素是否為空以上就實(shí)現(xiàn)了隊(duì)列的數(shù)據(jù)結(jié)構(gòu)，那么隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)有什么作用呢在廣度優(yōu)先搜索中，很適合隊(duì)列。隊(duì)列可以用在中，下面我們來實(shí)現(xiàn)一個(gè)廣度優(yōu)先搜索的例子，返回目標(biāo)節(jié)點(diǎn)深度。
隊(duì)列是先進(jìn)先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)，插入操作叫做入隊(duì)，只能添加在隊(duì)列的末尾；刪除操作叫做出隊(duì)，只能移除第一個(gè)元素。在JS中，用數(shù)組可以很簡(jiǎn)單的實(shí)現(xiàn)隊(duì)列。
function Queue () {
this.queue = [];
}
// 增加
Queue.prototype.enQueue = function(x) {
this.queue.push(x);
return true;
}
// 刪除
Queue.prototype.deQueue = function() {
if(this.isEmpty()) {
return false;
}
this.queue.shift();
return true;
}
// 獲取隊(duì)首元素
Queue.prototype.front = function() {
if(this.isEmpty()) {
return false;
}
this.queue[0];
}
// 是否為空
Queue.prototype.isEmpty = function() {
return !this.queue.length
}
以上就實(shí)現(xiàn)了隊(duì)列的數(shù)據(jù)結(jié)構(gòu)，那么隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)有什么作用呢？在廣度優(yōu)先搜索（BFS）中，很適合隊(duì)列。那什么是BFS。在樹的遍歷中，有兩種遍歷方式，其中一種就是從根節(jié)點(diǎn)一層一層的往下遍歷，這就是廣度優(yōu)先；另一種是先由根節(jié)點(diǎn)選一條路徑直接遍歷到葉子節(jié)點(diǎn)，這就是深度優(yōu)先搜索（DFS）。隊(duì)列可以用在BFS中，下面我們來實(shí)現(xiàn)一個(gè)廣度優(yōu)先搜索的例子，返回目標(biāo)節(jié)點(diǎn)深度。
let root = {
key: 1,
children: [
{
key:2,
},
{
key:3,
children:[
{
key:4,
}
]
}
]
} // 數(shù)據(jù)源
function bfs(root, target) {
//利用上面創(chuàng)建的Queue，當(dāng)然也可以直接用數(shù)組實(shí)現(xiàn)
let queue = new Queue();
let step = 0; // 根節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)之間的深度
queue.enQueue(root); //將根節(jié)點(diǎn)加入
//遍歷隊(duì)列
while(!queue.isEmpty()) {
step += 1;
let len = queue.length;
// 分層遍歷隊(duì)列，沒有目標(biāo)元素則刪除該層元素，繼續(xù)遍歷下一層
for(let i =0; i {
queue.enQueue(item)
})
}
queue.deQueue() //然后將遍歷過的節(jié)點(diǎn)刪除，
}
}
}
bfs(root,4)
這樣我們就完成了BFS的實(shí)現(xiàn)思路，大家可已參照該思路在具體的業(yè)務(wù)中靈活運(yùn)用BFS。
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/98967.html
1. 說明 本文所有的算法嚴(yán)格按照《算法導(dǎo)論》，本文將詳細(xì)的對(duì)BFS和DFS進(jìn)行分析，并提供算法的 js 實(shí)現(xiàn)，同時(shí)會(huì)對(duì)創(chuàng)建鏈表的方式進(jìn)行優(yōu)化 2. 圖的表示 圖的表示分為對(duì)頂點(diǎn)集 V 的表示和對(duì)邊集 E 的表示，這里的重點(diǎn)是如何表示邊，邊的表示分為鄰接矩陣和鄰接鏈表這兩種表示方法，鄰接矩陣適合表示邊稠密的圖，其消耗空間為|V|*|V|,如果是無向圖，則可以用上三角矩陣或者下三角矩陣來表示，是空間...
摘要：隊(duì)列棧隊(duì)列是先進(jìn)先出，后進(jìn)后出，常用的操作是取第一個(gè)元素尾部加入一個(gè)元素。棧是后進(jìn)先出，就像一個(gè)垃圾桶，后入的垃圾先被倒出來。遍歷中間過程，每一個(gè)節(jié)點(diǎn)入棧的時(shí)候是灰色的，出棧的時(shí)候是黑色的。 0. 前言 廣度優(yōu)先搜索(BFS)和深度優(yōu)先搜索(DFS)，大家可能在oj上見過，各種求路徑、最短路徑、最優(yōu)方法、組合等等。于是，我們不妨動(dòng)手試一下js版本怎么玩。 1.隊(duì)列、棧 隊(duì)列是先進(jìn)先出，...
摘要：散列表上面的地圖向我們展示了如何用廣度優(yōu)先搜索的思想找到北京到廣州的最短路線。在廣度優(yōu)先搜索中，我們需要用到隊(duì)列的這種思想來實(shí)現(xiàn)查找。建立了下面這個(gè)模型武漢廣州西藏上海上海武漢廣州代碼完整實(shí)現(xiàn)，利用遞歸和廣度優(yōu)先搜索的思想實(shí)現(xiàn)。 什么是廣度優(yōu)先搜索？ 如果只是是背概念，幼兒園的小朋友都能背下來念給你聽。 假設(shè)看這篇文章的都和我一樣是個(gè)前端工程師，我們要從廣度優(yōu)先搜索（BFS）中學(xué)到什么...
摘要：鄰接矩陣在鄰接矩陣實(shí)現(xiàn)中，由行和列都表示頂點(diǎn)，由兩個(gè)頂點(diǎn)所決定的矩陣對(duì)應(yīng)元素表示這里兩個(gè)頂點(diǎn)是否相連如果相連這個(gè)值表示的是相連邊的權(quán)重。直到返回到頂點(diǎn)完成探索具體還有版的深度和廣度優(yōu)先的算法，具體代碼奉上直達(dá)地址 圖github直達(dá)地址 https://github.com/fanshyiis/... 在計(jì)算機(jī)科學(xué)中，一個(gè)圖就是一些頂點(diǎn)的集合，這些頂點(diǎn)通過一系列邊結(jié)對(duì)（連接）。頂點(diǎn)用圓...
閱讀 3717·2023-04-26 00:56
閱讀 2706·2021-09-30 10:01
閱讀 974·2021-09-22 15:30
閱讀 3934·2021-09-07 10:21
閱讀 1541·2021-09-02 15:40
閱讀 2774·2021-08-30 09:47
閱讀 1256·2021-08-16 10:57
閱讀 1874·2019-08-30 14:01
