🔯從Python來學BFS廣度優先探索 與 等權圖的最短路徑Shortest Path

更新於 發佈於 閱讀時間約 1 分鐘

定義

圖Graph: 由節點和邊所組成的一個網狀資料結構。


圖的表達方式Graph representation:

常見的有相鄰串列adjacency list相鄰矩陣adjacency matrix

本文以adjacenct list作為示範。


節點Vertex: 節點,也稱之為Node,圖的基本組成單元之一。

邊Edge: 邊,可分為有向邊Directed Edge,或無向邊Undirected Edge

有向邊只能從起點走向終點。無向邊則可以雙向通過。

本文以有向邊作為示範。


廣度優先拜訪BFS:

從某個指定的起點開始探索整張圖,由內而外,逐層拜訪所有相鄰的節點

比喻:

就好像一個小石頭(或小水滴)掉入水中,同心圓往外一層一層水波紋擴散的模式

raw-image



等權圖 Equal weighted Graph

圖中所有的邊的成本都相同,最常見的簡化版本是每條邊的成本都為1。


最短路徑 Shortest Path:

起點出發,走到終點最短路徑(或最小成本)


當圖Graph是Edge成本都為1的等權圖的時候,
最短路徑 = 最佳路徑上經過的Edge總數


範例 等權圖中 A→D 的最短路徑

raw-image

演算法 用BFS來找等權圖中的最短路徑

1.建造一個BFS_queue,初始化時,放入起點計步器(一開始歸零)。


2.遵循BFS演算法從BFS_queue取出下一個要拜訪的節點計步器的值


3.由內而外逐層探索鄰居,並且將鄰居節點計步器+1的值推入BFS_queue。


4.假如某一步發現現在的節點就是終點,則輸出成功訊息,並且把最短路徑的長度輸出


  1. 假如整張圖都拜訪完還是走不到終點,則輸出失敗訊息,提示無法從起點走到終點。


演算法的時間複雜度 O(V+E) 每個點至多拜訪一次,每條邊最多檢查一次


詳細圖解 等權圖BFS最短路徑範例

raw-image


raw-image


raw-image


raw-image


raw-image


raw-image

最短路徑程式碼(底層依賴BFS廣度優先探索演算法)

    def shortest_path(self, start_node, target, visited=None):
if visited is None:
visited = set()

bfs_queue = deque([(start_node, 0)])
visited.add(start_node)

while bfs_queue:

cur, step = bfs_queue.popleft()
if cur == target:
print(f"shortest path from {start_node.value} to {target.value} takes {step} steps.")
return

print(cur.value)

for edge in cur.edges:
if edge.to_node not in visited:
visited.add(edge.to_node)
bfs_queue.append( (edge.to_node, step+1) )

print(f"There is no shortest path from {start_node.value} to {target.value}.")
return

體驗BFS廣度優先搜尋 與 等權圖最短路經的關聯

raw-image

完整的等權圖BFS 廣度優先拜訪與最短路徑實作和程式碼

from collections import deque

class Node:
def __init__(self, value):
self.value = value
self.edges = []

def add_edge(self, edge):
self.edges.append(edge)

class Edge:
def __init__(self, from_node, to_node):
self.from_node = from_node
self.to_node = to_node

class Graph:
def __init__(self):
self.nodes = []

def add_node(self, node):
self.nodes.append(node)

def add_edge(self, from_node, to_node):
edge = Edge(from_node, to_node)
from_node.add_edge(edge)

def dfs(self, start_node, visited=None):
if visited is None:
visited = set()

visited.add(start_node)
print(start_node.value)
for edge in start_node.edges:
if edge.to_node not in visited:
self.dfs(edge.to_node, visited)

def shortest_path(self, start_node, target, visited=None):
if visited is None:
visited = set()


bfs_queue = deque([(start_node, 0)])
visited.add(start_node)

while bfs_queue:

cur, step = bfs_queue.popleft()
if cur == target:
print(f"shortest path from {start_node.value} to {target.value} takes {step} steps.")
return

print(cur.value)

for edge in cur.edges:
if edge.to_node not in visited:
visited.add(edge.to_node)
bfs_queue.append( (edge.to_node, step+1) )

print(f"There is no shortest path from {start_node.value} to {target.value}.")
return

def demo():
# Graph and BFS demo

# Create Graph
graph = Graph()

# Create Node
nodeA = Node('A')
nodeB = Node('B')
nodeC = Node('C')
nodeD = Node('D')
nodeE = Node('E')
nodeF = Node('F')

# Add node into Graph
graph.add_node(nodeA)
graph.add_node(nodeB)
graph.add_node(nodeC)
graph.add_node(nodeD)
graph.add_node(nodeE)
graph.add_node(nodeF)

# Add edge into Graph
graph.add_edge(nodeA, nodeB)
graph.add_edge(nodeA, nodeC)
graph.add_edge(nodeB, nodeD)
graph.add_edge(nodeB, nodeE)
graph.add_edge(nodeC, nodeF)
graph.add_edge(nodeF, nodeD)

print("BFS traversal starting from node A:")

# 嘗試尋找從A走到D的最短路徑
graph.shortest_path(nodeA, nodeD)

# 嘗試尋找從C走到A的最短路徑
#graph.shortest_path(nodeC, nodeA)

if __name__ == '__main__':
demo()

測試輸出

BFS traversal starting from node A:
A
B
C
shortest path from A to D takes 2 steps.

結語


其實BFS廣度優先演算法就相當於水波紋從波源開始擴散的過程模擬

輸入是等權圖時,就可以利用這項特質,透過BFS來找從起點走到終點的最短路徑


最短路徑(最小成本) = 水波紋擴散層數 = 從起點到終點 沿路經過的Edge總數


讀者可以透過紙筆追蹤演算法和程式執行邏輯,測試幾個簡單的小範例,

會有更深刻的了解和體會!


Graph圖論BFS相關的演算法練習題與詳解


BFS 經典入門題 Binary Tree Level Order Traversal_Leetcode #102


BFS 經典入門題 Binary Tree Level Order Traversal II Leetcode #107


BFS應用題 Find Largest Value in Each Tree Row Leetcode #515


BFS經典應用 最精簡公車路線搭乘次數 Bus Routes_Leetcode #815


一魚多吃 用BFS來列出拜訪路徑 Diagonal Traverse II_Leetcode#1424


一題多解 用DP、BFS去解 Pefect Square 完全平方數的化簡_Leetcode #279


合縱連橫: 從 圖論的應用題 理解BFS背後的本質


Graph theory圖論 DFS、BFS演算法的統整與比較

留言
avatar-img
留言分享你的想法!
小松鼠-avatar-img
發文者
2024/09/23
林燃(創作小說家)
小松鼠-avatar-img
發文者
2024/09/27
動手學Python/資料結構/演算法 的目錄提及了這篇文章,趕快過去看看吧!
avatar-img
小松鼠的演算法樂園
95會員
427內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
2024/10/10
從Python 內建deque資料結構的角度切入, 同時了解deque 與 FIFO Queue相關的function用法。 collections.deque是一種兩端點皆可進出的雙端佇列 在兩端點高效地在O(1)常數時間內添加和刪除元素。 這使得deque非常適合實現FIFO Queue
Thumbnail
2024/10/10
從Python 內建deque資料結構的角度切入, 同時了解deque 與 FIFO Queue相關的function用法。 collections.deque是一種兩端點皆可進出的雙端佇列 在兩端點高效地在O(1)常數時間內添加和刪除元素。 這使得deque非常適合實現FIFO Queue
Thumbnail
2024/09/27
井字遊戲(OOXX)的遊戲描述 Tic Tac Toe(井字遊戲)是經典的雙人棋盤遊戲,在一個3x3的方格中進行。 每回合兩個玩家輪流選一個位置,先讓自己的符號(是 X 或 O)在 水平線、垂直線或對角線上連成一線的玩家宣告獲勝。
Thumbnail
2024/09/27
井字遊戲(OOXX)的遊戲描述 Tic Tac Toe(井字遊戲)是經典的雙人棋盤遊戲,在一個3x3的方格中進行。 每回合兩個玩家輪流選一個位置,先讓自己的符號(是 X 或 O)在 水平線、垂直線或對角線上連成一線的玩家宣告獲勝。
Thumbnail
2024/09/15
定義 圖Graph: 由節點和邊所組成的一個網狀資料結構。 圖的表達方式Graph representation: 常見的有相鄰串列adjacency list或相鄰矩陣adjacency matrix。 本文以adjacenct list作為示範。 節點Vertex: 節點
Thumbnail
2024/09/15
定義 圖Graph: 由節點和邊所組成的一個網狀資料結構。 圖的表達方式Graph representation: 常見的有相鄰串列adjacency list或相鄰矩陣adjacency matrix。 本文以adjacenct list作為示範。 節點Vertex: 節點
Thumbnail
看更多
你可能也想看
Thumbnail
「欸!這是在哪裡買的?求連結 🥺」 誰叫你太有品味,一發就讓大家跟著剁手手? 讓你回購再回購的生活好物,是時候該介紹出場了吧! 「開箱你的美好生活」現正召喚各路好物的開箱使者 🤩
Thumbnail
「欸!這是在哪裡買的?求連結 🥺」 誰叫你太有品味,一發就讓大家跟著剁手手? 讓你回購再回購的生活好物,是時候該介紹出場了吧! 「開箱你的美好生活」現正召喚各路好物的開箱使者 🤩
Thumbnail
介紹朋友新開的蝦皮選物店『10樓2選物店』,並分享方格子與蝦皮合作的分潤計畫,註冊流程簡單,0成本、無綁約,推薦給想增加收入的讀者。
Thumbnail
介紹朋友新開的蝦皮選物店『10樓2選物店』,並分享方格子與蝦皮合作的分潤計畫,註冊流程簡單,0成本、無綁約,推薦給想增加收入的讀者。
Thumbnail
定義 圖Graph: 由節點和邊所組成的一個網狀資料結構。 圖的表達方式Graph representation: 常見的有相鄰串列adjacency list或相鄰矩陣adjacency matrix。 本文以adjacenct list作為示範。 節點Vertex: 節點
Thumbnail
定義 圖Graph: 由節點和邊所組成的一個網狀資料結構。 圖的表達方式Graph representation: 常見的有相鄰串列adjacency list或相鄰矩陣adjacency matrix。 本文以adjacenct list作為示範。 節點Vertex: 節點
Thumbnail
在資料結構與演算法裡, 最簡單的線性資料結構除了list之外就是linked list鏈結串列了。 Linked list又有分為單向Singly linked list 和雙向Doubly linked list 在這篇文章,會從最基礎的Singly linked list開始講起。 定義
Thumbnail
在資料結構與演算法裡, 最簡單的線性資料結構除了list之外就是linked list鏈結串列了。 Linked list又有分為單向Singly linked list 和雙向Doubly linked list 在這篇文章,會從最基礎的Singly linked list開始講起。 定義
Thumbnail
題目敘述 Binary Tree Maximum Path Sum 給定一個二元樹,請找出最大的區間路徑和是多少? 註: 區間路徑和 = 某個節點a -> 某個節點b的路徑節點值總和。
Thumbnail
題目敘述 Binary Tree Maximum Path Sum 給定一個二元樹,請找出最大的區間路徑和是多少? 註: 區間路徑和 = 某個節點a -> 某個節點b的路徑節點值總和。
Thumbnail
今天的一魚三吃系列是透過 兩點之間是否存在一條路徑的題目,來回顧以前學過的DFS、BFS和Disjoint Set,鞏固圖論演算法的知識點。 英文的題目敘述在這裡 題目敘述 給定我們已知n個節點的圖,和圖上的每一條無向邊edges。 請問給定的起點start和終點end是否存在一條路徑可
Thumbnail
今天的一魚三吃系列是透過 兩點之間是否存在一條路徑的題目,來回顧以前學過的DFS、BFS和Disjoint Set,鞏固圖論演算法的知識點。 英文的題目敘述在這裡 題目敘述 給定我們已知n個節點的圖,和圖上的每一條無向邊edges。 請問給定的起點start和終點end是否存在一條路徑可
Thumbnail
這篇文章,會帶著大家複習以前學過的DFS框架, 並且以圖論的應用題與概念為核心, 貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個演算法框架。 DFS 深度優先搜索框架 def dfs( parameter ): # 邊界條件 if base case or stop cond
Thumbnail
這篇文章,會帶著大家複習以前學過的DFS框架, 並且以圖論的應用題與概念為核心, 貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個演算法框架。 DFS 深度優先搜索框架 def dfs( parameter ): # 邊界條件 if base case or stop cond
Thumbnail
這篇文章,會帶著大家複習以前學過的DFS框架 結合樹型DP, 並且以路徑和Path Sum的概念與應用為核心, 貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個演算法框架。 DFS 深度優先搜索框架 def dfs( parameter ): if base case or sto
Thumbnail
這篇文章,會帶著大家複習以前學過的DFS框架 結合樹型DP, 並且以路徑和Path Sum的概念與應用為核心, 貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個演算法框架。 DFS 深度優先搜索框架 def dfs( parameter ): if base case or sto
Thumbnail
題目會給定給我們一顆二元樹的根結點,要求我們輸出Level-order traversal的拜訪結果。 在這題,我們會複習並利用BFS模板,來實現逐層搜索演算法。
Thumbnail
題目會給定給我們一顆二元樹的根結點,要求我們輸出Level-order traversal的拜訪結果。 在這題,我們會複習並利用BFS模板,來實現逐層搜索演算法。
Thumbnail
題目會給定一顆樹,要求我們輸出所有從Root node根節點 到 Leaf node 葉子節點的路徑。 我們會介紹DFS模板 + Tree search演算法的框架來解題
Thumbnail
題目會給定一顆樹,要求我們輸出所有從Root node根節點 到 Leaf node 葉子節點的路徑。 我們會介紹DFS模板 + Tree search演算法的框架來解題
Thumbnail
圖論常用的演算法BFS 與 DFS 的統整與比較。 介紹常用且相關的底層資料結構 並且,介紹幾個適合使用的應用領域、解題分類。
Thumbnail
圖論常用的演算法BFS 與 DFS 的統整與比較。 介紹常用且相關的底層資料結構 並且,介紹幾個適合使用的應用領域、解題分類。
Thumbnail
進階圖論題目: 計算最短的一筆畫路徑長 題目會給定我們一張圖和對應的相鄰矩陣,要求我們返回一筆畫拜訪所有節點的最短路徑長,起終點不拘。
Thumbnail
進階圖論題目: 計算最短的一筆畫路徑長 題目會給定我們一張圖和對應的相鄰矩陣,要求我們返回一筆畫拜訪所有節點的最短路徑長,起終點不拘。
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News