一个拓扑结构题得实现（2011baidu校招研发部门的面试题目）

题目来自于友，今天无聊，试着把算法写出来活动一下脑子，题目如下：

有一个单入口，单出口的有向无环图。给出一个算法，在已有结点之间插入若干结点，使得从入口结点到出口结点经过的任意路径长度一致，详细描述你的算法思路，并分析其时间复杂度和空间复杂度。

分析：这个题的解显然是无数的，因为题目并没有限定任意路径长度的具体数字，只要一致即可。我们只考虑任意长度等于改图最大路径（长度），当然这里也没不要考虑权重。题目其实就变成了求任意节点P到结束点的最大路径，并平衡这个节点P到其后续节点最大路径差异。假设P有K个后续节点,N1,N2...,NK.我们知道P到结束点的最大路径Max(P)就等于Max(Max(Ni))+1,(i从1到K),而要最终任意路径长度一致，我们只要求出Max(P)后，对Max(Ni)进行对比，在P到Ni中插入Max(P)-1-Max(Ni)个节点即可，这种插入是不会影响到其它路径的。

1)算法实现：

struct Point
{
Point[] Nexts;//后续节点集合
bool Visited;//访问次数.
int MaxLen;
}
List<Point> Points;//这个集合包含所有的节点。目的主要是为了对图进行线性操作.

int MaxLength(Point p)
{
if(p.Visited==true)
{
return p.MaxLen;
}
p.Visited = true;
if(p.Nexts==null || p.Nexts.Length==0)
{
p.MaxLen = 1;
return 1;
}
int MaxLength = 0;
foreach(var item in p.Nexts)
{
int theLen = MaxLenght(item);
if(theLen>MaxLength)
{
MaxLength = theLen;
}
}
p.MaxLen = theLen+1;
foreach(var item in p.Nexts)
{
int InsertedPointCount = MaxLength-item.MaxLen;
Point P1 = p;
for(int i=1;i<= InsertedPointCount ;i++)
{
Point theTmp = new Point();
theTemp.MaxLen = item.MaxLen+(InsertedPointCount -i+1);
theTmp.Nexts.Add(item);
P1.Nexts.Remove(item);
P1.Nexts.Add(theTmp);
P1 = theTmp;
Points.Add(theTmp);
}
}
return p.MaxLen;
}
2)调用:开始节点为StartPoint.
初始化节点，主要是将访问标志和MaxLen进行重置，利用Points集合进行。
MaxLength(StartPoint).

3)分析：假设规模为n,时间复杂度主要是初始化，遍历和创建节点的时间，初始化的时间复杂度为θ(n),遍历的时间复杂度等于边数,最坏的情况是两两点之间都有连接，边数side=(n-1)n/2.那么时间复杂度T(n)<= n(n-1)/2=θ(n^2).创建节点的时间可以不考虑，那么这个算法的时间复杂度T(n)<=n(n-1)/2+n=θ(n^2).
空间复杂度：因为每个节点只会遍历一次，每访问一次，只需要常数个临时变量，因此其空间复杂度为Ω(n).(没有考虑补充节点部分）。

后记:关于拓扑结构的算法一般都非常具有实际应用价值,项目管理,流程优化,制造排程,产能预测等等,只是有的地方我们得通过一定的变换才能更好的应用.