Algorithmus für die Suche nach alle Zyklen in einem gerichteten Graphen auf C++ mit Angrenzens matrix

Gegebenen Graphen Nachbarschaft-matrix (ex. g[][]), graph gerichtet ist.
Bedürfnisse finden, die Anzahl aller Graphen Zyklen (falls vorhanden), und drucken Sie.

Versuchte ich schrieb dieses Algorithmus in Java, manchmal funktioniert es richtig. Wenn graph hat komplexe Zyklen, Algorithmus Rückkehr verrückte Zyklen. Bitte, Blick auf meinen code und helfen, um dieses problem zu beheben

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;
}
  • Ich bezweifle, dass irgendjemand wird schreiben Sie einfach den code für Sie. Brauchen Sie, um uns zu zeigen, was Sie versucht haben, zusammen mit mindestens einer Beschreibung des Problems(s), die Sie erlebt haben.
  • Haben Sie sich überlegt, dass es möglicherweise unendlich viele Zyklen?
InformationsquelleAutor Pavel Belov | 2010-02-15
Schreibe einen Kommentar