DAG

有向无环图(DAG)是一种图结构,由一组节点和一组有向边组成,其中每条边都有方向,从一个节点指向另一个节点,且图中不包含任何环(即无法从一个节点出发,沿有向边最终回到同一节点)。因此,DAG 是一种无环的有向图。

DAG 在任务调度、编译器优化、依赖分析等诸多领域有着广泛的应用。在这些应用中,DAG 通常用于表示任务之间的依赖关系或计算过程中的数据流。

拓扑排序

拓扑排序是图论和项目管理中的一种基础算法,用于对有向无环图(DAG)的节点(或任务)进行线性排序。拓扑排序的目标是安排节点的顺序,使得对于每条有向边 (u, v),节点 u 在线性顺序中都出现在节点 v 之前。换言之,它在尊重依赖关系的前提下,为完成任务或处理元素建立一致的顺序。

关于拓扑排序的要点:

  1. 有向无环图(DAG):拓扑排序只能应用于无环的有向图。这是因为环会使任务顺序产生歧义,从而无法得到拓扑序。

  2. 依赖解析:当您有一组存在依赖关系的任务或活动时,拓扑排序尤为有用。它确保任务按正确的顺序执行,因此依赖其他任务的任务绝不会在其前置条件完成之前开始。

  3. 应用:

    • 项目管理:拓扑排序有助于安排项目中的任务,确保项目按时完成。
    • 编译器优化:在编译器设计中,它有助于确定生成代码或优化程序片段的最佳顺序。
    • 依赖分析:在软件工程中用于分析模块、函数或类之间的依赖关系。
    • 课程安排:在学术机构中,它有助于根据先修课程安排课程。
  4. 算法:有多种算法可以执行拓扑排序。深度优先搜索(DFS)和广度优先搜索(BFS)是常用的方法。算法的选择取决于问题的具体需求。

  5. 关键路径:拓扑排序还可以识别项目中的关键路径,即图中最长的路径。关键路径上的任务是那些一旦延迟就会导致整个项目延迟的任务。

  6. 多种有效顺序:需要注意的是,在给定的 DAG 中,可能存在多种有效的拓扑序。这种灵活性为优化、并行处理和资源分配提供了空间。

总体而言,拓扑排序是一种强大的工具,用于在广泛存在有向无环图的应用中管理依赖关系并确保任务按正确的顺序执行。

对有向无环图(DAG)执行拓扑排序有两种常用算法:深度优先搜索(DFS)和广度优先搜索(BFS)。这两种算法均可用于为图中的节点找到有效的拓扑序。以下是每种算法的说明:

  1. 深度优先搜索(DFS)算法:

    • 从 DAG 中的任意节点开始。
    • 对图执行深度优先遍历,将节点标记为已访问。
    • 当到达一个没有未访问邻居的节点(即叶节点)时,将其添加到拓扑顺序的开头。
    • 继续此过程,直到所有节点都被访问。

    基于 DFS 的拓扑排序算法的伪代码:

    function topologicalSort(graph):
        order = []
        visited = set()
    
        for each node in graph:
            if node is not visited:
                visit(node, order, visited)
    
        return reverse(order)
    
    function visit(node, order, visited):
        mark node as visited
        for each neighbor of node:
            if neighbor is not visited:
                visit(neighbor, order, visited)
        append node to order
  2. 广度优先搜索(BFS)算法:

    • 初始化一个空队列和一个用于存储拓扑顺序的列表。
    • 首先将所有没有入边的节点(入度为 0)入队。
    • 当队列中还有节点时,执行以下操作:
      • 出队一个节点,将其添加到拓扑顺序列表中。
      • 对于其每个邻居,将其入度减 1。
      • 如果某个邻居的入度变为 0,则将该邻居入队。
    • 重复上述过程,直到队列为空。

    基于 BFS 的拓扑排序算法的伪代码:

    function topologicalSort(graph):
        order = []
        queue = empty queue
    
        for each node in graph:
            if in-degree of node is 0:
                enqueue(node)
    
        while queue is not empty:
            node = dequeue(queue)
            append node to order
            for each neighbor of node:
                reduce in-degree of neighbor by 1
                if in-degree of neighbor is 0:
                    enqueue(neighbor)
    
        return order

基于 DFS 和 BFS 的算法都会为 DAG 生成有效的拓扑顺序。在两者之间选择取决于性能和问题的特定要求等因素。

计算 G 的拓扑排序为 O(n+m),其中 V = n 且 E = m