Enumerating all connected subgraphs of a given order from graphs is a computationally challenging task. In this paper, we propose two algorithms for enumerating all connected induced subgraphs of a given order from connected undirected graphs. The first algorithm is a variant of a previous well-known algorithm. The algorithm enumerates all connected induced subgraphs of order $k$ in a bottom-up manner. The data structures that lead to unit time element checking and linear space are presented. Different from previous algorithms that either work in a bottom-up manner or in a reverse search manner, an algorithm that enumerates all connected induced subgraphs of order $k$ in a top-down manner by recursively deleting vertices is proposed. The data structures used in the implementation are also presented. The correctness and complexity of the top-down algorithm is analysed and proven. Experimental results show that the variant bottom-up algorithm outperforms the other algorithms for enumerating connected induced subgraphs of small order, and the top-down algorithm is fastest among the state-of-the-art algorithms for enumerating connected induced subgraphs of large order.

翻译：从图形中列出一个给定顺序的所有连接的子图是一个具有计算挑战性的任务。 在本文中, 我们提出两个算法, 用来从连接的非方向图形中罗列一个给定顺序的所有连接的诱导子图。 第一个算法是以前众所周知的算法的变体。 算法以自下而上的方式罗列了所有连接的导致秩序的子图。 显示出导致单位时间元素检查和线性空间的数据结构。 不同于以前以自下而上或反向搜索方式工作的算法, 一种通过递归式删除顶端图以自上向下方式罗列所有连接的顺序的诱导子图。 也提出了执行时使用的数据结构。 分析和验证了上下调算法的正确性和复杂性。 实验结果显示, 变量自下而上而起的算算法超越了用于计算小顺序连接的诱导子图的其他算法, 而自上而下而下而上至下调的算法在计算大顺序的状态- 算法中速度最快。