图的存储

首先要明白,图不仅要存点,还要存边。

图的存储表示有两种,矩阵法和邻接链表法。

矩阵法,是用二维矩阵来存放边信息。点向量,来保存点信息。可用于保存有向图和无向图。

不过无向图会导致冗余出现。

由于我们存放的是简单图,不会有自循环路径。

所以对角线元素均为0。没有路径标记为Integer.Max,其余填写权重即可。

邻接链表是一种数组,链表复合表示。

它是一种很常见的数据结构。可用于开散列表示,树的子女链表表示。

对于图来说,顶点组成顶点数组。不过顶点内维护一个指向其出度点的指针,组成出度边链表。

从每一顶点出发,可链式访问其所有出度点。

这种表示可大大节省空间,而且也高了效率。是为数不多的既省空间又省时间的表示。

不过按入度查找时有些麻烦。

原文地址:https://www.cnblogs.com/zqiguoshang/p/6615856.html