手册

SciPy 教程

介绍入门常量优化器稀疏数据图表空间数据 Matlab 数组插值显著性检验

首页运维开发其它工具 SciPy 教程

图表

阅读2426

更新时间2025-08-14

稀疏数据

空间数据

使用图

图是基本的数据结构。

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）

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）

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))

稀疏数据

空间数据