图图的存储、BFS、DFS

• 邻接矩阵的缺点是在表示一个图时通常很浪费存储空间。

对于无向图来说，它是一个对称矩阵，即 A[i][j] 等于 1 的话，那么 A[j][i] 也等于 1。那么实际上只要存储一半就可以了。

另外，假如存储的是稀疏图，也就是顶点很多，但是每个顶点的边不多的一种图。那么使用邻接矩阵存储将更浪费存储空间，因为很多位置的值都是 0，这些 0 其实都是没有用的。

• 邻接矩阵的优点就是存储方式简单、直观，而且获取两个顶点的关系时非常高效。另外，使用邻接矩阵时，在计算上也很方便。因为很多图的运算实际上可以转换为矩阵的运算，比如求最短路径问题时会提到一个 Floyd-Warshall 算法，这个算法会利用到矩阵循环相乘若干次的结果。

2.2. 邻接表

图的另一种存储方法，是使用邻接表(Adjacency List)。如图所示，有向图中的每个顶点对应一个链表，该链表中存储的是该顶点指向的顶点。对于无向图来说是类似的，每个节点对应的链表中存储的是该节点所相连的顶点。

• 接表相比邻接矩阵的一个优点就是节省空间，但是使用起来比较耗时间(时间换空间的设计思想)。在使用邻接矩阵判断无向图中 i 和 j 之间是否存在一条边，那么只需要判断 A[i][j] 是否为 1，而在邻接表中判断无向图中 i 和 j 之间是否存在一条边，那么需要判断 i 这个顶点对应的链表中是否存在 j。而且链表的方式对于缓存来说不太友好。所以，综上来说在邻接表中查询两个顶点的关系没有邻接矩阵那么高效了。
• 但是，为了让查询变得更加高效。我们可以参考散列表中提到的那样，将链表换成平衡二叉查找树(比如红黑树)，或者其他动态数据结构，比如跳表、散列表，有序动态数组(结合二分查找)等。

逆邻接表

邻接表中存储的是这个顶点指向的顶点，那么逆邻接表中存储的是指向这个顶点的顶点。比如要想查看 4 这个顶点指向了哪些节点就可以使用邻接表。但是想要查看有哪些节点指向了 4 这个顶点，那么就需要逆邻接表了。

（编辑：南通站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!