在图论中，有向无环图（DAG）的节点时间标记是进行拓扑排序、关键路径分析等算法的基础。介绍一种基于深度优先搜索的DAG节点时间标记算法，并对其进行优化以提高效率。

算法描述

该算法使用深度优先搜索遍历DAG，并在搜索过程中记录每个节点的开始时间和结束时间。开始时间表示节点被首次访问的时间，结束时间表示节点的所有邻接节点都被访问完毕的时间。

算法步骤：

  1. 初始化：创建一个数组 pre 用于存储每个节点的开始时间，创建一个数组 post 用于存储每个节点的结束时间，并将所有元素初始化为0。创建一个变量 tag 用于记录当前时间戳，初始化为0。
  2. 深度优先搜索：从DAG的任意一个节点开始进行深度优先搜索。
  3. 访问节点 cur 时，将 pre[cur] 设置为 ++tag，表示节点 cur 的开始时间为当前时间戳。
  4. 递归访问节点 cur 的所有未被访问的邻接节点。
  5. 当节点 cur 的所有邻接节点都被访问完毕后，将 post[cur] 设置为 ++tag，表示节点 cur 的结束时间为当前时间戳。
  6. 重复步骤2，直到所有节点都被访问。

算法优化

上述算法的时间复杂度为 O(V+E)，其中 V 是节点数，E 是边数。为了进一步提高效率，可以进行以下优化：

  • 使用邻接表存储图： 邻接矩阵的空间复杂度为 O(V^2)，而邻接表的空间复杂度为 O(V+E)。对于稀疏图，使用邻接表可以节省存储空间。
  • 标记已访问节点： 在深度优先搜索过程中，可以使用一个数组标记已经访问过的节点，避免重复访问。

总结

介绍了一种基于深度优先搜索的DAG节点时间标记算法，并对其进行了优化。该算法简单易懂，效率较高，可以应用于各种图论算法中。