SciPy 图结构

使用图结构

图（Graph）是一种基本的数据结构。

SciPy 为我们提供了用于处理此类数据结构的模块 scipy.sparse.csgraph。

邻接矩阵

邻接矩阵是一个 nxn 矩阵，其中 n 是图形中的元素数。

这些值表示元素之间的连接。

比如：

在这个例子中，顶点有 A、B、C，边权重有 1 和 2。

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：布尔值（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))