Python/scipy graphs
来自菜鸟教程
<languages />
科学图
使用图
图是必不可少的数据结构。
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
查找图中从一个元素到另一个元素的最短路径的方法。
它采用以下参数:
- return_predecessors: 布尔值(真返回遍历的整个路径,否则返回False)。
- 指标: 元素的索引,仅返回该元素的所有路径。
- 限制: 路径的最大重量。
例
找到从元素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()
查找所有元素对之间最短路径的方法。
例
找到所有成对元素之间的最短路径:
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))
贝尔曼·福特
The
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))
深度一阶
The
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))
广度优先
The
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))