mirror of
https://github.com/happyflyer/wangdao-data-structure.git
synced 2026-02-03 02:24:39 +08:00
2.1 KiB
2.1 KiB
图的存储结构
1. 邻接矩阵法
V=\{A,B,C,D,E\}用一维数组存储。E=\{(A,B),(A,C),(A,E),(B,C),(C,D),(C,E)\}用二维数组存储。
二维数组行号表示起始端点，列号表示终止端点，值表示该边是否存在或该边的权重。二维数组又称为邻接矩阵。
结点数为 n 的图 G=(V,E) 的邻接矩阵是 n \times n 的。
将 G 的顶点编号为 V_1,V_2,...,V_n （数组下标），若 $<V_i,V_j> \in E$，则 $A[i][j]=1$，否则 $A[i][j]=0$。
A[i][j]=
\begin{cases}
1,(V_i,V_j)或<V_i,V_j>是E(G)的边\\
0,(V_i,V_j)或<V_i,V_j>不是E(G)的边\\
\end{cases}
- 邻接矩阵法的空间复杂度为：$O(n^2)$，适用于稠密图。
- 无向图的邻接矩阵为对称矩阵。
- 无向图中第
i行（或第i列）非0元素（非正无穷）的个数为第i个顶点的度。 - 有向图中第
i行（第i列）非0元素（非正无穷）的个数为第i个顶点的出度（入度）。
2. 邻接表法
邻接矩阵法存储稀疏图会有很多空间浪费。
3. 十字链表
在邻接表中寻找所有的出边（以该顶点为弧尾的弧）非常容易，但是寻找某个顶点的入边非常困难，需要遍历整个边表。
4. 邻接多重表
