按到端节点的距离对图进行排序

Question

我有一个图表中的节点列表。该图是有向的，不包含循环。此外，一些节点被标记为 "end" 个节点。每个节点都有一组我可以使用的输入节点。

问题如下：如何按到任何可达端节点的最大距离对列表中的节点进行排序（升序）？这是图表的外观示例。

我已经添加了计算的距离，之后我可以对节点进行排序（灰色）。末端节点的距离为 0，而 C、D 和 G 的距离为 1。但是，F 的距离为 3，因为通过 D 的方法会更短 (2)。

我做了一个我认为的概念，问题就解决了。这是一些伪代码：

sortedTable<Node, depth> // used to store nodes and their currently calculated distance
tempTable<Node>// used to store nodes 
currentDepth = 0;

- fill tempTable with end nodes

while( tempTable is not empty)
{

    - create empty newTempTable<Node node>

    // add tempTable to sortedTable
    for (every "node" in tempTable)
    {
        if("node" is in sortedTable)
        {
            - overwrite depth in sortedTable with currentDepth
        }
        else 
        {
            - add (node, currentDepth) to sortedTable
        }

        // get the node in the next layer
        for ( every "newNode" connected to node)
        {
            - add newNode to newTempTable
        }

        - tempTable = newTempTable  
    }
    currentDepth++;
}

这种方法应该有效。然而，该算法的问题在于它基本上是从基于每个端节点的图形创建树，然后为每个深度更正旧的距离计算。例如：G 的深度为 1（直接在 B 上计算），然后是深度 3（在 A、D 和 F 上计算），然后是深度 4（在 A、C、E 和 F 上计算）。

你有更好的解决这个问题的方法吗？

Answer 1

可以用dynamic programming来完成。

图是图上的DAG, so first do a topological sort，让排序顺序为v1,v2,v3,...,vn。

现在，为所有"end node"设置D(v)=0，并且从最后到第一（根据拓扑顺序）做：

D(v) = max { D(u) + 1, for each edge (v,u) }

之所以有效，是因为该图是一个 DAG，当以相反的拓扑顺序完成时，所有出边 (v,u) 的所有 D(u) 的值都是已知的。

图表中的示例：

拓扑排序（一种可能）：

H,G,B,F,D,E,C,A

那么，算法：

init: 

D(B)=D(A)=0

从后往前走：

D(A) - no out edges, done
D(C) = max{D(A) + 1} = max{0+1}=1
D(E) = max{D(C) + 1} = 2
D(D) = max{D(A) + 1} = 1
D(F) = max{D(E)+1, D(D)+1} = max{2+1,1+1} = 3
D(B) = 0
D(G) = max{D(B)+1,D(F)+1} = max{1,4}=4
D(H) = max{D(G) + 1} = 5

附带说明一下，如果图不是 DAG，而是一般图，则这是 Longest Path Problem 的变体，即 NP-Complete。
幸运的是，当我们的图是 DAG 时，它确实有一个有效的解决方案。

按到端节点的距离对图进行排序

sort graph by distance to end nodes

algorithm

sorting

graph

distance