图结构

图是一种由顶点和边组成的非线性数据结构,用于表示对象之间的关系。图结构在解决网络、路径和连接性问题方面具有广泛的应用,如社交网络、地图导航和网络流量分析等。

边列表数据结构可视化示例

边列表

一种简单直观的图表示方法,将所有的边存储在一个列表中,每条边包含起始顶点、目标顶点和可选的权重信息。

添加边: O(1)查找边: O(E)删除边: O(E)查询相邻顶点: O(E)
简单直观适合稀疏图边操作高效空间高效
有向图数据结构可视化示例

有向图

有向图是一种边具有方向性的图结构,图中的边从一个顶点指向另一个顶点。有向图广泛应用于网络流量分析、社交网络关系建模、任务依赖关系等场景。

添加边: O(1)查找边: O(E)拓扑排序: O(V+E)
单向边拓扑排序强连通分量入度/出度
无向图数据结构可视化示例

无向图

无向图是一种边没有方向的图结构,图中的边表示两个顶点之间的双向连接。无向图广泛应用于社交网络、地图导航、电路设计等场景。

添加边: O(1)查找边: O(E)连通分量: O(V+E)
双向边连通分量度数最小生成树
加权图数据结构可视化示例

加权图

加权图是每条边都有一个与之关联的数值(权重)的图结构。权重可以表示距离、成本、容量等概念,广泛应用于路径规划、网络流量分析等场景。

添加边: O(1)最短路径: O((V+E)logV)最小生成树: O(ElogE)
边权重最短路径最小生成树网络流
有向无环图 (DAG)数据结构可视化示例

有向无环图 (DAG)

有向无环图 (DAG) 是一种边有方向且不包含环的图结构,常用于表示任务的依赖关系、工作流程、以及系统中的资源调度等问题。

添加边: O(V+E)拓扑排序: O(V+E)关键路径: O(V+E)
无环拓扑排序关键路径分析调度
邻接矩阵数据结构可视化示例

邻接矩阵

邻接矩阵是一种表示图的常用方式,使用二维数组存储图中各顶点之间的连接关系。

添加边: O(1)查找边: O(1)删除边: O(1)
二维数组空间效率快速查找动态大小
邻接表数据结构可视化示例

邻接表

邻接表是一种表示图的常用方式,使用链表存储图中各顶点之间的连接关系。

添加边: O(1)查找边: O(E)删除边: O(E)
链表空间效率快速查找动态大小