次小生成树

请问有没有求 次小生成树（就是代价第2小的） 的比较好的方法？
2000个结点，20000条边，最好能在O(n^2)以内


☆──────────────────────────────────────☆
    RobertLu (老妖怪) 于 2002年04月12日17:14:33 星期五 提到：

请问这里“次小”的定义是什么？
如果有两棵不同的最小生成树，其中一棵是否是这里说的“次小”？



☆──────────────────────────────────────☆
    dwyak (ArthurKing) 于 2002年04月12日18:35:56 星期五 提到：

如果有两棵最小生成树的话，其中一棵就是“次小”
或者可以假设，有唯一的最小生成树，求次小生成树


☆──────────────────────────────────────☆
    ender (ender) 于 Fri Apr 12 20:16:15 2002) 提到：

2000*20000算不算O(n^2)的？



☆──────────────────────────────────────☆
    dwyak (ArthurKing) 于 2002年04月12日20:22:20 星期五 提到：

2000*20000，如果系数很小的话，可以承受
如果是用fibonacci heap做的话，恐怕就要超时了


☆──────────────────────────────────────☆
    ender (ender) 于 Fri Apr 12 20:41:26 2002) 提到：

可以证明：对任何最小生成树T，有一棵次小的T1和T只差一条边。这已经给出20
00*20000的了。
Sorry, must leave now.


☆──────────────────────────────────────☆
    turboc (等待也是快乐的) 于 2002年04月12日20:45:50 星期五 提到：

【 在 ender (ender) 的大作中提到: 】
: 可以证明：对任何最小生成树T，有一棵次小的T1和T只差一条边。这已经给出20
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~这一步我还没想通
: 00*20000的了。
: Sorry, must leave now.


☆──────────────────────────────────────☆
    dwyak (ArthurKing) 于 2002年04月12日21:20:56 星期五 提到：

真的可以证明吗？如果可以的话，O(n^2+e)就可以解决了：）

☆──────────────────────────────────────☆
    ender (ender) 于 Fri Apr 12 21:54:24 2002) 提到：

Yes, O(n^2).
We need a table s[][] such that s[A][B] records the largest edge from
A to B on the MST. And we can get this by the following:
In Prim's algo, we grow the vertex set S, every time we find a new ver
tex v, we can get S[v][w] for all w already in S.

Must leave again, I will write a proof for the claim in 2 hours.



☆──────────────────────────────────────☆
    ender (ender) 于 Fri Apr 12 23:30:16 2002) 提到：

For any two trees T1 and T2, let c(T1,T2) be the number of edges in bo
th T1 and T2.

Suppose T is a MST. Let T0 be any tree other than T. Enough to show th
ere is a sequence T0, T1, ... Tk such that c(T,Ti) are increasing, and
cost of Ti's are non-increasing.

Just need to show one step:
Select any edge uv on T0, delete it from T0, T0 fall apart into A and
B. Since T is a MST, there is at least one edge u'v' in T connects A a
nd B and cost of u'v' not higher than uv, otherwise uv must be in T, t
he MST.
So, set T1=T0-uv+u'v', the cost is not increasing.


☆──────────────────────────────────────☆
    turboc (等待也是快乐的) 于 2002年04月13日10:40:15 星期六 提到：

我想通了，看上去是显然的，但是阶为何是O(n^2+E)，好像是O(E)



☆──────────────────────────────────────☆
    ender (ender) 于 Sat Apr 13 12:40:18 2002) 提到：

求MST的时间是多少？



☆──────────────────────────────────────☆
    dwyak (ArthurKing) 于 2002年04月13日19:44:12 星期六 提到：

MST可以O(elogn)的（e<=20000）
求任意结点a和b之间最长边的复杂度是O(n^2)