成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

廣度優(yōu)先和深度優(yōu)先

itvincent / 1959人閱讀

摘要：深度優(yōu)先遍歷和廣度優(yōu)先遍歷什么是深度優(yōu)先和廣度優(yōu)先其實(shí)簡單來說深度優(yōu)先就是自上而下的遍歷搜索廣度優(yōu)先則是逐層遍歷如下圖所示深度優(yōu)先廣度優(yōu)先兩者的區(qū)別對(duì)于算法來說無非就是時(shí)間換空間空間換時(shí)間深度優(yōu)先不需要記住所有的節(jié)點(diǎn)所以占用空間小而廣度優(yōu)先

深度優(yōu)先遍歷和廣度優(yōu)先遍歷

什么是深度優(yōu)先和廣度優(yōu)先

其實(shí)簡單來說 深度優(yōu)先就是自上而下的遍歷搜索 廣度優(yōu)先則是逐層遍歷, 如下圖所示

1.深度優(yōu)先

2.廣度優(yōu)先

兩者的區(qū)別

對(duì)于算法來說 無非就是時(shí)間換空間 空間換時(shí)間

深度優(yōu)先不需要記住所有的節(jié)點(diǎn), 所以占用空間小, 而廣度優(yōu)先需要先記錄所有的節(jié)點(diǎn)占用空間大
深度優(yōu)先有回溯的操作(沒有路走了需要回頭)所以相對(duì)而言時(shí)間會(huì)長一點(diǎn)

深度優(yōu)先采用的是堆棧的形式, 即先進(jìn)后出廣度優(yōu)先則采用的是隊(duì)列的形式, 即先進(jìn)先出

const data = [
    {
        name: "a",
        children: [
            { name: "b", children: [{ name: "e" }] },
            { name: "c", children: [{ name: "f" }] },
            { name: "d", children: [{ name: "g" }] },
        ],
    },
    {
        name: "a2",
        children: [
            { name: "b2", children: [{ name: "e2" }] },
            { name: "c2", children: [{ name: "f2" }] },
            { name: "d2", children: [{ name: "g2" }] },
        ],
    }
]

// 深度遍歷, 使用遞歸
function getName(data) {
    const result = [];
    data.forEach(item => {
        const map = data => {
            result.push(data.name);
            data.children && data.children.forEach(child => map(child));
        }
        map(item);
    })
    return result.join(",");
}

// 廣度遍歷, 創(chuàng)建一個(gè)執(zhí)行隊(duì)列, 當(dāng)隊(duì)列為空的時(shí)候則結(jié)束
function getName2(data) {
    let result = [];
    let queue = data;
    while (queue.length > 0) {
        [...queue].forEach(child => {
            queue.shift();
            result.push(child.name);
            child.children && (queue.push(...child.children));
        });
    }
    return result.join(",");
}

console.log(getName(data))
console.log(getName2(data))

作者：zwmmm
鏈接：https://juejin.im/post/5c4a96...
來源：掘金
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/106142.html

相關(guān)文章

  • 數(shù)據(jù)結(jié)構(gòu)與算法——廣度和深度優(yōu)先搜索

    摘要：今天就來看看基于圖的兩種搜索算法，分別是廣度優(yōu)先搜索和深度優(yōu)先搜索算法，這兩個(gè)算法都十分的常見，在平常的面試當(dāng)中也可能遇到。 1. 概論 前面說到了圖這種非線性的數(shù)據(jù)結(jié)構(gòu)，并且我使用了代碼，簡單演示了圖是如何實(shí)現(xiàn)的。今天就來看看基于圖的兩種搜索算法，分別是廣度優(yōu)先搜索和深度優(yōu)先搜索算法，這兩個(gè)算法都十分的常見，在平常的面試當(dāng)中也可能遇到。 在圖上面的搜索算法，其實(shí)主要的表現(xiàn)形式就是從圖...

    shmily 評(píng)論0 收藏0

  • 深度優(yōu)先搜索和廣度優(yōu)先搜索

    摘要：不撞南墻不回頭深度優(yōu)先搜索基礎(chǔ)部分對(duì)于深度優(yōu)先搜索和廣度優(yōu)先搜索，我很難形象的去表達(dá)它的定義。這就是深度優(yōu)先搜索了，當(dāng)然，這個(gè)題目我們還有別的解法，這就到了我們說的廣度優(yōu)先搜索。 不撞南墻不回頭-深度優(yōu)先搜索 基礎(chǔ)部分 對(duì)于深度優(yōu)先搜索和廣度優(yōu)先搜索，我很難形象的去表達(dá)它的定義。我們從一個(gè)例子來切入。 輸入一個(gè)數(shù)字n，輸出1~n的全排列。即n=3時(shí)，輸出123，132，213，231，...

    huaixiaoz 評(píng)論0 收藏0

  • JS算法之深度優(yōu)先遍歷(DFS)和廣度優(yōu)先遍歷(BFS)

    摘要：算法之深度優(yōu)先遍歷和廣度優(yōu)先遍歷背景在開發(fā)頁面的時(shí)候，我們有時(shí)候會(huì)遇到這種需求在頁面某個(gè)節(jié)點(diǎn)中遍歷，找到目標(biāo)節(jié)點(diǎn)，我們正常做法是利用選擇器，或者，但在本文，我們從算法的角度去查找節(jié)點(diǎn)，同時(shí)理解一下深度優(yōu)先遍歷和廣度優(yōu)先遍歷的原理。 JS算法之深度優(yōu)先遍歷(DFS)和廣度優(yōu)先遍歷(BFS) 背景 在開發(fā)頁面的時(shí)候，我們有時(shí)候會(huì)遇到這種需求：在頁面某個(gè)dom節(jié)點(diǎn)中遍歷，找到目標(biāo)dom節(jié)點(diǎn)，...

    roadtogeek 評(píng)論0 收藏0

  • 利用深度/廣度優(yōu)先遍歷手動(dòng)實(shí)現(xiàn)JavaScript對(duì)象的深度拷貝

    摘要：引言搜索對(duì)象的深度拷貝，往往會(huì)冒出轉(zhuǎn)換和遞歸拷貝大法。但遇到大數(shù)據(jù)量，它們都有調(diào)用棧爆棧的風(fēng)險(xiǎn)今天，我們嘗試?yán)脴涞睦蒙疃葟V度優(yōu)先遍歷來實(shí)現(xiàn)對(duì)象的深度拷貝。以下代碼在環(huán)境下全部測試通過。 引言 搜索JavaScript對(duì)象的深度拷貝，往往會(huì)冒出JSON轉(zhuǎn)換和遞歸拷貝大法。但遇到大數(shù)據(jù)量，它們都有調(diào)用棧爆棧的風(fēng)險(xiǎn)今天，我們嘗試?yán)脴涞睦蒙疃?廣度優(yōu)先遍歷來實(shí)現(xiàn)對(duì)象的深度拷貝。以下代碼...

    RobinTang 評(píng)論0 收藏0

  • 實(shí)現(xiàn)深度遍歷和廣度遍歷(遞歸與非遞歸版本)

    摘要：先畫個(gè)樹，然后解釋何為深度，何為廣度第一層子集第二層子集第二層子集第三層，子集第三層第四層圖就不畫太復(fù)雜了，最高四層的結(jié)構(gòu)，如果換成的形式的話可以理解成第一層第二層 先畫個(gè)樹，然后解釋 何為深度， 何為廣度 第一層 子集 | ...

    Betta 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

itvincent

男|高級(jí)講師

TA的文章

閱讀更多
最新活動(dòng)
閱讀需要支付1元查看
<