廣度優先和深度優先

itvincent 發布于2019-08-26 10:25 / 1948人閱讀

摘要：深度優先遍歷和廣度優先遍歷什么是深度優先和廣度優先其實簡單來說深度優先就是自上而下的遍歷搜索廣度優先則是逐層遍歷如下圖所示深度優先廣度優先兩者的區別對于算法來說無非就是時間換空間空間換時間深度優先不需要記住所有的節點所以占用空間小而廣度優先

深度優先遍歷和廣度優先遍歷

什么是深度優先和廣度優先

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

1.深度優先

2.廣度優先

兩者的區別

對于算法來說無非就是時間換空間空間換時間

深度優先不需要記住所有的節點, 所以占用空間小, 而廣度優先需要先記錄所有的節點占用空間大
深度優先有回溯的操作(沒有路走了需要回頭)所以相對而言時間會長一點

深度優先采用的是堆棧的形式, 即先進后出廣度優先則采用的是隊列的形式, 即先進先出

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

// 廣度遍歷, 創建一個執行隊列, 當隊列為空的時候則結束
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...
來源：掘金
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

云服務器 GPU云服務器廣度優先遍歷廣度優先搜索 python廣度優先廣度優先搜索算法代碼

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/106142.html

數據結構與算法——廣度和深度優先搜索

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

shmily 2019-08-16 16:13 評論0 收藏0
深度優先搜索和廣度優先搜索

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

huaixiaoz 2019-07-31 10:02 評論0 收藏0
JS算法之深度優先遍歷(DFS)和廣度優先遍歷(BFS)

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

roadtogeek 2019-08-23 16:33 評論0 收藏0
利用深度/廣度優先遍歷手動實現JavaScript對象的深度拷貝

摘要：引言搜索對象的深度拷貝，往往會冒出轉換和遞歸拷貝大法。但遇到大數據量，它們都有調用棧爆棧的風險今天，我們嘗試利用樹的利用深度廣度優先遍歷來實現對象的深度拷貝。以下代碼在環境下全部測試通過。引言搜索JavaScript對象的深度拷貝，往往會冒出JSON轉換和遞歸拷貝大法。但遇到大數據量，它們都有調用棧爆棧的風險今天，我們嘗試利用樹的利用深度/廣度優先遍歷來實現對象的深度拷貝。以下代碼...

RobinTang 2019-08-26 10:36 評論0 收藏0
實現深度遍歷和廣度遍歷(遞歸與非遞歸版本)

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

Betta 2019-08-26 10:09 評論0 收藏0