图 (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)

应用场景

• 社交网络分析
• 路由算法
• 推荐系统
• 依赖关系分析
• 神经网络