作者learnerQQ (小铨)
看板C_and_CPP
标题请教演算法中的 Minimum Spanning Trees
时间Sun Jun 14 18:25:12 2009
小弟听好友说 这里有很多热心的 前辈 指导
特地 来这边请益
有一题我看了不是说很懂
Q: Let G = (V,E) be a connected,undirected graph with a real-value
weight function w defined on E.
Let A be a subset of E that is included in some minimum spanning
tree for G, let (S,V-S) be any cut of G that respects A, and let
(u,v) be a light edge crossing (S,V-S). please show that edge
(u,v) is safe for A.
小弟 我知道 求 MST 最常见的 就是 Prime & Kruskal algorithm
这题说 A 是 G的 子树 并且把 G切成 两部分 (S,V-S)
并且 (u,v) be a light edge crossing (S,V-S)
如何 SHOW edge (u,v) is safe for A?
不是最小边 且不是不要有 Cycle 就好了吗?
题目要我 show 虾米阿=ˇ=
Q2: 为什麽 Prime 的 Time complexity is O(V lg V + E lg V)
直觉想法是 O(E lg V)
谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.39.26.144