菜鸟笔记
提升您的技术认知

图的存储结构(邻接矩阵)

邻接矩阵(无向图)

因为图是由顶点和边或弧组成的,所以最好是把他们分开存储。

下面来看无向图的邻接矩阵。

图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图。

如下图所示:

由上图可以很明显的看出0表示不存在顶点间的边,1表示顶点间存在的边。

邻接矩阵(有向图)

下面是一个有向图,我们把他化为邻接矩阵:

由上图可知:有向图是有方向的,要考虑出度和入度,只有Vi到Vj时才表示存在。

邻接矩阵(网)

网实际上就是每条边带有权的图。

如下图所示:

这里的∞表示一个计算机允许的、大于所有边上权值的值。