1、使用图
图是必不可少的数据结构。
SciPy为我们提供了用于处理此类数据结构的模块scipy.sparse.csgraph。
2、邻接矩阵
邻接矩阵是一个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]
下面介绍了一些处理邻接矩阵的最常用方法。
3、connected_components
使用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))4、dijkstra
使用dijkstra方法查找图中从一个元素到另一个元素的最短路径。
它采用以下参数：
return_predecessors：布尔值（真，返回遍历的整个路径，否则为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))5、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))6、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))7、depth_first_order
depth_first_order()方法返回节点的深度优先遍历。
此函数采用以下参数：
1) graph
2) 遍历图的起始元素。
例如：
首先遍历给定邻接矩阵的图深度：
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))8、breadth_first_order
breadth_first_order()方法返回节点的广度优先遍历。
此函数采用以下参数：
1) graph
2) 遍历图的起始元素。
例如：
首先遍历给定邻接矩阵的图宽度：
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))