SciPy 圖
使用圖
圖是一種基本的資料結構。
SciPy 為我們提供了 scipy.sparse.csgraph 模組來處理這類資料結構。
鄰接矩陣
鄰接矩陣是一個 nxn 矩陣，其中 n 是圖中元素的數量。
值表示元素之間的連線。
示例
對於像這樣的圖，具有元素 A、B 和 C，連線如下：
A 和 B 以權重 1 連線。
A 和 C 以權重 2 連線。
C 和 B 未連線。
鄰接矩陣將如下所示：
A B C
A:[0 1 2]
B:[1 0 0]
C:[2 0 0]
以下是一些用於處理鄰接矩陣的最常用方法。
連通分量
使用connected_components() 方法查詢所有連通分量。示例
import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix
arr = np.array([
[0, 1, 2],
[1, 0, 0],
[2, 0, 0]
])
newarr = csr_matrix(arr)
print(connected_components(newarr))
自己動手試一試 »
Dijkstra
使用 dijkstra 方法查詢圖中從一個元素到另一個元素的最短路徑。
它接受以下引數：
- return_predecessors: 布林值（如果返回整個遍歷路徑則為 True，否則為 False）。
- indices: 返回僅從此元素開始的所有路徑的元素索引。
- limit: 路徑的最大權重。
示例
查詢從元素 1 到 2 的最短路徑
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
arr = np.array([
[0, 1, 2],
[1, 0, 0],
[2, 0, 0]
])
newarr = csr_matrix(arr)
print(dijkstra(newarr, return_predecessors=True, indices=0))
自己動手試一試 »
Floyd Warshall
使用 floyd_warshall() 方法查詢所有元素對之間的最短路徑。
示例
查詢所有元素對之間的最短路徑
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix
arr = np.array([
[0, 1, 2],
[1, 0, 0],
[2, 0, 0]
])
newarr = csr_matrix(arr)
print(floyd_warshall(newarr, return_predecessors=True))
自己動手試一試 »
Bellman Ford
bellman_ford() 方法也可以查詢所有元素對之間的最短路徑，但此方法還可以處理負權重。
示例
查詢具有負權重的給定圖從元素 1 到 2 的最短路徑
import numpy as np
from scipy.sparse.csgraph import bellman_ford
from scipy.sparse import csr_matrix
arr = np.array([
[0, -1, 2],
[1, 0, 0],
[2, 0, 0]
])
newarr = csr_matrix(arr)
print(bellman_ford(newarr, return_predecessors=True, indices=0))
自己動手試一試 »
深度優先順序
depth_first_order() 方法從一個節點返回一個深度優先遍歷。
此函式接受以下引數：
- 圖。
- 用於遍歷圖的起始元素。
示例
遍歷給定鄰接矩陣的圖以深度優先方式進行
import numpy as np
from scipy.sparse.csgraph import depth_first_order
from scipy.sparse import csr_matrix
arr = np.array([
[0, 1, 0, 1],
[1, 1, 1, 1],
[2, 1, 1, 0],
[0, 1, 0, 1]
])
newarr = csr_matrix(arr)
print(depth_first_order(newarr, 1))
自己動手試一試 »
廣度優先順序
breadth_first_order() 方法從一個節點返回一個廣度優先遍歷。
此函式接受以下引數：
- 圖。
- 用於遍歷圖的起始元素。
示例
遍歷給定鄰接矩陣的圖以廣度優先方式進行
import numpy as np
from scipy.sparse.csgraph import breadth_first_order
from scipy.sparse import csr_matrix
arr = np.array([
[0, 1, 0, 1],
[1, 1, 1, 1],
[2, 1, 1, 0],
[0, 1, 0, 1]
])
newarr = csr_matrix(arr)
print(breadth_first_order(newarr, 1))
自己動手試一試 »
