1. 首頁
  2. 問答
  3. 使用貪婪算法找到樹的最小尺寸主導集合

使用貪婪算法找到樹的最小尺寸主導集合

2011-03-15 46 views
2

支配集（DS）：=給定無向圖G =（V; E），頂點集合如果對於V中的每個頂點，在與v相鄰的S中有一個頂點。整個頂點集合V是任何圖中的平凡支配集合。使用貪婪算法找到樹的最小尺寸主導集合

查找樹的最小尺寸控制集。

來源

2011-03-15 SecureFish

+0

我認爲這個規則很清楚：選擇兩個節點的父節點。對於兩個子樹，選擇該子樹的根節點。 – SecureFish 2011-03-15 17:07:59

+0

問題是什麼？ – NPE 2011-03-15 17:10:25

+0

暈倒。使用貪婪爲樹找到最小尺寸的主導集合。 – SecureFish 2011-03-15 17:14:08

回答

1

看起來相當簡單。

  1. 按頂點數排序頂點。
  2. 抓住第一個。
  3. 抓住下一個，如果它與目前爲止沒有任何抓取相鄰。
  4. 如果超出頂點，END，否則，轉至2

來源

2011-03-15 17:20:43 corsiKa

+0

貪婪表示你可能會在那裏排序 – corsiKa 2011-03-15 17:24:31

+0

這是我的想法： – SecureFish 2011-03-15 17:44:42

+0

挑選一個未遮蓋的葉子，選擇其父項並將其添加到集合中; – SecureFish 2011-03-15 17:45:14

0

你作出有關頂點的權重什麼假設？在這個問題的典型表述中，頂點可以被加權。

來源

2012-03-06 03:18:31 solvingPuzzles

2

1-始終從葉子

開始

2-加入他們的父母到DS和削減兒童

3-馬克父母爲主導已經

4-完成程序選出的父，檢查的無論是那些標節點有一個孩子，是不是
爲主，將它們添加到DS

好運

來源

2013-04-17 16:32:31

+0

？你不需要先排序節點嗎？ – newbieLinuxCpp 2013-04-18 22:42:53

+0

根本不需要排序，是的它是O（| V | + | E |）中的線性時間，您不應該考慮時間複雜度中節點之間移動的代價，只是比較的次數。 – 2013-04-20 02:39:23

相關問題

 相關問題