图的表示
-
图 \(G = (V,E)\),其中 \(V\) 为点集,\(E\) 为边集
-
邻接矩阵:顾名思义为矩阵,\(a_{i,j}\) 表示边 \((i,j)\) 的信息。优点是可以进行矩阵乘法,可以方便的判断 \((u,v) \in E\);缺点是空间复杂度为 \(O(V^2)\),遍历图的时间复杂度也为 \(O(V^2)\),不适用于稀疏图
-
邻接表:顾名思义为链表,\(Adj_u\) 表示能从 \(u\) 出发只经过一条边到达的点 \(v\)。优点是空间复杂度为 \(O(V+E)\),稠密图和稀疏图都适用;缺点也是不能快速判断 \((u,v) \in E\)