Βοηθεια!-ευρεση ολων των δυνατων μονοπατιων σε ενα γραφο

[Επισκέπτης]

καλημερα,αντιμετωπιζω ενα προβλημα και μου φαινεται δυσκολο...

πειτε οτι εχω το γραφο της σελιδας 2

http://www.uop.gr/~javalab/docs/projects-javalab-2005.pdf

 

αυτο που θελω να κανω εγω ειναι να τυπωσω ολα τα δυνατα μονοπατια...δηλαδη στη συγκεκριμενη περιπτωση πρεπει να εχω:

A,B,F,L

A,B,G,M

A,B,G,N,T

A,B,G,N,M

A,B,G,N,V

A,D,I

A,D,J

A,D,K

A,D,K,R,X

A,D,K,R,Y

A,D,K,R,Z

 

μπορει καποιος να με βοηθησει με καποιο αλγοριθμο;

εχετε γενικα να προτεινετε καποια λυση-μεθοδολογια-σκεψη-αλγοριθμο-κωδικα;

ευχαριστω.

[zinas]

Ο γραφός που υπάρχει στο σχήμα είναι δέντρο. Αν μιλάμε μόνο για δέντρο, αυτό σημαίνει ότι υπάρχει μοναδικό μονοπάτι που οδηγεί στο κάθε φύλο. Άρα ξεκινώντας από κάθε φύλο και παίρνοντας τη διαδρομή που αδηγεί στη ρίζα του δέντρου, έχεις όλα τα μονοπάτια.

[Επισκέπτης]

ευχαριστω γαι την απαντηση.

καταλαβαινεις ομως πως δε μπορω να αρχισω απο τα φυλλα και να παω στη ριζα...βλεπεις,οι δεικτες ειναι προς τα κατω και οχι προς τα πανω...δεν ειναι δηλαδη οπως ειναι και μια διπλα συνδεδεμενη λιστα που μπορεις να πας απο οποια κατευθυνση θες..σε δεντρικη δομη πρεπει να αρχισεις απο τη ριζα...εκτος βεβαια αν ξερεις κατι που εγω δε ξερω..οποτε..

[My8os]

Δεν είδα την εκφώνηση αλλά αν μιλάμε για δέντρο τότε για να το διασχίσεις θα πρέπει να χρησιμοποιήσεις έναν απο τους παρακάτω αναδρομικούς αλγόρυθμους:

 

Preorder, πρώτα τυπώνει τη ρίζα, μετά αριστερό παιδί και μετά δεξί:

>
void preorder(treenode t){
   if(t!=NULL){
       print(t);
       preorder(t->leftchild);
       preorder(t->rightchild);     
   }
}

 

Inorder, πρώτα τυπωνει αριστερό παιδί, μετά ρίζα και μετά δεξί παιδί:

>
void inorder(treenode t){
   if(t!=NULL){
       inorder(t->leftchild);
       print(t);
       inorder(t->rightchild);     
   }
}

 

Postorder, πρώτα τυπωνει αριστερό παιδί, μετά δεξί και τέλος τη ρίζα:

>
void postorder(treenode t){
   if(t!=NULL){
       postorder(t->leftchild);       
       postorder(t->rightchild);     
       print(t);
   }
}

 

Καλό είναι να googlάρεις τις παραπάνω ονομασίες για να τα βρείς με περισσότερες λεπτομέρειες .

[zinas]

Χμμμ... μάλλον έχεις δίκιο σ'αυτό που λες. Δεν σκέφτηκα καθόλου την υλοποίηση και απάντησα εντελώς θεωρητικά.

 

function printPath(node, path) {

 

1) Add node to path

2) if node has children then printPath(firstChild, path) else print path

3) if node has neighbour then printPath(nextNeighbour, path)

 

}

 

Αν υποθέσουμε ότι είναι εντελώς σειριακή η εκτέλεση του αλγορίθμου, τότε ο τρόπος που διασχίζουμε το δέντρο είναι depth-first. Επίσης, ανάλογα με την υλοποίηση πρόσεχε πώς θα διαχειριστείς το path (ένα array φαντάζομαι θα είναι).

 

Ότι γράφω παραπάνω είναι με κάθε επιφύλαξη... ούτε έχω δει τον αλγορίθμο πουθενά, ούτε τον έχω δοκιμάσει. Συγγνώμη αν έχω κάνει κάποιο λάθος και σε μπερδέψω.

[zinas]

@My8os:

Έχω την εντύπωση ότι αυτά που έγραψες δεν τυπώνουν μονοπάτια, απλά διασχίζουν όλο το δέντρο με κάποια σειρά.

[bird]

Μια χαρά το τυπώνει ο αλγόριθμος του My8os απλά δεν κάνει για το δέντρο του φίλου μας γιατί κάποια nodes έχουν περισσότερα από 2 κλαδιά...

[zinas]

Σωστός ο bird... για άλλη μια φορά είμουν απρόσεκτος

 

void preorder(treenode t){

if(t!=NULL){

print(t);

while (t->hasNextChild) {

preorder(t->nextChild); }

}

}

 

Με αυτή τη τροποίηση λογικά θα παίζει.

[bird]

Μπά, πάλι δεν θα δουλέψει :)

Ίσως αυτό κάνει δουλειά....

 

>void preorder(treenode t){

  int i;
   if(t!=NULL){

       print(t);

       for( i = 0; i < t->ChildNo; i++ ) {

           preorder(t->nextChild[i]); }

   }

}

όπου το nextChild είναι ένας πίνακας με τους pointers που "δείχνουν" στα παιδιά και ChildNo Ο αριθμός των παιδιών κάθε node...

[zinas]

Το ίδιο λέμε bird

 

Τη λογική έγραψα, δηλαδή ότι θα υπάρχει ένα loop σε όλα τα παιδιά του κόμβου. Στο συντακτικό δεν έδωσα σημασία (για να είμαι ειλικρινής ούτε καν ξέρω σε ποια γλώσσα θα το υλοποιήσει).

[Επισκέπτης]

kai pali eyxaristw gia to endiaferon...prosekste omws...

an anoiksete to link poy parathetw kai diabasete to eggrafo 9a deite pws ayta poy lete hdh yparxoyn..

dhladh h preorder() einai sthn ousia h anazhthsh kata ba9os,in-depth search

px. as poyme oti 9elw na brw to monopati apo th koryfh (A)ews to T

h preorder 9a moy dwsei

A,B,F,L,G,M,N,T

enw egw thelw

A,B,G,N,T

mallon ayto poy xreiazomai einai mia tropopohmenh in-depth search,tropopoihmenh oson afora th lista (oura) poy synodeyei thn in-depth.

[gtroza]

εχετε γενικα να προτεινετε καποια λυση-μεθοδολογια-σκεψη-αλγοριθμο-κωδικα;

 

pros natural_sgf (apo asxeto me thrasos!)

 

perioxh \EDGES

 

mexri na teleiosei h perioxh \EDGES

set path(i) =1o zeygos

sbysto apo seira

pare epomeno

sbysto apo seira

des kathe path an periexei to 1o tou zeygous(ektos apo thesh 0)

an vrethei kane neo path(i+1) me to aristero tmhma kai kolla to zeygos

psaxe gia zeygos me 1o to last tou path

an den breis ;print path ; xana sthn arxh ths perioxhs \EDGES (opos emeine meta tis diagrafes); i=i+1

an breis ; kolla 2o tou zeygous sto path(i)

sbysto apo seira

 

telos seiron ; ara neo path ;i= i+1 ;xana sthn arxh

 

kapos etsi me ligh kaliterh organosh

an sbyneis , dhmiourgeis nees diadromes kai xanapsaxneis mexri na teleiosei h perioxh \EDGES tha exeis sto telos tis diadromes pou xreiazesai.

 

 

kalh epityxia

[Inkjjl]

natural_sqf eisai defteroetis UOP????Imoun ekei OLO to proto etos!!!Me kseroun ta paidia tou tritou kai tou tetartou etous...Tora eimai di.uoa...Akyro to minima alla tha apantiso kai sto erotima sou...Einai poly arga tora...Avrio! ;-)

[Επισκέπτης]

@gtroza

endiaferousa skepsh file moy...9a th koitaksw..thnx

@Inkjjl

nai,deytero etos UoP..ama hsoyn edw olo to prwto etos kai parakoloy9hses kana ma8hma tote stantar 9a se kserw..toylaxiston fatsika..pws soy fainetai ekei?

pio dyskola ta ma9hmata h pio eykola?

[Hatman]

beadth first or depth first u dont mind

 

Vasika o kwdikas se prolog einai 4-5 grammes an thimamai kala.

kanto se prolog.