algorithm - 图的所有子图 - 不知情的搜索（人工智能相关）

Question

我需要编写一个程序，该程序必须能够首先使用深度等算法找到图的所有子图。问题是我无法理解如何表示一组具有以下关系的节点：

A: A->B A->D A->F
B: B->A B->C 
C: C->B C->D
D: D->C D->A D->F
F: F->A F->D

在树中，所以我可以使用该算法。欢迎任何来源或解释。

Answer 1

图 G"(V",E") 是图 G(V,E) 的子图，如果：

1. V" 是 V 的子集

2. E" 必须具有来自 E 的所有边，它们连接 V 中存在的 2 个顶点"

存储任意数量顶点的所有子图空间复杂度：

TIME & SPACE = SUM { k * (|V|-k+1) } for k: 1..|V|

TIME & SPACE = 1/6 n (n+1) (n+2)

TIME & SPACE ~ O(|V|^3 + |V|^2 + |V| + ..)

在英语中，您将需要大量空间来保存 G 的所有可能子图。

TIME & SPACE ~ SUM { (|V|-k+1) * SPACE(Gk) }
    for k: 1..|V|, SPACE(Gk): size of sub-graph with k nodes

获得所有可能子图的算法是蛮力算法..

算法（Java）：

public class SubGraphs
{
    public static ArrayList<Graph> getAllSubsets (Graph g)
    {
        // i: 1,2,3 .. |V|
        for (int i=1; i<graph.V.size(); i++)
        {
            addSubsets(subsets, i);
        }
    }

    public static void addSubsets (ArrayList<Graph>, int i)
    {
        // generate all k-permutations from set V
        ArrayList<Node[]> perm = generateAllPerm(graph.V, graph.V.size()-i);

        // Ex: abc ~ 3:abc ; 2:ab,ac,bc ; 1:a,b,c
        for (Node[] p : perm)
        {
            subsets.add(removeVerticesFromGraph(graph, p));
        }
    }
}