图
图是一种非线性结构，由顶点和边构成，我们可以将图抽象的表示为一组顶点和边的集合
我们将顶点看作节点，将边看作各个节点的引用(指针)，我们就可以将图看作是一种从链表拓展过来的 数据结构
图的常见类型与属于
- 根据边是否有方向，可以将图分为有向图和无向图
- 在无向图中，边表示两个节点“双向链接”
- 在有向图中，边具有方向性，即A->B和B->A两个边的方向是独立的
- 根据所有节点是否连通，可以分为连通图和非连通图
- 对于连通图，从某个节点出发，可以到达任意一个节点
- 对于非连通图，从某个节点出发，至少有一个节点无法直接到达
- 我们可以为边添加“权重”变量，从而得到有权图
常用术语：
- 邻接：当两个节点之间存在边相连接时，这两个节点邻接
- 路径：从顶点A到顶点B所构成的边的序列称为从A到B的路径
- 度：一个顶点拥有的边数
图的表示
一般有“邻接矩阵”和“邻接表”表示
邻接矩阵
设图的顶点数量为 n，「邻接矩阵 adjacency matrix」使用一个 n×n 大小的矩阵来表示图，每一行（列）代表一个顶点，矩阵元素代表边，用 1 或 0 表示两个顶点之间是否存在边
-
特性
- 顶点不能与自身相连，因此邻接矩阵主对角线元素没有意义
- 对于无向图，两个方向的边等价，此时邻接矩阵关于主对角线对称
- 将邻接矩阵的元素从 1 和 0 替换为权重，则可表示有权图
- 使用邻接矩阵表示图时，我们可以直接访问矩阵元素以获取边，因此增删查改操作的效率很高，时间复杂度均为 O(1) 。然而，矩阵的空间复杂度为 O(n2) ，内存占用较多。
邻接表
使用 n 个链表来表示图，链表节点表示顶点。第 n 个链表对应顶点 n ，其中存储了该顶点的所有邻接顶点文章来源：https://www.toymoban.com/news/detail-816950.html
邻接表仅存储实际存在的边，而边的总数通常远小于 n2 ，因此它更加节省空间。然而，在邻接表中需要通过遍历链表来查找边，因此其时间效率不如邻接矩阵文章来源地址https://www.toymoban.com/news/detail-816950.html
到了这里，关于数据结构之图的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
