java - 在多项式时间内使用 DFS 的最小命中集算法

Question

我需要编写一个算法来找到给定无向图的最小命中集 F，即包含图的每个循环中的最小边的集合，使得 F 与任何给定循环的交集不为空。我编写了一个算法，该算法使用深度优先搜索来查找图中所有可能的循环，然后在每个循环中取最小边并将其放入一个集合中(我在其中删除了重复项)。

但是，我被要求在多项式时间内完成这项任务，我不太确定我的算法能做到这一点。例如，我添加了一个计数器来解决以下从 A 开始的图形，我的 DFS 方法被调用了 34 次:

谁能帮我计算一下我写的算法的运行时间？它是功能性的，但似乎效率很低。谢谢

这是我的 DFS 方法的代码。 MHS 是像节点一样工作的基本数据结构。它们有一个标签和一个链接列表，其中包含一个端点(另一个节点)和一个与之关联的整数值)。 cycles 只是一个包含所有循环的 ArrayList，它们本身表示为边值的 ArrayList。

我使用了这篇文章 https://stackoverflow.com/a/549312/1354784 中描述的方法.

public static void DFS(MHS v){
    ++counter;
    if(v.visited){
        MHS current=v.predecessor;
        ArrayList<Integer> currEdges=new ArrayList<Integer>();
        currEdges.add(getEdgeValue(current, v));
        while(!current.equals(v)){
            MHS p=current.predecessor;
            if(p==null)
                break;
            currEdges.add(getEdgeValue(p, current));
            current=p;
        }
        if(currEdges.size()>0)
            cycles.add(currEdges);
    }else{
        v.visited=true;
        for(int i=0;i<v.links.size();i++){
            MHS w=v.links.get(i).next;
            if(v.predecessor==null || !v.predecessor.equals(w)){
                if(v.visited){
                    MHS ok=w.predecessor;
                    w.predecessor=v;
                    DFS(w);
                    w.predecessor=ok;
                }else{
                    w.predecessor=v;
                    DFS(w);
                }
            }
        }
        v.visited=false;
    }
}

Answer 1

您真的是从找出图中的每个循环开始的吗？如果你有完整的图 Kn，其中每对节点都是连接的，那么任意大小的节点的每个有序集都定义了一个环，因此环的数量呈指数增长。

你可以尝试类似的东西

While (there are any cycles left)
  Find a cycle
  find the shortest edge in that cycle
  remove that edge from the graph

这应该是多项式时间，因为 while 循环的每次循环都会从图中删除一条边，迟早你会用完所有边。

但我不确定这是否回答了您的问题。我还注意到命中集合的标准定义是一个 NP 完全问题，通过集合封面 - https://en.wikipedia.org/wiki/Set_cover_problem#Hitting_set_formulation