js實作深度優先搜索(DFS)和廣度優先搜索(BFS)-有解無憂

深度優先搜索（DFS）

首先構造一個我們需要遍歷的結構，這里用html演示

<div id="root">
      <p></p>
      <label></label>
      <ul>
          <li>
              <span></span>
          </li>
          <li></li>
          <li>
              <a href="">
                  <img src="" alt="">
              </a>
          </li>
      </ul>
</div>

用圖表示的話就是這樣

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-rnz6pDIq-1617634866638)(/Users/yinlu/Documents/截屏/DFS.png)]

其實這個方法就是從根節點開始，一直遍歷他的子節點，直到他的子節點被遍歷完畢，才去遍歷他的兄弟節點，以此類推

核心演算法如下：

function DFS(node) {
        let nodes = []
        if (node !== null) {
            let stack = []
            stack.push(node)
            while (stack.length !== 0) {
                let item = stack.pop()
                nodes.push(item)
                let children = item.children
                for (let i = children.length - 1; i >= 0; i--) {
                    stack.push(children[i])
                }
            }
            return nodes
      }
}

演算法講解：

nodes:[ ] -> [div] -> [div, p] ->[div, p, label] -> [div, p, label, ul] -> [div, p,label, ul, li] -> [div, p, label, ul, li, span] -> [div, p, label, ul, li, span, li] ->[div, p, label, ul, li, span, li, li] -> [div, p, label, ul, li, span, li, li, a] -> [div, p, label, ul, li, span, li, li, a, img]

stack:[ ] -> [div] -> [ul, label, p] -> [ul, label] -> [ul] -> [li, li, li] ->[li, li,span] ->[li, li] -> [li] -> [a] -> [img] -> [ ]

item: div -> p -> label -> ul -> li -> span -> li -> li -> a -> img

結果：

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-UfVKqgLk-1617634866641)(/Users/yinlu/Documents/截屏/截屏2021-04-05 下午9.56.08.png)]

廣度優先搜索（BFS）

還是以上html結構，用圖表示廣度優先搜索的話就是這樣

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-MYfERV5g-1617634866642)(/Users/yinlu/Documents/截屏/BFS.png)]

這個方法就是從根節點的第一個子節點開始，先遍歷他所有的兄弟節點，然后在遍歷第一個節點的子節點，完成該遍歷后，暫時不深入，繼續遍歷其兄弟節點的子節點，以此類推，

核心演算法如下：

function BFS(node) {
        let nodes = []
        if (node != null) {
            let queue = []
            queue.unshift(node)
            while (queue.length != 0) {
                let item = queue.shift()
                nodes.push(item)
                let children = item.children
                for (let i = 0; i < children.length; i++) {
                    queue.push(children[i])
                }
            }
        }
        return nodes
}

演算法講解：

nodes[ ]: [ ] -> [div] -> [div, p] -> [div, p, label] -> [div, p, label, ul] -> [div, p, label, ul, li] -> [div, p, label, ul], li, li] -> [div, p, label, ul, li, li, li] -> [div, p, label, ul, li, li, li, span] -> [div, p, label, ul, li, li, li, span, a] -> [div, p, label, ul, li, li, li, span, a, img]

queue[ ]: [ ] -> [div] -> [p, label, ul] -> [label, ul] -> [ul] -> [li, li, li] -> [li, li, span] -> [li, span] -> [span, a] -> [a] -> [img]

item: div -> p -> label -> ul -> li -> li -> li -> span -> a -> img

結果：

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-EHLsdcQ9-1617634866644)(/Users/yinlu/Documents/截屏/截屏2021-04-05 下午11.00.10.png)]

轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/272904.html

標籤：其他

上一篇：JS入門陣列處理實用方法總結

下一篇：理解js繼承的六種方式