Python SciPy 图(Graphs)

SciPy依赖于Numpy,SciPy包含的功能:最优化、线性代数、积分、插值、拟合、特殊函数、快速傅里叶变换、信号处理、图像处理、常微分方程求解器等,SciPy是高端科学计算工具包,用于数学、科学、工程学等领域。本文主要介绍Python SciPy 图(Graphs)。

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))
推荐阅读
cjavapy编程之路首页