邻接矩阵存储图存储空间与什么有关
时间: 2024-05-18 19:16:30 浏览: 17
邻接矩阵存储图的存储空间与图中的顶点数和边数有关。在邻接矩阵中,使用一个二维数组来表示图的边和顶点之间的连接关系。数组的大小由图的顶点数决定,每个元素都代表了两个顶点之间的连接情况。如果两个顶点之间存在边,则在相应的数组位置上存储一个非零值,否则存储零值。因此,邻接矩阵的存储空间与顶点数的平方成正比。
具体地说,对于有N个顶点和E条边的图,邻接矩阵的存储空间为N^2个元素,每个元素需要用一个固定的空间来存储。因此,邻接矩阵的存储空间为O(N^2)。需要注意的是,邻接矩阵对于稀疏图(边数较少)而言可能会浪费大量的存储空间,因为大部分数组元素都是零。
总结起来,邻接矩阵存储图的存储空间与图的顶点数和边数成正比,具体为O(N^2)。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* [论文研究-基于邻接矩阵的FP-tree构造算法.pdf](https://download.csdn.net/download/weixin_38744270/11732306)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
- *2* *3* [图的邻接矩阵存储](https://blog.csdn.net/qq_45519325/article/details/126089663)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]