OJ3-2_旅行商_拓扑排序

思路

这是一道假的旅行商问题，实际上是一个最长路径问题，需要用拓扑排序来解。

建表

本题因为用到拓扑排序，所以采取邻接表存储最为合适。

拓扑排序

采取不断删除入度为0的点的方法来进行拓扑排序。

得到最长路径

设以节点p为结尾的所有路径中最长的长度为length[p]

则如果p有前驱，length[p]=max(length[p的前驱])+1

如果p没有前驱，则length[p]=0

因此我们采取按照拓扑排序的序列逐步更新其后继的length的方法。这样当我们访问到每一个节点时，其前驱都应该是已经被访问的状态，因此其length的值是正确的。由递归证明可以证明length数组的每个值都是正确的。

由此，最长路径就等于max(length)

伪代码

build adjacency list(邻接表)
calculate the in-degree of every point

//拓扑排序
array[n]
for i from 0 to n-1:
    find a point whose in-degree is 0, regard it as p
    array[i]=p
    for q in the set of following points of p:
        q.in-degree--

//找最长路径
length[n]={0,0,……,0}
for i from 0 to n-1:
    for q in the set of following points of array[i]:
        length[q]=max(length[q],length[array[i]]+1)
longest_route=max(length)

本站总访问量次

评论