JS實(shí)現(xiàn)深度優(yōu)先搜索求解兩點(diǎn)間最短路徑

更新時(shí)間：2019年01月17日 11:19:35 作者：我要瀟瀟灑灑

這篇文章主要為大家詳細(xì)介紹了JS實(shí)現(xiàn)深度優(yōu)先搜索求解兩點(diǎn)間最短路徑，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

本文實(shí)例為大家分享了JS實(shí)現(xiàn)深度優(yōu)先搜索求解兩點(diǎn)間最短路徑的具體代碼，供大家參考，具體內(nèi)容如下

效果：

找出圖里點(diǎn)到點(diǎn)最短路徑，并打印軌跡

圖片如下所示：

代碼：

const map = [
  [0, 1, 1, 0, 1],
  [1, 0, 0, 1, 0],
  [1, 0, 0, 0, 1],
  [0, 1, 0, 0, 0],
  [1, 0, 1, 0, 0]
]

function dfsManager(map, start, end){

  var min = 9999,
    path = [],
    unvisited = [];
  for(let i=0; i<5;i++){
    unvisited[i] = true
  }

  (function dfs(map, start, end, step){
    //unvisited[start] = false //不重復(fù)訪問最后的節(jié)點(diǎn)
    if(start === end){
      console.log('step:',step)
      for(let i=0; i<path.length; i++){
        if(path[i] >= 0){
          console.log(path[i]+'->')
        }
      }
      if(min > step){
        min = step
      }
      return
    }
    unvisited[start] = false  //要重復(fù)訪問最后的節(jié)點(diǎn)
    let len = map.length

    for(let i=0; i<len; i++){
      if(map[start][i] === 1 && unvisited[i]){
        path.push(i)  //記錄路徑
        dfs(map, i, end, step+1)
        path.pop()   //避免污染其他路徑
      }
    }
  })(map, start, end, 0)

  return min
}

console.log('min:',dfsManager(map,3,4))

output：

step: 4
1->
0->
2->
4->
step: 3
1->
0->
4->
min: 3

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章:

JS使用Dijkstra算法求解最短路徑

相關(guān)文章

event.currentTarget與event.target的區(qū)別介紹
event.currentTarget與event.target的區(qū)別想大家在使用的時(shí)候不是很在意，本文以測試代碼來講解它門之間的不同
2012-12-12
javascript中的隱式調(diào)用
本篇文章給大家詳細(xì)介紹了javascript中的隱式調(diào)用相關(guān)知識點(diǎn)，對此有興趣的可以跟著小編一起學(xué)習(xí)下。
2018-02-02
使用CoffeeScrip優(yōu)美方式編寫javascript代碼
CoffeeScript就是JavaScript，他進(jìn)行的是一對一的編譯，或者說是翻譯，而且編譯成的JavaScript代碼可讀性很強(qiáng)。本文給大家介紹使用CoffeeScript優(yōu)美方式編寫javascript代碼，感興趣的朋友一起看看吧
2015-10-10
JavaScript實(shí)現(xiàn)數(shù)組去重的14種方法大全
親愛的小伙伴,對于數(shù)組javascript中的數(shù)組去重方法你知道多少種呢？學(xué)會如何對數(shù)組進(jìn)行去重對于javascript的學(xué)習(xí)來說也是十分重要的,下邊就讓我來分享一下我所知道的集中數(shù)組去重的方法吧,感興趣的小伙伴跟著小編一起來看看吧
2025-03-03
使用TypeScript?V8來改進(jìn)您的JavaScript代碼
TypeScript?V8是一個強(qiáng)大的JavaScript類型系統(tǒng),它可以幫助你發(fā)現(xiàn)JavaScript代碼中的錯誤和潛在問題,并在編譯時(shí)捕獲它們,以便您可以解決它們,TypeScript?V8為JavaScript提供一系列的類型注釋,包括自定義類型和其他高級功能
2023-08-08
JS實(shí)現(xiàn)電商商品展示放大鏡特效
這篇文章主要為大家詳細(xì)介紹了JS實(shí)現(xiàn)電商商品展示放大鏡特效，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2020-01-01
原生JS分頁展示效果（點(diǎn)擊分頁看效果）
特別酷的分頁展示效果，原生JS實(shí)現(xiàn)，點(diǎn)擊分頁看效果
2012-11-11
微信小程序?qū)崿F(xiàn)Timeline時(shí)間線效果
這篇文章主要為大家詳細(xì)介紹了微信小程序?qū)崿F(xiàn)Timeline時(shí)間線效果，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2022-05-05
Js的MessageBox效果代碼
看到論壇上有人模仿alert，自己也寫了一個。本來想模仿winapi里的MessageBox 但可惜js 不支持，阻塞模式。
2008-05-05
javascript實(shí)現(xiàn)時(shí)鐘動畫
這篇文章主要為大家詳細(xì)介紹了javascript實(shí)現(xiàn)時(shí)鐘動畫，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2020-12-12