图数据结构详解：有向无环图与最短路径

"本文主要介绍了图这一数据结构的相关知识，包括事件发生时间的计算公式，图的定义，术语，存储结构，遍历方法，连通性问题，有向无环图（DAG）及其应用，最短路径算法，以及一些核心概念如顶点，边，度，邻接点等。此外，还提到了图的子图，网络，稠密图与稀疏图的概念。" 在计算机科学中，图是一种重要的数据结构，它由一个顶点集V和一个弧集R构成，即Graph=(V,R)，用于表示对象之间的关系。有向图是指弧具有方向性，而无向图则没有方向。图的度是衡量一个顶点与其他顶点连接程度的指标，包括出度（以该顶点为起点的边数）和入度（以该顶点为终点的边数）。顶点的总度等于其出度与入度之和。 事件发生时间的计算公式在图的某些特定应用中非常重要，例如在拓扑排序或者最短路径算法中。这个公式用于确定图中节点的最早可到达时间（ve）和最晚必须离开时间（vl）。在有向无环图（DAG）中，拓扑排序可以找出所有节点的一个线性次序，使得对于每条边(u, v)，节点u都在节点v之前。计算公式如下： ve(源点) = 0； // 源点的最早发生时间为0 ve(k) = Max{ve(j) + dut(<j, k>)}； // 其他节点的最早发生时间为所有入边源节点的最早发生时间加上边的延迟的最大值 vl(汇点) = ve(汇点)； // 汇点的最晚离开时间等于其最早发生时间 vl(j) = Min{vl(k) – dut(<j, k>)}； // 其他节点的最晚离开时间为所有出边目标节点的最晚离开时间减去边的延迟的最小值 图的遍历方法主要有深度优先搜索（DFS）和广度优先搜索（BFS），它们在解决图的问题中起到关键作用，比如寻找路径、判断连通性等。连通图是指图中任意两个顶点之间都存在路径，连通分量则是图中最大的连通子图。对于强连通图，从任一顶点出发都可以到达其他所有顶点。 图的存储结构通常分为邻接矩阵和邻接表两种。邻接矩阵用二维数组表示，邻接表则使用链表节省空间。在处理大规模图时，邻接表通常更为高效，特别是在处理稀疏图时。 无向完全图有n(n-1)/2条边，有向完全图有n(n-1)条弧。当边或弧数量少于nlogn时，图称为稀疏图，反之为稠密图。图的子图是原图的一部分，包含部分顶点和这些顶点间的边。 最后，生成树是图的一个子集，它包含了所有顶点并且没有环，形成一个树形结构，而生成森林是多个生成树的集合，对应于无向图的连通分量。在实际应用中，例如网络路由、任务调度等领域，图的各种性质和算法有着广泛的应用。