SciPy 图结构

本页内容
上一节: SciPy_稀疏矩阵 下一节: SciPy_空间数据

SciPy 图结构

图结构是算法学中最强大的框架之一。

图是各种关系的节点和边的集合,节点是与对象对应的顶点,边是对象之间的连接。

SciPy 提供了 scipy.sparse.csgraph 模块来处理图结构。

邻接矩阵

邻接矩阵(Adjacency Matrix)是表示顶点之间相邻关系的矩阵。

邻接矩阵逻辑结构分为两部分:V 和 E 集合,其中,V 是顶点,E 是边,边有时会有权重,表示节点之间的连接强度。

用一个一维数组存放图中所有顶点数据,用一个二维数组存放顶点间关系(边或弧)的数据,这个二维数组称为邻接矩阵。

看下下图实例:

顶点有 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]

邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵。

无向图是双向关系,边没有方向:

有向图的边带有方向,是单向关系:

注:上面两个图中的 D 节点是自环,自环是指一条边的两端为同一个节点。

连接组件

查看所有连接组件使用 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))

以上代码输出结果为:


示例

(1, array([0, 0, 0], dtype=int32))

Dijkstra -- 最短路径算法

Dijkstra(迪杰斯特拉)最短路径算法,用于计算一个节点到其他所有节点的最短路径。

Scipy 使用 dijkstra() 方法来计算一个元素到其他元素的最短路径。

dijkstra() 方法可以设置以下几个参数:

  1. return_predecessors: 布尔值,设置 True,遍历所有路径,如果不想遍历所有路径可以设置为 False。
  2. indices: 元素的索引,返回该元素的所有路径。
  3. 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))

以上代码输出结果为:


示例

(array([ 0.,  1.,  2.]), array([-9999,     0,     0], dtype=int32))

Floyd Warshall -- 弗洛伊德算法

弗洛伊德算法算法是解决任意两点间的最短路径的一种算法。

Scipy 使用 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))

以上代码输出结果为:


示例

(array([[ 0.,  1.,  2.],
       [ 1.,  0.,  3.],
       [ 2.,  3.,  0.]]), array([[-9999,     0,     0],
       [    1, -9999,     0],
       [    2,     0, -9999]], dtype=int32))

Bellman Ford -- 贝尔曼-福特算法

贝尔曼-福特算法是解决任意两点间的最短路径的一种算法。

Scipy 使用 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))

以上代码输出结果为:


示例

(array([ 0., -1.,  2.]), array([-9999,     0,     0], dtype=int32))

深度优先顺序

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

以上代码输出结果为:


示例

(array([1, 0, 3, 2], dtype=int32), array([    1, -9999,     1,     0], dtype=int32))

广度优先顺序

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

以上代码输出结果为:


示例

(array([1, 0, 2, 3], dtype=int32), array([    1, -9999,     1,     1], dtype=int32))
上一节: SciPy_稀疏矩阵 下一节: SciPy_空间数据
此页面最后编辑于2022年8月17日 (星期三) 21:57。