码农教程 - 一技在手,衣食无忧! tools

目录

SciPy 图表

❮ 上一节 下一节 ❯

使用图表

图是一种重要的数据结构。

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一种查找图中从一个元素到另一个元素的最短路径的方法。

它需要以下参数：

  1. 返回前辈：布尔值（True 返回整个遍历路径，否则返回 False）。
  2. 指数：元素的索引，仅返回该元素的所有路径。
  3. 限制：路径的最大权重。

示例

求从元素 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))
亲自试一试 »

贝尔曼·福特

这个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()方法返回从节点开始的深度优先遍历。

该函数采用以下参数：

  1. 图表。
  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))
亲自试一试 »

广度一阶

这个breadth_first_order()方法返回从节点开始的广度优先遍历。

该函数采用以下参数：

  1. 图表。
  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))
亲自试一试 »

通过练习测试一下

练习:

插入缺失的方法来查找所有连接的组件：

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

开始练习

❮ 上一节 下一节 ❯