PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 任給一圖如何找induced連通子圖的總數

看板Prob_Solve (計算數學 Problem Solving)作者tkcn (小安)時間13年前 (2011/02/22 10:42)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串2/4 (看更多)

※ 引述《ythung (費瑪連珠)》之銘言： : 本來在Math板問 : 有高人指點可以來這裡請教(汗~~今天才知道ptt有這個板) : 任給一圖(simple undirected graph) : 如何找其所有induced連通子圖的總個數 : 一些特定圖還可以用排列組合算 : 但若特殊圖呢(目前我討論的圖頂點數最多20點) 跑去 math 板看了原文，那幾位推文的強者根本就都會嘛 XD 因為最多也才 20 個點，所以可能的解最多也只有 2^20 (約 10^6) 就算每個解都跑一次 DFS/BFS，一組 Graph 我估計幾分鐘之內多半也能算完吧。如果要有效率一點的方式，可以從一個 node 開始(此時必為 connected)，用 BFS 每次把現有的解加入一個 neighbor，形成一個新的解。因為加的都是 neighbor，所以必定 connected。如果新的解先前已經產生過就略過不計， BFS 總共經過幾回合就會是答案了。 (突然覺得這解法跟上面有篇樂透的根本一樣嘛) 繼續加速的技巧也跟樂透一樣，善用 bitwise operations。每一組解都對應成 bits pattern， adjacency matrix 也用 bits 來表示，這樣在加入新 neighbor 的地方，就可以用 bitwise operations 達成。舉例來說目前的解為 {3}，state 就會是 00000100 {3} 有兩個 neighbors: {1},{5}，adj 為 00010001 第一步先加入 {1}，新的 state 成為 00000101，假設 {1} 的 neighbors 為 {2},{3},{6}，adj 即為 00100110。那麼 {1,3} 的 neighbors 就可以直接算出: 00010001 | 00100110 & (~00000101) = 00100010 ^ ^ ^ ^ | | | 新的 state 的 neighbors | | 新的 state | 新加入 vertex 的 neighbors 原state 的 neighbors -- ◤ ◥ ◢ ◣ T$，修好它吧。 ⊙▁⊙─ ─⊙▂⊙ 碰到問題，用SoftICE就對了！ ╰ ∕皿﹨ ◥皿◤ ╯ ◥█◤◢ ◥ ︶◤ Lee ◤ ︶ ◥◤ ﹨▼∕◥ T$ Chen ＭＹＴＨＢＵＧＴＥＲＳ ◥ ◤＼◥ by dajidali -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.114.78.231