随着包括化学情报学、生物信息学、计算机视觉、视频索引、文本检索以及Web分析在内的广泛应用,图作为一种一般数据结构在复杂结构和它们之间相互作用建模中变得越来越重要。为了进一步进行特征化、区分、分类和聚类分析,挖掘频繁子图模式已经成为一项重要的任务。近年来,频繁子图挖掘已经成为数据挖掘中一个活跃和重要的课题。　　 本文对基于图论的经典频繁子图挖掘算法进行了系统的研究和全面的总结,在此基础上提出了基于深度优先策略的频繁导出子图挖掘算法CISM(ConnectedInduced Subgraph Mining)。CISM采用基于顶点的扩展策略。首先扫描图集,找到图集中的频繁点,并把非频繁点从图集中删除,降低问题的规模；然后找到图集中的频繁边,将频繁边按支持度降序排列；接下来对每一条频繁边进行深度优先搜索,扩展生成候选导出子图,找到该边的所有候选导出k-子图,紧接着对这些候选导出k-子图进行支持度计数,得到频繁导出k-子图,再由这些频繁导出k-子图找到频繁导出(k+1)-子图,直到不能找到更大规模的频繁子图,即完成对该频繁边的所有扩展；然后将该频繁边从图集中删除,进入另一条频繁边的扩展；该方法能够有效地减少冗余子图的生成,提高挖掘的效率。通过真实的PTE化合物数据测试,CISM算法能够准确、高质量地挖掘图集中的频繁导出子图。