熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

數據結構考研分類復習真題 第七章 圖[35]

2013-11-15 15:15:41  來源: 數據結構 

  .考慮右圖

  ()從頂點A出發求它的深度優先生成樹

  ()從頂點E出發求它的廣度優先生成樹

  ()根據普利姆(Prim) 算法

  求它的最小生成樹【上海交通大學 六 (分)】

  在什麼情況下Prim算法與Kruskual算法生成不同的MST?【西安電子科技大學 計應用 一 (分)】

  .下面是求無向連通圖最小生成樹的一種方法

  將圖中所有邊按權重從大到小排序為(eeem)
  i:=
  WHILE (所剩邊數 >=頂點數)
  BEGIN
  從圖中刪去ei
  若圖不再連通則恢復ei
  i:=i+
  END

  試證明這個算法所得的圖是原圖的最小代價生成樹【北京郵電大學 五 (分)】

[]  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  


From:http://tw.wingwit.com/Article/program/sjjg/201311/23124.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.