※ 引述《tkcn (小安)》之銘言： : ※ 引述《ythung (費瑪連珠)》之銘言： : : 本來在Math板問 : : 有高人指點可以來這裡請教(汗~~今天才知道ptt有這個板) : : 任給一圖(simple undirected graph) : : 如何找其所有induced連通子圖的總個數 : : 一些特定圖還可以用排列組合算 : : 但若特殊圖呢(目前我討論的圖頂點數最多20點) : 跑去 math 板看了原文，那幾位推文的強者根本就都會嘛 XD : 因為最多也才 20 個點，所以可能的解最多也只有 2^20 (約 10^6) : 就算每個解都跑一次 DFS/BFS，一組 Graph 我估計幾分鐘之內多半也能算完吧。 真是隔行如隔山(我以前是念純數的) DFS? BFS? 都不知是啥 剛去google一下 http://www.csie.ntnu.edu.tw/~u91029/GraphTraversal.html 才知道是"圖論中兩種遍歷演算法Depth-first Search和Breadth-first Search" 其實我在computer方面根本沒啥基礎 只有在大學(20年前的事了)修過資訊概論, 離散數學, 數值分析之類的課程 當時也學過BASIC,Pascal及C語言(但也差不多忘光了) 畢竟年代久遠了所以現在要重拾書本備感吃力(恐怕也有點緩不濟急) 但科展作品的修改(學生已通過校內初審)迫在眉睫 所以只好上網求教眾高手 我想問的是 這些圖的連通子圖總數如果用excel或maple(為了科展, 我最近才開始學的)有辦法作出來嗎? 如果以我原文任一個圖作一具體程式的實例 我可能就會更快速理解了 當然用我曾學過的語言也可以(只是我已不知道去那裡找那些語言的程式) : 如果要有效率一點的方式，可以從一個 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 這看起來更有效率 (因為我覺得學生的寫法太冗長了, 作2xn矩形就花了九頁) 但有更多不懂的名詞 對我來說很難理解... 不知大大能不能推薦一兩本經典的演算法入門書 我覺得我還是得多多研究, 自我充實 ※ 編輯: ythung 來自: 124.9.130.97 (02/23 00:20)