有向无环图的函数定义

Question

让我们考虑以下问题：对于有向无环图 G = (V,E) 我们为每个顶点 u 定义函数 "levels"，作为 l(u) 使得：
1. l(u)>=0 对于每个 u
2.如果有一条从u到v的路径(u -> v)那么l(u)>l(v)
3.对于每个顶点u，l(u)是同时满足条件1和2的最小整数。

问题说：
a. 证明对于每个 DAG，上述函数都是唯一定义的，即它是唯一满足条件 1,2 和 3 的函数。
b. 找到一个 O(|V| + |E|) 算法为每个顶点计算此函数。

下面是一个基于拓扑排序的可能算法：首先，我们找到 G 的转置，它是 G^T，定义为 G^T = (V,E^T)，其中 E^T={(u,v): (v,u) is in E} 如果基于邻接表实现，则总共需要 O(|V|+|E|)： (O(|V|) 分配和 sum for all v in V of |Adj[v]| = O(|E|))。拓扑排序需要 Theta(|V|+|E|)，因为它包括 BFS 和列表中的 |V| 插入，每个插入需要 O(1).

TRANSPOSE(G){
    Allocate |V| list pointers for G^T i.e. (Adj'[])
    for(i = 1, i <= |V|, i++){
        for every vertex v in Adj[i]{
            add vertex i to Adj'[v]
        }
    }
}
L = TopSort(G)

Answer 1

假设您有 G 的拓扑排序。然后你可以考虑颠倒顺序的顶点：如果你有一条 u -> v 边，那么 v 在顺序上排在 u 之前。

如果按此顺序在节点上循环，则如果没有出边则让 l(u) = 0 和 l(u) = 1 + max(l(v), for each v such that there is an edge (u, v))。这是最优的，给你一个 O(|V| + |E|) 算法来解决这个问题。

证明留作练习。 :D

Answer 2

a. Prove that for every DAG the above function is uniquely defined, i.e. it's the only function that satisfies conditions 1,2 and 3.

也许我遗漏了什么，但这对我来说似乎很明显：如果您将其定义为满足这些条件的最小值，怎么可能有多个？

b. Find an O(|V| + |E|) algorithm that calculates this function for every vertex.

我认为你的拓扑排序思路是正确的（注意拓扑排序是一个BFS），但是应该在转置图上进行（将每条边的方向反转).然后拓扑排序中的第一个值得到 0，下一个得到 1 等等。例如，对于转置图：

1   2   3
*-->*-->*
        ^
*-------|
1

我已经根据节点在拓扑排序中的位置对它们进行了编号。您通过使用 BFS 实现拓扑排序来为节点编号。当您从 FIFO 队列中提取一个节点时，您会从其所有可达节点的入度中减去 1。当该入度变为 0 时，您将它变为 0 的节点插入队列中，并将其编号为 exracted_node + 1。在我的示例中，编号为 1 的节点从入度 0 开始。然后，最底部的 1 减去一个来自标记为 3 的节点的入度，但该入度将为 1，而不是零，因此我们不将其插入队列。但是我们插入 2 因为它的入度将变为 0.

伪代码:

G = G^t
Q = a FIFO queue
push all nodes with indegree 0 in Q
set l(v) = 0 for all nodes with indegree 0
indegree(v) = how many edges are going into node v
while not Q.Empty():
  x = Q.Pop()
  for all nodes v reachable from x:
    if indegree[v] > 0:
      indegree[v] = indegree[v] - 1
      if indegree[v] == 0:
        Q.Push(v)
        l[v] = l[x] + 1

您也可以使用 DFS 来实现，该 DFS 在递归 returns 后计算每个节点的值，如：

value(v) = 1 + max{value(c), c a child of v}

注意DFS在转置图上不是dont，因为我们会让递归处理拓扑排序顺序的遍历。

有向无环图的函数定义

A function definition for directed acyclic graphs

algorithm

graph

topological-sort

vertex

directed-acyclic-graphs