T最早可以执行的任务是什么?必须先执行从依赖关系箭头到T的所有任务。您可以通过从T中搜索以得出可到达节点的权重之和来找到它们。
您可以执行的最新任务是什么?从U通过依赖箭头上的向后可完成的所有任务都必须稍后执行。同样,您可以通过从U进行搜索来找到可到达节点的权重之和。
图形是DAG,不一定要连接。周期没有意义。简单的DFS就可以满足搜索要求。
还有两个子问题。首先,您要避免对N个节点的图进行2N次搜索。这不难。无论从何处开始搜索,节点子级的权重总和都是相同的,因此在边缘上向前进行一次搜索就可以找到所有最早的时间,而在边缘后边进行一次搜索就可以找到最新的时间。
第二个子问题是如何表示图形。我们最多可以有500个顶点,但最多不能有500个边。因此,该图可能是稀疏的。对于DAG SEACH最有效的是邻接表。您将需要其中两个:一个用于前边缘,另一个用于后边缘。
假设您已经建立了一个邻接表表示,其中a[i].adj
是与节点i
相邻(向前)的节点的列表,任务持续时间在数组d[]
中。还要假设在建立邻接矩阵时,您要跟踪数组ni[]
中每个顶点的边缘数。我们想将最早的时间存储在数组e[]
中。
记住要搜索DAG,需要遍历所有节点以找到起点:对于前向搜索,没有边缘的节点(称为源),对于后边缘搜索没有边缘的节点(称为汇)。
然后用于正向搜索的伪代码将如下所示
def find_all_earliest() for i = 1 to v e[i] = UNASSIGNED for i = 1 to v if ni[i] = 0 // found a source find_earliest(i) // Return the sum of node weights of subtree rooted at `i`. def find_earliest(i) if e[i] != UNASSIGNED // Use already-computed value if there is one. return e[i] decendant_sum = 0 for a in a[i].adj decendant_sum += find_earliest(a) e[i] = decendant_sum return decendant_sum + d[i]
完成后,
e[i]
包含任务i
的最早开始时间。最新搜索将是对称的。答案是相应的最早时间和最新时间之间的差异。
此后,e[i]
包含任务i
的最早开始时间。