时间戳

首页 > 解决方案 > 到达 DAG 中所有节点的最小节点子集

algorithm - 到达 DAG 中所有节点的最小节点子集

问题描述

假设我们有一个由节点 A、B、C、D 和 E 组成的 DAG。

每个节点都有一个可达节点列表 - 例如：

A --> B, C
A --> B
D --> E

在这种情况下，我们必须访问节点 A 和 D 才能全面访问图中的所有节点。一般来说，解决这个问题的最佳算法是什么？

标签： algorithm

解决方案

这是一种线性方法：

  1. 对于每个节点计数，它的度数（指向它的边数）
  2. 因为图是一个 DAG（无循环），我们可以将所有入度为 0 的节点作为我们的起始子集

时间复杂度（N + M） - 图大小线性

推荐阅读