Python/scipy graphs

来自菜鸟教程
跳转至:导航、​搜索

<languages />

科学图

使用图

图是必不可少的数据结构。

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. return_predecessors: 布尔值(真返回遍历的整个路径,否则返回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))

贝尔曼·福特

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

深度一阶

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

广度优先

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