SciPy 教程 之 SciPy 图结构 1

SciPy 教程 之 SciPy 图结构 1

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]

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

无向图是双向关系，边没有方向

有向图的边带有方向，是单向关系