1

我试图在图中找到最大集团（邻接矩阵），该图最多可以有 50 个节点。目前，当图形大小达到 n = 40 左右时，我已经开始永远花费。谁能找到我可以做的任何优化？

  public static void maxClique(Graph graph, List<Integer> clique) {
    //Get the newest node added to the clique
    int currentValue = clique.get(clique.size() - 1);

    if (clique.size() > max.size()) {
      max = clique;
    }

    // Check every node
    for (int i = 0; i < graph.size; i++) {

      // If the node being checked is connected to the current node, and isn't the current node
      if (graph.matrix[currentValue][i] == 1 && !clique.contains(i)) {
        //Check if the new clique is bigger than the current max.


        //Make a new clique and add all the nodes from the current clique to it
        ArrayList<Integer> newClique = new ArrayList<>();
        newClique.addAll(clique);
        //Add the new node
        newClique.add(i);

        //Repeat
        if (makesNewClique(graph, clique, i)) {
          maxClique(graph, newClique);
        }
      }
    }
  }

全类内容：https : //pastebin.com/fNPjvgUm 邻接矩阵：https ://pastebin.com/yypN9K4L

4

1 回答 1

1

David Eisenstat 的评论给出了答案，这是我为以后来到这里的任何人提供的代码：

  public void bronKerbosh(Set<Integer> p, Set<Integer> r, Set<Integer> x) {
    if (x.isEmpty() && p.isEmpty() && r.size() > max.size()) {
      max = new ArrayList<>();
      max.addAll(r);
    }

    Object[] pArr = p.toArray();
    for (Object vTemp : pArr) {
      int v = (int)vTemp;

      Set<Integer> newR = new HashSet<>();
      newR.addAll(r);
      newR.add(v);

      bronKerbosh(intersect(p, neighbors(v)), newR, intersect(x, neighbors(v)));
      p.remove(v);
      x.add(v);
    }
  }
于 2020-10-04T05:00:21.403 回答