# Baum mit Adjazensmatrix



## JanDMC (16. Jan 2009)

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 (16. Jan 2009)

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.



```
X
  / \
 Y   Z
 
->
 XYZ
X011
Y100
Z100
```


----------



## JanDMC (16. Jan 2009)

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 (17. Jan 2009)

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


```
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

```
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

```
List computeChildren(Node node)
{
    return node.children;
}
```
und bei einer Adjazenzmatrix sowas wie

```
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 (18. Jan 2009)

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 (18. Jan 2009)

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 (18. Jan 2009)

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 (18. Jan 2009)

Ä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

```
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 (18. Jan 2009)

> 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.


----------

