前端的數據結構與算法（1）-- dfs

hizengzeng 發布于2019-08-21 11:54 / 2174人閱讀

摘要：前端在開發過程中接觸到的算法最多的莫過于排序和深度優先遍歷。關于算法的遍歷過程，我簡略的畫了一個示例圖實例最近在實際業務場景中，跟后端約定頁面中所有組件的消息根據頁面上的組件聚合到一個對象中，后端返回的是類似如下的一個樹形數據結構。

dfs

前端在開發過程中接觸到的算法最多的莫過于排序和 dfs(深度優先遍歷) 。 dfs 算法廣泛用于圖（樹是圖的一種）的遍歷，如：沒有 querySelectorAll 的時候，根據 classname 或者 tag 查找 element。

關于 dfs 算法的遍歷過程，我簡略的畫了一個示例圖：

實例：

最近在實際業務場景中，跟后端約定頁面中所有組件的消息根據頁面上的組件 id 聚合到一個對象中，后端返回的是類似如下的一個樹形數據結構。前端需要把所有的錯誤信息都拿出來，按照頁面上所有組件的順序聚合顯示在一個全局信息面板組件上（至于按照組件順序排序算法本文暫且略過）

let tree = {
    "id1": {
        message: "hello"
    },
    "id2": {
        message: "world",
        children: {
          "id2-1": {
              message: "haha",
              children: {
              }
          },
          "id2-2": {
              message: "heihei"
          }
        }
    }
}

由于某些大組件可能是由多個小組件層層嵌套組合而來，且每個小組件都有相應的 message 需要展示，所以就選擇了上述的樹形結構來表達組件的信息。這個時候就會有人問，為什么不讓后端把所有 message 都聚合到數組里面？因為前端不僅需要把這些錯誤信息聚合到一起展示，也需要把錯誤定位到具體組件上

遞歸版本實現

function dfs(tree = {}, messages = []) {
    let i = 0;
    if(!messages) messages = [];
    if(tree.message) messages.push(tree.message);
    
    const keys = Object.keys(tree.children || {});
    while (i < keys.length) {
        dfs(tree.children[keys[i]], messages);
        i += 1;
    }
    return messages;
}

 tree = {
    message: null,
    children: tree
 };  
 
 dfs(tree);

非遞歸版本實現

  function dfs(tree = {}) {
    const array = [tree];
    let messages = [];
    while (array.length) {
      const top = array.pop();
      if (top.message) {
        messages.push(top.message);
      }
      const keys = Object.keys(top.children || {});
      let i = keys.length;
      while (i > 0) {
        i -= 1;
        array.push(top.children[keys[i]]);
      }
    }
    return messages
  }
  
 tree = {
    message: null,
    children: tree
 };  
 
 dfs(tree);

在實際使用中，考慮到數據結構的層數沒那么多，其實尾遞歸版本和非遞歸版本所消耗的時間在瀏覽器的優化下幾乎可忽略了。

GPU云服務器云服務器矩陣dfs算法描述的數據結構與算法 dfs生存分析需要的數據 php與前端的交互

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

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

算法（第4版） Chapter 4.2 有向圖

摘要：只好特地拎出來記錄證明一下算法步驟第一步在逆圖上運行，將頂點按照逆后序方式壓入棧中顯然，這個過程作用在有向無環圖上得到的就是一個拓撲排序作用在非上得到的是一個偽拓撲排序第二步在原圖上按第一步的編號順序進行。等價于已知在逆圖中存在有向路徑。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslat...

曹金海 2019-08-14 17:13 評論0 收藏0
PHP面試：常見查找算法一篇說透

摘要：我們現在來看二分搜索算法的兩種變形插值搜索和指數搜索。插值搜索是對二分搜索算法的改進，插值搜索可以基于搜索的值選擇到達不同的位置。預警在本篇文章中，將為各位老鐵介紹不同的搜索算法以及它們的復雜度。因為力求通俗易懂，所以篇幅可能較長，大伙可以先Mark下來，每天抽時間看一點理解一點。本文配套的Github Repo，歡迎各位老鐵star，會一直更新的。開篇和排序類似，搜索或者叫做...

付永剛 2019-07-01 10:47 評論0 收藏0
隨機生成指定面積單連通區域

摘要：原文鏈接最近在知乎上看到一個問題，隨機生成指定面積單連通區域，感覺還挺有意思的，于是整理一下寫一篇新文章。問題闡述如下圖所示，在的區域中，隨機生成面積為的單連通區域，該隨機包括位置隨機以及形狀隨機。原文鏈接：https://xcoder.in/2018/04/01/random-connected-area/ 最近在知乎上看到一個問題，「隨機生成指定面積單連通區域？」，感覺還挺有意...

zhoutk 2019-08-22 16:00 評論0 收藏0
算法（第4版） Chapter 4.1 無向圖

摘要：邊僅由兩個頂點連接，并且沒有方向的圖稱為無向圖。用分隔符當前為空格，也可以是分號等分隔。深度優先算法最簡搜索起點構造函數找到與起點連通的其他頂點。路徑構造函數接收一個頂點，計算到與連通的每個頂點之間的路徑。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 謝路云Chapter...

kamushin233 2019-08-14 17:14 評論0 收藏0