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?
Du musst angemeldet sein, um einen Kommentar abzugeben.
Dieses problem hat exponentielle Komplexität im Allgemeinen Fall. Die Sache ist die, dass, wenn jeder Knoten mit jedem zusammenhängt dann ist die Anzahl aller Graphen Zyklen ist mehr als
2^n
(jede Teilmenge von Knoten bildet mehrere Zyklen).Somit gibt es keinen guten Algorithmus im Allgemeinen Fall.
Zu finden in einem Kreislauf, die Sie verwenden können Breite-zuerst-Suche. Finden Sie alle Zyklen aus, die Sie verwenden sollten brute-force-Algorithmus.
Wenn C++ ist das problem dann eine andere Sprache. meine Kenntnisse in C++ keine Besondere Merkmal, dass es effizienter/komfortabler arbeiten auf die Grafik ankommt. Alternativ vielleicht möchten Sie sich für einen Rahmen, der die Abstraktion der low-level, so dass Sie konzentriert sich auf den high-level-Frage. Sie überlegen, Boost Graph library für diesen Zweck.