图的存储¶
直接存边¶
直接存下集合 \(E\)，这样空间牺牲较小。但是牺牲了很大的访问速度。可以用一个数组 \(e\) 表示每一条边，第 \(i\) 条边为 \(e_i\)，那么假如第 \(i\) 条边接通了 \(u\) 和 \(v\)，权值为 \(w\)，\(e_i=(u,v,w)\)。
邻接矩阵¶
可以使用一个 \(|V|\times|V|\) 的二维数组 \(e\)，对于 \(u\) 和 \(v\) 两个点，如果他们之间有边的话，\(e_{(u,v)}=1\)。如果是一张带权图的话，那么 \(e_{(u,v)}=w\)；反之若 \(u\) 和 \(v\) 不连通，\(e_{(u,v)}=\infty\)。空间可能会过大。
邻接表¶
可以使用 \(|V|\) 个动态数组，第 \(i\) 个动态数组表示为 \(i\) 的邻边，那么如果 \(u\) 到 \(v\) 有边，就直接将 \(v\) 存到第 \(u\) 个动态数组里面就行了。这种存图方法理论上来讲是最为优秀的，但是不可以 \(\mathcal O(1)\) 判断任意两点是否有边。
链式前向星
邻接表还有链表优化版本，叫做链式前向星，感兴趣可以自己百度，再次不做阐述。
复杂度对比¶
假设点数为 \(n\)，边数为 \(m\)，\(i\) 的邻点数量为 \(f(i)\)。
| 存图方法 | 空间复杂度 | 判断任意两点是否有边 | 遍历任意点的邻边 | 遍历整张图 |
|---|---|---|---|---|
| 直接存边 | \(\mathcal O(m)\) | \(\mathcal O(m)\) | \(\mathcal O(m)\) | \(\mathcal O(nm)\) |
| 邻接矩阵 | \(\mathcal O(n^2)\) | \(\mathcal O(1)\) | \(\mathcal O(n)\) | \(\mathcal O(n^2)\) |
| 邻接表 | \(\mathcal O(m)\) | \(\mathcal O(f(i))\) | \(\mathcal O(f(i))\) | \(\mathcal O(n+m)\) |