※ 引述《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