图
约 290 字小于 1 分钟
2025-11-19
图 (Graph)
定义与概念
图是由顶点和边组成的非线性数据结构,用于表示对象之间的关系。
核心特点
- 关系建模:擅长表示复杂关系网络
- 灵活结构:可以是无向、有向、加权等
- 路径分析:支持最短路径、连通性分析
- 复杂算法:包含丰富的算法体系
主要类型
- 无向图:边没有方向
- 有向图:边有方向
- 加权图:边带有权重
- 连通图:所有顶点都连通
- 完全图:每对顶点都有边连接
基本操作复杂度
| 操作 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 存储空间 | O(V²) | O(V+E) |
| 添加顶点 | O(V²) | O(1) |
| 添加边 | O(1) | O(1) |
| 检查邻接 | O(1) | O(V) |
图算法复杂度
| 算法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 深度优先搜索 | O(V+E) | O(V) |
| 广度优先搜索 | O(V+E) | O(V) |
| Dijkstra算法 | O(E log V) | O(V) |
| 最小生成树 | O(E log V) | O(V) |
应用场景
- 社交网络分析
- 路由算法
- 推荐系统
- 依赖关系分析
- 神经网络
