图的存储与一般有三种形式,邻接矩阵、邻接表、链式前向星(邻接表的一种)。
本文全文使用这个图来进行演示。
图示
我们规定,一共有 $n$ 个点,$m$ 条边。输入数据的格式为 “起点”、“终点”、“边权”。则这个图的输入数据为:

1 2 2
1 4 3
2 3 1
2 5 3
3 1 2
5 3 2
5 4 4

邻接矩阵

由于邻接矩阵空间消耗巨大,一般不使用。
邻接矩阵初始化时,我们使用无穷。
\begin{bmatrix} \infty & \infty & \infty & \infty & \infty \ \infty & \infty & \infty & \infty & \infty \ \infty & \infty & \infty & \infty & \infty \ \infty & \infty & \infty & \infty & \infty \ \infty & \infty & \infty & \infty & \infty \end{bmatrix}
因为对于有些题目,存在瞬移术,可以将某个权重的边跳过,这时可以把它的边权设为 0,这样就和不连通的情况产生了冲突,因此,就不能使用 0 为初值,当然,对于不存在这种情况的题目,仍可使用 0。
对于这个图,其邻接矩阵为:
\begin{bmatrix} 0 & 2 & \infty & 3 & \infty \ \infty & 0 & 1 & \infty & 3 \ 2 & \infty & 0 & \infty & \infty \ \infty & \infty & \infty & 0 & \infty \ \infty & \infty & 2 & 4 & 0 \end{bmatrix}
邻接矩阵的实质,就是用元素的有无来判断两个点是否连通。
因此,邻接矩阵的遍历效率很低,空间开销也很大,而且不能存储重边,可以存储自环(不过好像用处不大)。
建图、存储的时间复杂度为 $\text{O}(n^2)$ (若初始化为 $0$ 则为 $O(m)$ 的时间复杂度),空间复杂度为 $\text{O}(n^2)$。
遍历的时间复杂度为 $\text{O}(n^2)$。
模板如下: 继续阅读 »