Baum mit Adjazensmatrix

Status
Nicht offen für weitere Antworten.

JanDMC

Mitglied
Hey Leute,

wie baut man am besten einen Baum mit einer Adjazensmatrix auf? Ich habe sonst eine Verkettete Liste genommen wo in jedem Knoten die <referenzen gespeichert werden, was mit einer Matrix ja kein Sinn mehr machen würde, nur ich habe keine Idee wie man Abbilden kann z.B. bei einem Binärbaum, ob das eine "linke Referenz" ist oder eine "rechte" da man in der Matrix ja nur eine Kante setzen kann, jedoch ohne "links " und "rechts".

Ich hoffe ihr habt die Frage verstanden, sonst einfach nachfragen.

mfg


Jan
 

Marco13

Top Contributor
In einer Adjazenzmatrix steht afair nur, zwischen welchen Knoten Kanten existieren. Wenn also nicht mehrere Kanten zwischen zwei Knoten existieren müssen, ist das in Ordnung.


Code:
   X
  / \
 Y   Z
 
->
 XYZ
X011
Y100
Z100
 

JanDMC

Mitglied
Ahh coole Idee bin ich irgendwie nich drauf gekommen.
Die Frage die sich jetzt stellt, wie traversiert man dann mit einer Adjazenzmatrix ohne Knoten " 2 Mal zu besuchen". Ich hab das immer so gemacht indem ich rekursiv je nach Traversierungsart die linke und dann rechte Referenz durchgegangen bin,

mfg jan
 

Marco13

Top Contributor
Die Adjazenzmatrix ist nur eine Darstellung - eine Implementierungsart - eine Repräsentation im Speicher, sozusagen. Man könnte stattdessen auch eine Adjazenzliste, direkte Referenzen, ... oder 1000 andere Sachen verwenden. An den Algorithmen selbst ändert das nichts.


Der einzige Unterschied (und in diesem Sinne vielleicht ein "Fehler" in meiner Antwort) ist, dass ein Baum gerichtet ist. Das Beispiel, das ich gepostet hatte, wäre die Darstellung für einen ungerichteten Graphen

Code:
   X
  / \
 Y   Z

Ungerichtet: Eine 1 bedeutet: Es gibt eine Kante zwischen den Knoten

 XYZ
X011
Y100
Z100

Gerichtet: Eine 1 bedeutet: Es gibt eine Kante VON dem Knoten 
in der jeweilgen Zeile ZU dem Knoten in der jeweiligen Spalte 
(hier z.B. von X nach Y, aber nich von Y nach X)

 XYZ
X011
Y000
Z000

Z.B. ist Traversierung im Pseudocode ja sowas wie
Code:
void visit(Node node)
{
    List children = computeChildren(node);
    for (children c)
    {
        visit(c)
    }
}
und die Methode "computeChildren" würde bei direkten Referenzen eben sowas machen wie
Code:
List computeChildren(Node node)
{
    return node.children;
}
und bei einer Adjazenzmatrix sowas wie
Code:
List computeChildren(Node node)
{
    List result = new List();
    for (alle Spalten s in der Zeile z der Adjazenzmatrix, die zum Knoten 'node' gehört)
    {
        if (adjazenzmatrix[z][s] == 1)
        {
            result.add(knotenFürSpalte(s));
        }
    }
    return result;
}

Wenn's nicht hilft, poste ggf. mal deinen Traversierungscode UND wie du die Sachen vorher (ohne Adjazenzmatrix) gespeichert und verwendet hast.
 

JanDMC

Mitglied
Genau da ist mein Problem, ich habe gar keine Knoten ansich da ich durch ein true in der Matrix z.b an stelle (5,4) eine Referenz von Knoten 5 auf 4 habe. Nur wie ich die Knoten speicher ist halt so eine Sache. Deswegen kann ich sowas wie node.children ja nicht aufrufen da ich nirgends ein Objekt speicher welches auf andere Knoten referenziert, wenn das der Fall wäre, bräuchte man ja auch keine Adjazenzmatrix oder sehe ich das falsch?.

mfg

Jan

//Edit

Wenn ich das richtig verstaden habe, soll ich für jede Zeile nachgucken an welcher Stelle ich eine 1 stehen habe und dann einen Knoten anlegen mit einer referenz auf die Spalte wo die 1 Stand?
 

Marco13

Top Contributor
Jetzt ist NOCH unklarer, wie du das vorher gemacht hast: Einerseits redest du von Knoten und Referenzen auf Knoten, andererseits sagst du, dass du keine Knoten hast....?
 

JanDMC

Mitglied
Ich habe früher bereits einen BinärBaum implementiert OHNE Adjazenzmatrix. Da hatte ich Knoten und als Attribut linke und rechte referenz.

Jetzt soll ich aber einen Baum mit Hilfe einer Adjazenzmatrix aufbauen somit fallen die Knoten als Objekte zusammen mit den Referenzen weg oder nicht. Die Referenzen sind in der Matrix gespeichert und als Knoten dient eine Zeile der Matrix.
 

Marco13

Top Contributor
Ähhh ... ich glaube, ich sehe das Problem ... aber ... das klingt ein bißchen, als wolltest du deinen Algorithmus jetzt nicht mehr über einen (abstrakten) Baum laufen lassen, sondern über eine Adjazenzmatrix. Also so
Code:
void visit(int matrix[][], int nodeIndex)
{
    for (int i=0; i<matrix[nodeIndex].length)
    {
        if (matrix[nodeIndex][i] == 1)
        {
            visit(matrix, i);
        }
    }
}
das wäre aber ziemlich unflexibel und unschön.

Aber wenn es NUR darum geht: In einer Adjazenzmatrix kann man natürlich (eigentlich) nichtmehr zwischen "rechtem" und "linkem" Kind unterscheiden - außer, wenn man in die int-matrix eine "1" für "rechtes Kind" und eine "2" für "linkes Kind" schreibt ... oder so.
 

JanDMC

Mitglied
In einer Adjazenzmatrix kann man natürlich (eigentlich) nichtmehr zwischen "rechtem" und "linkem" Kind unterscheiden

Danke! Genau das denke ich mir auch. Deswegen die Frage wieso man eine Graphenhirachie mit einer Matrix aufbauen soll. Naja so sind die Vorgaben.
Danke für die Antworten.
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
E XML - Datei Darstellung in IntelliJ als Baum Allgemeine Java-Themen 2
Karl_Der_Nette_Anfänger Hat wer ne Lösung für verknüpfte Postleitzahlen? (Baum/Wurzel Struktur) Allgemeine Java-Themen 11
D 2,3-Baum rekursiv erstellen Allgemeine Java-Themen 20
D Datentypen 2-3 Baum erstellen mit geordnetem int-array Allgemeine Java-Themen 0
L Dependency Injection für Baum-Einträge Allgemeine Java-Themen 9
M Iterator für trinären Baum Allgemeine Java-Themen 0
N Rekursiv Höhe Baum Allgemeine Java-Themen 3
D Baum zeichnen hilfe Allgemeine Java-Themen 4
D if - else Baum vereinfachen Allgemeine Java-Themen 4
A AVL-Baum - Testen ob einer vorliegt Allgemeine Java-Themen 4
M Eclipse Stackoverflow beim Einlesen von großen Bilder in kd Baum Allgemeine Java-Themen 15
G Datentypen TreeMap nach Color sortiert (kd-Baum) Allgemeine Java-Themen 8
M Baum nach Stack plus Objektkonvertierung Allgemeine Java-Themen 5
S Baum mit vordefinierten Werten befüllen Allgemeine Java-Themen 2
D Datenstruktur für Hierarchie/Baum mit Tiefe 3 Allgemeine Java-Themen 8
D Rot-Schwart-Baum denkfehler im code? Allgemeine Java-Themen 6
M Baum Allgemeine Java-Themen 3
K Dependency Baum erstellen/analysieren Allgemeine Java-Themen 2
MQue Tidy HTML baum durchlaufen Allgemeine Java-Themen 5
C Breitendurchlauf Baum. Vorgehen unklar. Allgemeine Java-Themen 23
C Fehler im Quellcode. Suche in einem Baum Allgemeine Java-Themen 3
R Daten aus Baum entsprechend in jTree einfuegen Allgemeine Java-Themen 2
C Daten möglichst schnell einem Baum zuordnen Allgemeine Java-Themen 2
S Datenstruktur für einen Baum Allgemeine Java-Themen 5
N Baum aus Datei laden. Allgemeine Java-Themen 3

Ähnliche Java Themen

Neue Themen


Oben