迷宮系列（三）利用BFS/DFS的資料得到最短路/通路 - IT人

迷宮系列（三）利用BFS/DFS的資料得到最短路/通路 ... 比如：DFS演算法第一步就走了錯誤的一步，在此之後即使到達目的節點也不會是最短的路徑 ... Togglenavigation IT人 IT人 迷宮系列（三）利用BFS/DFS的資料得到最短路/通路 小聲逼逼發表於 2017-12-16 一、如何得到最短路 演算法性質分析 1.BFS性質： 該演算法需要在發現所有與這個源節點距離為k的節點後，才回去發現與這個源節點距離為k+1的節點。

故BFS對一個圖G的搜尋是嚴格分層的，如果一個點V在第n層被發現，那麼它距離源節點的最短距離一定為n，否則將違背BFS演算法的性質。

2.DFS性質： 主要思想：一條路走到黑 故：DFS在問題有解的情況下可以順利找到解，但DFS的搜尋是盲目的，它的目的僅僅是走過各種可能的分支來找到問題的解，但不一定是最優解。

比如：DFS演算法第一步就走了錯誤的一步，在此之後即使到達目的節點也不會是最短的路徑 3.結論 BFS演算法可以用來找出一個圖中的最短路 DFS演算法不能找出最短路，但可以找出所有通路（雖然BFS也可以） 二、如何得到路徑 1.考慮在BFS演算法示例中得到的結果 假設起點為A，前往G，顯然最短路有兩條A->D->G和A->E->G 2.如何根據表格裡的資料得到路徑呢 思路1. 從起點A開始搜尋，根據dis遞增的規律來找到G，從而輸出正確的路徑 分析：不可行 原因：從A點出發會產生過多的旁枝，沒有意義 思路2. 從終點G開始逆向搜尋，根據dis遞減的規律來找到A，從而輸出正確的路徑 分析：可行 原因：由於起點是唯一的，從G延展出的所有dis嚴格遞減的節點序列最終一定都回到起點A。

3.如何實現？ 做法：搜尋，深度優先搜尋=￣ω￣= 虛擬碼 PATH(節點v) { if(v==起點) { 從棧底輸出棧S，即為最短路徑之一; } else { for(與v鄰接的每一個元素u) { if(u尚未被訪問) { if(u.dis==v.dis-1)//u是v的前驅（是u發現的v） { 標記u被訪問; 把u壓入棧; PATH(u); 取消u的標記; 彈出棧頂元素; } } } } } 另：如何尋找通路 對於通路，我們可以認為只要該節點dis屬性不為初始值(-1)，這個節點就是可以行走的，所以我們可以從終點起，按照這樣的狀態轉移約束，搜尋出所有的通路 下一節將講解其他的實現細節和DFS的實際應用（敲黑板！重要！=￣ω￣=） 相關文章 大資料和Hadoop平臺介紹 2020-11-22 Hadoop （在模仿中精進資料視覺化04）舊金山街道樹木分佈視覺化 2020-11-22 視覺化 Mysql資料庫之多表查詢、事務、DCL 2020-11-22 資料庫MySQL Mysql資料安全備份 2020-11-22 MySQL 利用requestes\pyquery\BeautifulSoup爬取某租房公寓(深圳市)4755條租房資訊及總結 2020-11-22 在SAPSpartacus產品明細頁面用outlet顯示自定義資料 2020-11-22 Redis資料結構之整數集合 2020-11-22 資料結構Redis 【資料結構】二叉樹的建立與遍歷 2020-11-22 演算法資料結構 基於深度對抗學習的智慧模糊資料生成方法 2020-11-22 你211研究生不好好學你的專業，為什麼自學大資料開發？ 2020-11-22 36氪研究院：2020年中國服裝行業資料中臺研究報告（附下載） 2020-11-23 金融科技創新發展研究報告：資料要素與金融科技創新 2020-11-23 腦機介面資料分析工具EEGLAB04---繪製通道光譜圖 2020-11-22 微信小程式父子元件之間的資料傳遞 2020-11-22 如何避免資料庫被黑 2020-11-23 資料庫 手把手教你學Python之基本資料型別 2020-11-23 Python 今日資料行業日報（2020.11.23）『預計今年黑色星期五網路銷售額增長45%』 2020-11-23 Hadoop3.2.1【HDFS】原始碼分析:DataXceiver:讀取資料塊解析[二] 2020-11-23 Hadoop Mysqlbinlog備份資料及恢復資料，學會這個，我在也不怕刪庫跑路啦~ 2020-11-23 MySQL 5G革命：如何讓「資料」實現最大效能？ 2020-11-23 最新文章 C語言execve()函式 Photoshop破解版百度網盤（百度雲）資源附序號產生器 XCOrganizerforMac-專案標籤分配追蹤軟體 在實驗中觀察指標——C++函式引數的壓棧順序 劍指offer-Go版實現第五章：優化時間和空間效率 js中的toString方法 springBoot@Scheduled多工同時開始執行 AngularUniversal的演進歷史 SAP電商雲SpartacusUI的響應式UI實現細節 什麼是前端開發中的mobilefirst策略 SAPSpartacusdevelopbranch的伺服器端渲染啟動方式 AngularUniversal學習筆記