数据结构-图的存储结构

图的存储结构

在这里插入图片描述

在这里插入图片描述

邻接矩阵的主要特点：
①方便查找任意一个顶点是否存在边。

②方便找任一个顶点的所有“邻接点”（有边直接相连的顶点）。

③方便计算任一顶点的度。

④无向图的邻接矩阵数组一定是一个对称矩阵。

⑤对于无向图，邻接矩阵数组的第i行或第i列非零元素、非∞元素的个数正好是顶点i的度。

⑥对于有向图，邻接矩阵数组的第i行（或第i列）非零元素、非无穷元素的个数正好是顶点i的出度（或入度）。

⑦在邻接矩阵中，判断图中两个顶点之间是否有边或者求两个顶点之间的权的执行时间为O(1)。

⑧一个图的邻接矩阵表示是唯一的。
在这里插入图片描述

图的邻接矩阵存储类型定义如下：
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

例：

在这里插入图片描述

在这里插入图片描述

例题：

在这里插入图片描述

邻接表的特点：
①邻接表表示 不唯一

②方便找任意顶点的所有“邻接点”。

③若无向图中有N个顶点，e条边，则其邻接表需要N个头结点+2e个表结点。邻接表的存储空间为O（n+2e）、有向图：O（n+e）。

④特别适合稀疏图存储。

⑤无向图中顶点V_i。的度为第i个单链表的结点数。

⑥方便计算任意顶点的度（无向图）。

⑦有向图（就算出度方便，入度不方便）。

在这里插入图片描述

相关阅读:
vscode插件开发-发布插件
云安全技术发展综述
SolidWorks二次开发语法技巧及基础
计算机毕业设计之java+ssm基于android的家庭理财系统app
基于Hadoop架构的可视化大数据挖掘建模平台
nvm 安装管理node版本注意事项
spring5.0源码解析 Aop 04 配置通知器
LCR 150.彩灯装饰记录 II
2022年全球市场抗菌整理剂总体规模、主要生产商、主要地区、产品和应用细分研究报告
本地新建项目如何推到码云上去

原文地址：https://blog.csdn.net/CSDN_e_1/article/details/127869806