圖的走訪- BFS 篇 - iT 邦幫忙

4 圖的走訪- BFS 篇如果要好好地探索一張圖，最經典的方法莫過於深度優先 ... 接下來跟大家分享一個把BFS 演算法反過來應用在圖論中的有趣例子。

2021iThome鐵人賽 DAY 3 0 SoftwareDevelopment 圖論與演算法之間的相互應用系列第 3篇 圖的走訪-BFS篇 13th鐵人賽 卡卡恩 2021-09-1715:13:04227瀏覽 4圖的走訪-BFS篇 如果要好好地探索一張圖，最經典的方法莫過於深度優先搜索(DepthFirstSearch)以及廣度優先搜索(BreadthFirstSearch)了！深度優先搜索DFS是利用堆疊的概念，如果有發現一條道路通往尚未探索過的點，那麼就先把這個點的狀態暫時堆疊起來，先行探索下一個點，直到無路可進以後才回溯。

廣度優先搜索BFS則是預先勘查好所有與目前這個點相連的所有點，將之標記後放入一個待處理的佇列，然後從這個佇列逐一重複相同的探索動作。

這兩種演算法有著非常非常多的應用，我們今天先來舉幾個簡單的例子。

（備註：我們今天討論的圖，都是無向、無權重的圖，是最單純的那類圖。

） 4.1尋找最短路線 想像一下我們有一些房間，而房間與房間之間有走廊連結著。

如果我們今天要從點A走到點B，這時候就可以從A開始利用廣度優先搜索，逐步探查A走一步可以到的點、然後到走兩步可以到的點、等等依此類推。

如果我們將「探查誰從而發現誰」這樣的關係描繪出來，不難發現這樣會形成一個樹狀結構（我們通常稱它為BFS搜索樹） 不是重點的參考程式碼(Python)： fromqueueimportQueue importnetworkxasnx defget_bfs_tree(G,start_node): """回傳從start_node開始搜索的BFS搜索樹、以及每個點的父節點。

""" prev=dict()#prev紀錄每個點是誰走過來的。

prev[start_node]=start_node#做個標記，表示走過了。

q=Queue() q.put(start_node) H=nx.Graph() whilenotq.empty(): u=q.get() forvinG.neighbors(u): ifvnotinprev: H.add_edge(u,v) prev[v]=u q.put(v) returnH,prev 4.2保持雙頂點連通分量的子圖 接下來跟大家分享一個把BFS演算法反過來應用在圖論中的有趣例子。

想像一下，如果這張圖G代表一個網路。

每一條邊都代表連接兩個節點的某條網路線，我們想要找出這個圖的子圖H（也就是保留某些網路線），使得任兩點之間仍然可以進行資料傳輸（可以是直接或間接的資料傳輸）。

顯然隨便找一棵生成樹就可以了，如果我們想要額外增加條件：如果某個節點壞掉了，在原本的圖G上面仍然連通，在這個子圖H上也必須要連通。

在這樣的條件之下，我們說這個子圖H是保有圖G的雙連通分量特性的！要怎麼實作呢？想必各位也已經猜到了，沒錯就是使用BFS！如果我們對這張圖G做兩次BFS（第二次的時候可能有些地方會斷開，就對每個連通分量各自做一次BFS就行了），這些蒐集起來的邊，可以經過神奇的數學證明，它滿足我們想要的保持雙頂點連通分量的條件！ 4.X冷笑話 為什麼把一張圖燒掉以後，時間很快就過了呢？因為，這一切都太圖燃了啊... 留言 追蹤 檢舉 上一篇 圖的資料結構 下一篇 圖的走訪-DFS篇 系列文 圖論與演算法之間的相互應用 共30篇 目錄 RSS系列文 訂閱系列文 5人訂閱 26 近似最短路徑(6) 27 近似最短路徑(7) 28 近似最短路徑(8) 29 近似最短路徑(9) 30 第k短路徑問題(1) 完整目錄 尚未有邦友留言 立即登入留言 iT邦幫忙鐵人賽 參賽組數 1087組 團體組數 52組 累計文章數 20485篇 完賽人數 572人 鐵人賽最新文章 資料驗證(golang)(Day23) .NetCoreWebApi_筆記22_Swagger自訂文件並讀取API註解描述 [Day??]2021iThome鐵人賽-頒獎典禮@2022.01.08‧輔仁大學 [Day33]HexoxNexT-顯示最新文章、導入GoogleAnalytics的坑 【Day31】新加坡工作後續的時程 重構原本的內容(golang)(Day22) Laravel-jQueryAJAX範例 2022/1/2更新 .NetCoreWebApi_筆記21_Swagger及OpenAPI介紹與配置使用方式_API管理與測試探討 .NetCoreWebApi_筆記20_api結合ADO.NET資料庫操作part8_新聞文章查詢 前往鐵人賽 技術推廣專區 [Day2]抓取每日收盤價 [Day1]基本工具安裝 利用python取得永豐銀行API的Nonce [Day03]tinyML開發板介紹 永豐金融API測試員 [Day01]在享受tinyML這道美食之前 [Day3]使用ta-lib製作指標 [Day4]函數打包與買進持有報酬率試算 計算API所需要的參數:HashID 計算API所需要的參數:IV 前往鐵人賽 熱門問題 中華電信企業資安攻擊名稱HTTP-APACHE-LOG4j2-BODY6-RCE 40人小公司用的郵件伺服器 急救！將ImageView傳到另一個頁面 關於團隊合作 正航ERP相關問題 資安宣導文案 請問有哪位好心人能借一下百度帳號... 請教SQL大師，如何在GROUPBY分群裡找出組別最多筆數量的組別名稱 [已解決]急!!!csv匯入MySQLWorkbench出現錯誤訊息請問如何解決 C#如何將資料庫的每個字元從原本的(ascii編碼)逐一轉成(utf8編碼) IT邦幫忙 站方公告 【2021iThome鐵人賽】登登登！究竟獎落誰家，2021iThome鐵人賽得獎名單正式揭曉 熱門tag 看更多 13th鐵人賽 12th鐵人賽 11th鐵人賽 鐵人賽 2019鐵人賽 2018鐵人賽 javascript 2017鐵人賽 windows php python windowsserver linux c# 程式設計 資訊安全 css vue.js sql 分享 熱門回答 40人小公司用的郵件伺服器 關於團隊合作 資安宣導文案 SVN版本控制的選擇 python檔案計算問題 [已解決]急!!!csv匯入MySQLWorkbench出現錯誤訊息請問如何解決 C#如何將資料庫的每個字元從原本的(ascii編碼)逐一轉成(utf8編碼) 正航ERP相關問題 為什麼Visualstudio查詢資料庫資料會顯示 中華電信企業資安攻擊名稱HTTP-APACHE-LOG4j2-BODY6-RCE 熱門文章 【Day31】新加坡工作後續的時程 2021法遵科技與電腦稽核專題競賽-賀雲科大、逢甲、北商大、中正、致理科大、亞洲科大等學校隊伍獲獎，培育智慧法遵與AI稽核人才邁向國際~ Laravel-jQueryAJAX範例 [Day33]HexoxNexT-顯示最新文章、導入GoogleAnalytics的坑 【徵才】台北中山區-知名航空貨運-資訊網管人員 重構原本的內容(golang)(Day22) 科學家與研究生的關係研究篇 [Day??]2021iThome鐵人賽-頒獎典禮@2022.01.08‧輔仁大學 30天Python自學:Day01 印表機維修五種常見故障，若遇到問題就能先自己排除了 一週點數排行 更多點數排行 海綿寶寶(antijava) Gary(mosbbs) raytracy(raytracy) 一級屠豬士(hitomitanaka) Samuel(kuanyu) ccenjor(ccenjor) 居然解出來了(partyyaya) horace_work(horace_work) 純真的人(jer5173) souda(souda) × At 輸入對方的帳號或暱稱 Loading 找不到結果。

標記 {{result.label}} {{result.account}} 關閉