Überprüfen, ob eine 2D Matrix ein Baum ist

[John Cena]

Hallo,

ich sitze schon seit Tagen an einer alten Klausuraufgabe. Gegeben ist:

public class Graph {
 boolean[][] matrix;
 boolean[] besucht;
 //...
 public boolean istBaum() {
  besucht = new boolean[matrix.length];
  return istBaum(0);
 }
 public boolean istBaum(int knoten) {}
}

Und man soll überprüfen, ob die gegebene Matrix zyklenfrei und zusammenhängend ist, also einem Baum entspricht. Ich hab eine Lösung gefunden und die auch getestet, nur ist sie zu lang und bei gerichteten Graphen mit mehr als einer einlaufenden Kante gibt er manchmal auch true zurück. Die Frage wäre, kann ich irgendwo etwas kürzen oder es besser machen? In der Klausur hätte ich gerade mal 10 Minuten zum bearbeiten der Aufgabe gehabt und da ist auch wenig Platz auf der Seite, das heißt, die Lösung ist anscheinend kurz und "einfach". Profs sind alle im Urlaub und keiner antwortet mir, darum dachte ich, ich versuche mein Glück hier, in der Hoffnung, dass jemand mir vielleicht weiterhelfen kann. Hier mein Code:

public boolean istBaum(int knoten) {
 besucht[knoten] = true;
 for (int i = 0; i < matrix.length; i++) {
  if (matrix[knoten][i] || matrix[i][knoten])
   if (!besucht[i]) {
    istBaum(i);
   }
 }
 for (int i = 0; i < matrix.length; i++) {
  if (!besucht[i])
   return false;
 }
 return istZyklenfrei();
}
public boolean istZyklenfrei() {
 int wert = 0;
 for (int i = 0; i < matrix.length; i++) {
  for (int j = 0; j < matrix[i].length; j++) {
   if (matrix[i][j])
    wert++;
  }
 }
 if (!istSymmetrisch()) {
  if (wert > matrix.length - 1)
   return false;
 } else {
  if (wert > 2 * matrix.length - 2)
   return false;
 }
 return true;
}
public boolean istSymmetrisch() {
 for (int i = 0; i < matrix.length; i++) {
  for (int j = 0; j < matrix[i].length; j++) {
   if (matrix[i][j] != matrix[j][i])
    return false;
  }
 }
 return true;
}

LG

 

[thecain]

Nur für gerichtete Graphen nehme ich an, wenn es sich um einen baum handelt? Dann toplogisch sortieren.

Also quasi immer den node entfernen, der keinen Incoming Edge hat. Ist das nicht möglich, hat er einen cycle. Müsste O(|E| + |V|) sein

 

[mrBrown]

Für zyklenfrei musst du nur eine etwas modifizierte Tiefensuche machen. Anstatt nur Besucht/nicht besucht speicherst du zusätzlich, ob schon alle Nachfolgerknoten abgearbeitet wurde.
Sobald du dann einen Knoten findest, der zwar begonnen, aber noch nicht fertig abgearbeitet ist, ist ein Zyklus gefunden.

 

[John Cena]

Hey,

Danke für eure Antworten. Da in der Aufgabenstellung auch nichts weiter steht, soll man das anscheinend für gerichtete sowie ungerichtete Graphen gleichzeitig überprüfen, was das größte Problem für mich darstellte. Topologisches Sortieren, darauf bin ich auch gekommen, einer meiner Versuche war, zuerst die einlaufenden Kanten der Knoten zu zählen, einen zu suchen der 0 einlaufende kanten hat und so weiter, nur irgendwie, bei meiner Implementierung, hatte ich Endlosschleifen drin, darum habe ich die Idee verworfen.

Die Tiefensuche zu modifizieren ist eine gute Idee, hab ich auch schon 100 mal versucht durch probieren, denken und Internet Recherchen, nur mit meinen Anfänger skills hab ich auch das nicht hingekriegt, obwohl es bestimmt einfach ist. Vielleicht denke ich auch zu kompliziert. LG

 

[mrBrown]

Als Pseudocode:

istZyklus(v)
    wenn v begonnen
        Zyklus gefunden
    wenn v nicht besucht
       v als begonnen makieren
       für alle Nachfolger w von v
            istZyklus(w)
       v als besucht markieren

 

[John Cena]

Hey mrBrown,

vielen Dank für dein Pseudocode, ich setze mich mal später nochmal dran und versuche meinen Code zu bearbeiten. Danke nochmal.
LG