数据结构-图

数据结构-图

定义

图是一些顶点的集合,这些顶点通过一些边想连接,顶点用圈表示,边通过线表示,是一个多对多的数据结构。
可以拆分,就是点集V和边集E的集合。

特点

边可以是有方向的,只能单向前进,也可能是双向的,可以来回运动,也有的边带有权重,模拟为长度什么的物理量。

存储方式

  1. 邻接表
    每一个顶点会存储一个从该节点开始的链表,比如说A可以到BC,那么就是A->B->C。
  2. 邻接矩阵
    用一个矩阵来存储,假设A能到B且距离为5,那么m[0][1]=5.

相关术语

  1. 有向图:边是有方向的图
  2. 无向图:边没有方向,正反都可
  3. 简单图:不存在重复边,顶点不能直接到自身
  4. 完全图:任意两点都存在边(有向的话要有两条方向相反的边)
  5. 子图:点集和边集都是原图的子集,且构成图
  6. 顶点的度:以该顶点为一个端点的边的数目
---本文结束,感谢阅读---