# Kanten eines Baumes umdrehen



## Katja (18. Okt 2007)

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:


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


----------



## Marco13 (18. Okt 2007)

Hm. Ist zwar jetzt etwas zu spät, um das im Detail nachzuvollziehen (was da dann mit -1, -2 und dem TreeStack abläuft....) aber wenn es richtig verstanden habe, ist das Problem im Moment folgendes:

Du hast einen Baum, der z.B. so aussieht

```
0
    / \
   /   \
  1     2
 / \   / \
3  4  /   \
      5    6
```

Und der ist als array gespeichert

array[0] = -1;
array[1] = 0;
array[2] = 0;
array[3] = 1;
array[4] = 1;
array[5] = 2;
array[6] = 2;

Wenn du jetzt die Nachfolger von Knoten X finden willst, musst du den ganzen Array durchlaufen, um rauszufinden, bei welchen ArrayINDIZES der WERT 'X' steht. Und das für jeden Knoten. Das hat dann Laufzeit O(n*n). 

Es wäre wohl effizienter, das ganze einmal am Anfang rumzudrehen, und dann nurnoch drauf zuzugreifen. Implementierungsmöglichkeiten gibt's da 1000e. Welche die beste (d.h. für deinen Fall geeinetste) ist, weiß ich jetzt nicht. Aber man könnte einfach durch den Array laufen, und jeweils den Nachfolger (d.h. den ArrayINDEX) in eine Liste schreiben, die man über den Index des Vorgängers (d.h. des ArrayWERTES) anspricht. Zum Beispiel (!) ungefähr so

```
List<Integer> nodes[] = new ArrayList<Integer>[array.length];
for (int i=0; i<array.length; i++) 
{
    if (nodes[array[i]] == null) nodes[array[i]] = new ArrayList<Integer>();
    nodes[array[i]].add(i);
}
```
Das Ergebnis wäre in diesem Fall ein array mit Listen

nodes[0] = { 1, 2 }
nodes[1] = { 3, 4 }
nodes[2] = { 5, 6 }
nodes[3] = null
nodes[4] = null
nodes[5] = null
nodes[6] = null

Das hat dann einmal Laufzeit O(n), und man kann sich alle Nachfolger mit Laufzeit O(1) holen. 

Wie genau du mit dieser Information dann das eigentliche Umdrehen implementierst, bleibt dir überlassen :wink:


----------



## Katja (19. Okt 2007)

Vielen Dank !!!!!  Das hat funktioniert.


----------

