請教演算法中的 Minimum Spanning Trees
小弟聽好友說 這裡有很多熱心的 前輩 指導
特地 來這邊請益
有一題我看了不是說很懂
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
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
