algorithm - "maximally packed"DAG中每个节点的计算深度

Question

(注意:我考虑过在 https://cstheory.stackexchange.com/ 上提出这个问题，但认为我的问题不够理论化——它是关于算法的。如果这篇文章有更好的 Stack Exchange 社区，我很高兴听!)

我使用的术语“起始节点”表示没有链接的节点，“终端节点”表示没有链接的节点。所以下图有起始节点A和B以及终止节点F和G:

我想按照以下规则绘制它:

• 至少一个起始节点的深度为0。
• 链接总是从上到下
• 节点尽可能垂直排列

使用这些规则，上图中显示了每个节点的深度。有人可以建议一种算法来计算运行时间少于 O(n^2) 的每个节点的深度吗？

更新:

我调整了图表以显示 DAG 可能包含不同深度的起始节点和终端节点。 (这是我在最初的错误答案中没有考虑的情况。)我还将术语从“x 坐标”切换为“深度”，以强调这是关于“图形”而不是“图形”。

Answer 1

您的节点的 x 坐标对应于从任何节点到该节点的最长路径，没有引入边。对于 DAG，它可以在 O(N) 中计算:

given DAG G:
  calculate incomming_degree[v] for every v in G
  initialize queue q={v with incomming_degree[v]==0}, x[v]=0 for every v in q
  while(q not empty):
     v=q.pop()  #retreive and delete first element
     for(w in neighbors of v):
          incomming_degree[w]--
          if(incomming_degree[w]==0): #no further way to w exists, evaluate
               q.offer(w)
               x[w]=x[v]+1

x 存储所需的信息。