0

考虑到顶点集 V = {v_1, ... , v_n} 的无向图 G = (V,E)，我正在尝试为最小顶点覆盖问题提出回溯算法。给定一个 n 顶点图的邻接列表 Adj[1...n] 输出 G 的最小顶点覆盖的大小。我不想使用修剪。

我定义了参数 Adj[1..n], int i 来表示我们目前已经涵盖的 Adj 的索引，以及非负 int vertexCover 来表示顶点覆盖。我的想法是当我们覆盖 Adj[1..n] 中的所有顶点时停止，如果我们还没有完成，我想首先检查是否存在连接到 G 中所有其他顶点的顶点，因为然后这个顶点显然将是解决方案。如果不存在这样的顶点，我想将邻接列表转换为一棵树，我可以在其中递归调用我的函数来遍历树。我还在考虑创建一个 int 数组 A 来记录作为最小顶点覆盖一部分的顶点的索引。

我在下面分享我的pseducode，我目前在如何在树中进行选择时遇到问题，我相信 MinVertexCover(Adj, i + 1, vertexCover) 将遍历树（因此它将访问根的孩子），但我不确定如何决定是否包括该孩子和/或继续下一个孩子。

MinVertexCover(Adj[1..n], int i, int vertexCover)
   n = length(Adj)
   if i = n 
      return vertexCover
   else 
      for k = 1 to n
          if length(Adj[k]) = n - 1 
             A.add(k)
             vertexCover = length(A)
          else
             minVertexCover(Adj, i + 1, vertexCover)
          return minVertexCover
4

0 回答 0