- 搜標題
- 搜題干
- 搜選項
問答題
【簡答題】
對下圖所示的連通網(wǎng)絡G，用克魯斯卡爾（Kruskal）算法求G的最小生成樹T，請寫出在算法執(zhí)行過程中，依次加入T的邊集TE中的邊。說明該算法的貪心策略和算法的基本思想，并簡要分析算法的時間復雜度。
答案：
TE={（3，4），（2，3），（1，5），（4，6）（4，5）}
貪心策略是每次都在連接兩個不同連通分量的邊...
貪心策略是每次都在連接兩個不同連通分量的邊...
你可能感興趣的試題
問答題
【簡答題】
對下列各組函數(shù)f（n）和g（n），確定f（n）=O（g（n））或f（n）=Ω（g（n））或f（n）=θ（g（n）），并簡要說明理由。
（1）f（n）=2n；g（n）=n!
（2）f（n）=√n；g（n）=logn2
（3）f（n）=100；g（n）=log100
（4）f（n）=n3；g（n）=3n
（5）f（n）=3n；g（n）=2n
答案：
（1）f（n）=O（g（n）），因為g（n）的階比f（n）的階高。
（2）f（n）=Ω（g（n））...
（2）f（n）=Ω（g（n））...
