Алгоритм нахождения всех циклов в ориентированном графе на C ++ с использованием матрицы смежности

Question

Учитывая матрицу смежности графа (например, g [] []), граф является направленным. Нужно найти количество всех циклов графа (если есть) и распечатать их.

Я пытался написать этот алгоритм на Java, иногда он работает правильно. Если граф имеет сложные циклы, алгоритм возвращает сумасшедшие циклы. Пожалуйста, посмотрите на мой код и помогите решить эту проблему

public static final int k = 6;

public static int g[][] = { { 0, 1, 0, 0, 0, 0 },
                            { 1, 0, 1, 0, 0, 0 },
                            { 0, 0, 0, 1, 0, 0 },
                            { 0, 0, 0, 0, 1, 0 },
                            { 0, 0, 1, 0, 0, 0 },
                            { 0, 0, 0, 0, 0, 0 } };

public static Vector stack = new Vector();

public static void printStack() {
    System.out.print("stack is: { ");
    for (int i = 0; i < stack.size(); i++) {
        System.out.print(stack.get(i) + " ");
    }
    System.out.println("};");

}

public static boolean checkCycle() {
    boolean res = false;

    for (int i = 0; i < stack.size() - 1; i++) {
        if (stack.get(i).equals(stack.lastElement())) {
            res = true;
            break;
        }

    }
    return res;
}

public static boolean go_to_line(int line) {
    boolean res = false;
    for (int i = 0; i < k; i++) {
        if (g[line][i] == 1) {
            stack.add(i);
            if (checkCycle() == true) {
                System.out.println("Cycle found!");
                res = true;
            } else {
                res = go_to_line(i);
            }
        }
    }

    return res;
}

public static int cycles_count() {
    int res = 0;

    for (int i = 0; i < k; i++) {
        if (g[i][i] == 1) {
            System.out.println("Knot detected at item {" + i + "}!");
            res++;
        }

        for (int j = i + 1; j < k; j++) {
            if (g[j][i] == 1) {
                stack.add(j);
                stack.add(i);

                if (go_to_line(i) == true) {
                    res++;

                    System.out.print("Final ");
                    printStack();
                    stack.removeAllElements();
                }
            }
        }
    }

    return res;
}

Answer 1

Эта проблема имеет экспоненциальную сложность в общем случае. Дело в том, что если каждая вершина соединена с каждой, то число циклов графа больше чем 2^n (любое подмножество узлов образует несколько циклов).

Таким образом, в общем случае нет хорошего алгоритма. Чтобы найти некоторый цикл, вы можете использовать поиск в ширину. Чтобы найти все циклы, вы должны использовать алгоритм грубой силы.

Answer 2

Если проблема в C ++, смените ее на другой язык. Насколько мне известно, C ++ не имеет особой функции, которая делает его более эффективным / удобным для работы с графами. В качестве альтернативы вы можете искать структуру, которая будет абстрагировать низкий уровень, позволяя вам сосредоточиться на вопросе высокого уровня. Для этой цели вы можете рассмотреть Boost Graph Library .