Hallo,
ich möchte für einen Baum, der aus einem regulären Graphen mit Grad 1 ausgeschnitten wurde, die Kanten
umdrehen. Vor dem Umdrehen verlaufen diese in Richtung Wurzel.
Ich habe die Kanten des kompletten Graphen in einem Array int graph[] gespeichert, wobei der Ausgang der Kante
dem Arrayindex entspricht und die erreichte Kante als Wert zu diesem Index gespeichert ist.
Um den Baum zu invertieren, führe ich einen DFS aus. Aber da jeweils der Vorgänger zu einem Knoten bestimmt
werden muss (das sind oft auch mehrere) und diese im Array erst gesucht werden müssen, dauert das Ganze
bei großen Bäumen sehr lange.
Kann man das irgendwie verbessern? Eine andere Datenstruktur vielleicht? Ich hatte es zuerst über
Adjazenzlisten versucht, aber das dauert noch länger.
Der Code sieht so aus:
Wäre total schön, wenn mir jemand weiterhelfen könnte.
Gruß,
Katja
ich möchte für einen Baum, der aus einem regulären Graphen mit Grad 1 ausgeschnitten wurde, die Kanten
umdrehen. Vor dem Umdrehen verlaufen diese in Richtung Wurzel.
Ich habe die Kanten des kompletten Graphen in einem Array int graph[] gespeichert, wobei der Ausgang der Kante
dem Arrayindex entspricht und die erreichte Kante als Wert zu diesem Index gespeichert ist.
Um den Baum zu invertieren, führe ich einen DFS aus. Aber da jeweils der Vorgänger zu einem Knoten bestimmt
werden muss (das sind oft auch mehrere) und diese im Array erst gesucht werden müssen, dauert das Ganze
bei großen Bäumen sehr lange.
Kann man das irgendwie verbessern? Eine andere Datenstruktur vielleicht? Ich hatte es zuerst über
Adjazenzlisten versucht, aber das dauert noch länger.
Der Code sieht so aus:
Code:
// findet den nächstfolgenden Knoten zu einem gegebenen Knoten k, in Richtung Wurzel
public int runThroughGraph (int k) {
int x =graph[k];
return x;
}
// findet die Vorgänger eines Knoten root, von der Wurzel weglaufend
public int findPredecessors (int root, int successor, int counter){
int predecessor;
int count = 0;
for(int i=0;i<numberOfNodes;i++){
if(graph[i]==successor){
predecessor=i;
count++;
if(count==counter){
return predecessor;
}
}
}
if(successor==root){
return -2;
}
else {
return -1;
}
}
//Umdrehen der Kanten des Baumes und schreiben in Adjazenzliste
public void reverseTree(int root){
Stack s = new Stack();
int r = root;
TreeStack t = new TreeStack();
int m;
int save;
int counter = 1;
int newNumber=1;
do {
m = findPredecessors(root,r,counter);
if(r==root){
if(isOnCircle(r,m)){
counter++;
m = findPredecessors(root,r,counter);
}
}
if(m!=-1 && m!=-2){
t.push(s,r,counter);
r = m;
counter = 1;
}
else{
if(m==-1){
save = r;
counter = (Integer)t.pop(s);
r = (Integer)t.pop(s);
setTreeEdge(r,save);
counter++;
}
}
}
while(!s.empty()|| m!=-2);
}
Wäre total schön, wenn mir jemand weiterhelfen könnte.
Gruß,
Katja