Graph
By Long Luo
矩阵存图法
图中的顶点我们已经编好了号，那么我们需要储存的和图相关的信息，就只剩下点与点之间的连边了。
一个很直观的想法就是用一个二维数组来存图，下标代表点，值代表连边的情况。这就是所谓的矩阵存图法，也被称作为邻接矩阵存图法。
更具体地，我们一般使用 bool 数组来储存点与点之间的连边信息：
如果 con[i][j] 的值为 true ，表示点 i 与点 j 之间连了一条从 i 指向 j 的边。 如果 con[i][j] 的值为 false ，表示点 i 与点 j 之间没有连边。
以下图为例：
邻接表存图法
前面我们说过，矩阵存图的最大的劣势，就是在面对稀疏图时，有很多空间没有储存有效信息（对于一个图，我们往往更加关注哪些点之间有连边，而不关注哪些点之间没有连边），被浪费掉了。一个优化的思路是：我们不再考虑储存每一个点对之间的连边信息，而只考虑那些有连边的点对。这样我们就能够保证所储存下来的信息都会是有效的。
针对上述思路，对于一个有 nn 的点的图，我们可以利用 nn 个链表，第 ii 个链表里存着所有从 ii 直接连向的点。以下图为例：