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