图(Graph):复杂关系的数学模型与遍历算法
图是一种用于描述多对多关系的数据结构,由节点(顶点) 和边组成,广泛应用于地图导航、社交网络、电路设计等场景。与树的 “层次化” 结构不同,图的节点可以任意连接,能更灵活地表达现实世界中的复杂关系。
图的基本概念与分类
核心定义
- 顶点(Vertex):图中的基本元素(如城市、用户)。
- 边(Edge):连接两个顶点的关系(如道路、好友关系)。
- 邻接:若两个顶点之间有边相连,则互为邻接点。
图的分类
(1)按边的方向性
- 无向图:边没有方向,顶点
u与v的边可表示为(u, v),且(u, v) = (v, u)(如双向道路)。 - 有向图:边有方向,顶点
u到v的边表示为<u, v>,与<v, u>不同(如单向街道、微博关注)。
(2)按边的完整性
- 完全图:
- 无向完全图:每个顶点与其他所有顶点都有边,含
n个顶点的无向完全图有n(n-1)/2条边。 - 有向完全图:每对顶点之间有两条方向相反的边,含
n个顶点的有向完全图有n(n-1)条边。
- 无向完全图:每个顶点与其他所有顶点都有边,含
(3)其他常见类型
- 稀疏图:边数远少于完全图的图(如社交网络中用户的好友关系)。
- 稠密图:边数接近完全图的图(如电路中的节点连接)。
图的存储结构
图的存储需高效表达顶点与边的关系,常用方式有邻接矩阵和邻接表。