Posted on 2013-05-26 10:40
鑫龙 阅读(244)
评论(0) 编辑 收藏 引用 所属分类:
数据结构与算法
题目：一个单入口单出口的有向无环图中，要求在某些地方插入一些节点使得任何一条由起点到终点所经历的节点数相同，类似于下面的图，要求给出算法描述并分析时间复杂度。
如上图所示，节点A到C有两条路径，ABC这条路径经过了一个节点，而AC路径经过了0个节点，我们的算法所要做的事就是要在AC路径中间加入一个节点，然后ABC路径和ADC路径都经过了一个节点。
算法是这样的：对于每个节点维护一组信息，包括节点的层数（起始节点到该节点的路径长度，起始节点设为0）以及生成该长度的父节点，相对于右图，节点6维护的不经处理的信息就是：层数2来自节点3和节点4；节点7维护的不经处理的信息就是：层数3来自节点5和节点6以及层数2来自节点4；节点8的不经处理的信息是：层数4来自节点7，层数3来自节点7，层数2来自节点4。我们算法所要做的事就是最终使每个节点需要维护的层信息变为一个，即无论从那条路径到该节点，该节点所处的层数都是固定的。算法如下：1、初始化起始节点的层数信息2、从起始节点开始遍历每条路径，遇到每个节点生成一个维护信息（1）如果此节点不存在维护信息，创建之；（2）如果该节点存在维护信息，有两种情况：（a）如果生成的维护信息的层数和原来已有的维护信息的层数是相同的，则合并这两个维护信息，比如对于例子中的图，节点5原来的维护信息为“层数3来自节点2”，然后从节点3到节点5生成的维护信息为“层数3来自节点3”，由于层数相同，我们可以将其合并为“层数3来自节点2和节点3”；（b）如果生成的维护信息的层数和原来节点的维护信息的层数不一致，我们需要比较那一个的层数较大：a.如果原来维护信息的层数较大，此时，我们只需要在生成此维护信息的节点与此节点之间插入一个新的节点，然后生成新节点的维护信息，然后从新节点开始（2）过程b.如果新生成的维护信息的层数较大，将新生成的节点信息存入此节点，然后我们需要在生成原来维护信息的所有节点和此节点之间插入新节点，并且需要从所有的新插入节点开始（2）过程