问删除图中找到链的最小顶点数

EN

private boolean isSafe(int v, int graph[][], int path[], int pos) {
    if (graph[path[pos - 1]][v] == 0)
        return false;

    for (int i = 0; i < pos; i++)
        if (path[i] == v)
            return false;

    return true;
}


private void hamCycleUtil(int graph[][], int path[], int pos, List<int[]> paths) {
    if (pos >= adjMatrix.length) {
        return;
    }

    for (int v = 0; v < adjMatrix.length; v++) {
        if (isSafe(v, graph, path, pos)) {
            path[pos] = v;

            int[] copyOfPath = new int[adjMatrix.length];
            System.arraycopy(path, 0, copyOfPath, 0, adjMatrix.length);
            paths.add(copyOfPath);


            hamCycleUtil(graph, path, pos + 1, paths);

            path[pos] = -1;
        }
    }
}


public int createChain() {
    List<int[]> paths = new ArrayList<>();
    int[][] matrix = new int[adjMatrix.length][adjMatrix.length];
    for (int i = 0; i < adjMatrix.length; i++) {
        for (int j = 0; j < adjMatrix.length; j++) {
            if (adjMatrix[i][j]) matrix[i][j] = 1;
            else matrix[i][j] = 0;
        }
    }
    int[] path = new int[adjMatrix.length];
    Arrays.fill(path, -1);

    for (int i = 0; i < adjMatrix.length; i++) {
        path[0] = i;
        hamCycleUtil(matrix, path, 1, paths);
    }

    int[] maxPath = new int[adjMatrix.length];
    Arrays.fill(maxPath, -1);
    int quantityOfElems = 0;
    int maxPathLength = 0;
    for (int[] chain : paths) {
        for (int value : chain) {
            if (value == -1) {
                break;
            }
            quantityOfElems++;
        }
        for (int value : maxPath) {
            if (value == -1) {
                break;
            }
            maxPathLength++;
        }
        if (quantityOfElems >= maxPathLength) {
            maxPath = Arrays.copyOf(chain, chain.length);
        }
        maxPathLength = 0;
        quantityOfElems = 0;
    }

    /*
    for (int value : maxPath) {
        System.out.print(value + " ");
    }
    System.out.println();*/

    for (int i = 0; i < adjMatrix.length; i++) {
        for (int j = 0; j < adjMatrix.length; j++) {
            adjMatrix[i][j] = false;
        }
    }

    quantityOfElems = 0;
    for (int i = 0; i < maxPath.length - 1; i++) {
        if (maxPath[i] == -1 || maxPath[i + 1] == -1) break;
        adjMatrix[maxPath[i]][maxPath[i + 1]] = true;
        adjMatrix[maxPath[i + 1]][maxPath[i]] = true;
        quantityOfElems++;
    }

    return maxPath.length - quantityOfElems - 1;
}