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))
自己动手试一试 »
