ακυκλο γράφημα στη C

[voulaji]

θέλω ένα αλγόριθμο που θα δέχεται σαν είσοδο ένα γράφημα και θα επιστρέφει false, όταν δεν υπάρχει κανένας κύκλος, και true εάν υπάρχει. Κατόπιν πρέπει να κατασκευαστεί πρόγραμμα στη C, που θα ελέγχει έαν το γράφημα έχει κύκλους ή όχι. Αν το γράφημα περιλαμβάνει κύκλο, τότε να τον τυπώνει. Το πρόγραμμα θα διαβάζει το γράφημα από το αρχείο, που θα έχει την εξής μορφή:

n, m

u, v float string

(σσ όπου n και m, ακέραιοι που δηλώνουν τον αριθμό κορυφών και ακμών του γραφήματος, τα u και v είναι οι κορυφές στα δυο άκρα μιας ακμής).

Προσοχή μόνο στο ότι, εάν ένα γράφημα είναι μη κατευθυνόμενο, δεν είναι ανάγκη να παρουσιάσουμε την ακμή (u,v) δυο φορές.

[warchief]

Με την καλή έννοια αλλά δεν νομίζω πως ο σκοπός αυτού του φόρουμ είναι να λύνει εργασίες. Κάτσε και ασχολήσου με την εργασία σου και αν έχεις κάποιο συγκεκριμένο πρόβλημα στα διαδικαστικά πόσταρε. Αυτό βέβαια δεν απαγορεύει από κάποιον/α να ασχοληθεί με την εργασία σου και να στην δώσει σερβιρισμένη στο πιάτο, αλλά γιατί να το κάνει?

[bokarinho]

Γιατί έχει γίνει άπειρες φορές, γιατί να μην γίνει και τώρα. Εκεί στηρίζεται το γεγονός και το insomnia έχει γίνει πολύ δημοφιλές για αυτό.

[narbi]

Αρα, bokarinho φαντάζομαι ότι το πτυχίο θα το δώσουν στο insomnia...

Άλλο να κολλάς σε ένα σημείο της επίλυσης και άλλο να ζητάς όλη την άσκηση..

[bokarinho]

Αρα, bokarinho φαντάζομαι ότι το πτυχίο θα το δώσουν στο insomnia...

Άλλο να κολλάς σε ένα σημείο της επίλυσης και άλλο να ζητάς όλη την άσκηση..

 

Ακριβώς, το πτυχίο θα πάει στο Insomnia, σαν το Oscar ακούγεται.

[voulaji]

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

Εν τέλει, κύριε narbi, ασχολήσου με κάτι πιο αποδοτικό από τις ειρωνίες σου.

[georgemarios]

http://en.wikipedia.org/wiki/Cycle_detection

[voulaji]

Το διάβασα αυτό που μου έστειλες και ήταν πολύ ενδιαφέρον και κατανοητό. Επειδή όμως, έχει περισσότερο γενικά πράγματα, δεν βοηθήθηκα όσο θα'θελα.

Τουλάχιστον μπορείς να μου περιγράψεις λίγο την λογική της άσκησής μου για να ξεκινήσω να κάνω κάτι;

[cfilip]

θέλω ένα αλγόριθμο που θα δέχεται σαν είσοδο ένα γράφημα και θα επιστρέφει false, όταν δεν υπάρχει κανένας κύκλος, και true εάν υπάρχει. Κατόπιν πρέπει να κατασκευαστεί πρόγραμμα στη C, που θα ελέγχει έαν το γράφημα έχει κύκλους ή όχι. Αν το γράφημα περιλαμβάνει κύκλο, τότε να τον τυπώνει. Το πρόγραμμα θα διαβάζει το γράφημα από το αρχείο, που θα έχει την εξής μορφή:

n, m

u, v float string

(σσ όπου n και m, ακέραιοι που δηλώνουν τον αριθμό κορυφών και ακμών του γραφήματος, τα u και v είναι οι κορυφές στα δυο άκρα μιας ακμής).

Προσοχή μόνο στο ότι, εάν ένα γράφημα είναι μη κατευθυνόμενο, δεν είναι ανάγκη να παρουσιάσουμε την ακμή (u,v) δυο φορές.

 

κλασικό θέμα διακριτών μαθηματικών!

 

εδώ χρειάζονται πράγματα που πρέπει να κάνεις, για να προχωρήσεις στην άσκηση

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

β) κάνε εξάσκηση του παραπάνω τρόπου με το χέρι με διάφορους γράφους μέχρι να καταλάβεις καλά τον τρόπο και κράτα πρόχειρες σημειώσεις για το κάθε βήμα που κάνεις

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

 

 

hint :

1) για το α) μπορείς να κάνεις πρώτα ένα Depth-First Search (αν δεν ξέρεις τι είναι, πρέπει να διαβάσεις λίγο διακριτά μαθηματικά πριν ασχοληθείς με την άσκηση) και αν βρεις ένα κόμβο που ήδη έχεις επισκεφτεί έχεις κύκλο. μπορείς να δεις και εδώ :

 

http://pages.cs.wisc.edu/~deppeler/cs367/f04/lectures/Lecture28.ppt

 

2) για το γ) υπάρχουν αρκετά βιβλία με αλγόριθμους πάνω σε γράφους που εξηγούν την λογική και θα σε βοηθήσουν πολύ, μια βόλτα στο παπασωτηρίου ή σε σχετικό κατάστημα θα σε βοηθήσεις πολύ. (ίσως να υπάρχει και στην βιβλιοθήκη κάτι σχετικά αν δεν θεσ να αγοράσεις κάτι). προσωπικά προτείνω το εξής :

 

http://www.informit.com/store/product.aspx?isbn=0201316633

[georgemarios]

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

 

γραφημα ξερεις τι ειναι φανταζομαι

κατευθυνομενο γραφημμα?

διαδρομη σε ενα γραφημα?

κυκλος σε ενα γραφημα?

 

Το πρόγραμμα θα διαβάζει το γράφημα από το αρχείο, που θα έχει την εξής μορφή:

n, m

u, v float string

μπορεις με αυτο το τροπο να περιγραψεις ενα γραφημα? Καταλαβαινεις τι γίνεται?

 

όπως λεει και ο cfilip, εξασκησου στο χαρτι πρωτα, οργανωσε το και θα δεις πως το προγραμμα θα δημιουργηθει σιγα-σιγα μονο του (οκ, σχεδον.... )

[voulaji]

Παιδιά σας ευχαριστώ πολύ. Θα διαβάσω σύμφωνα με τις υποδείξεις σας. Θα τα ξαναπούμε σύντομα.

[voulaji]

Έχω κατανοήσει το θεωρητικό υποβαθρο και είμαι στο στάδιο να γράψω τον κώδικά μου.

Στην αρχή γράφω το πως διαβάζω το αρχείο, γνωστό και σχετικά εύκολο. Βέβαια δυσκολέυομαι στο εξής: το αρχείο, πρέπει να έχει την εξής μορφή:

n, m

u, v float string

(σσ όπου n και m, ακέραιοι που δηλώνουν τον αριθμό κορυφών και ακμών του γραφήματος, τα u και v είναι οι κορυφές στα δυο άκρα μιας ακμής)

Πως δήλώνω αυτή τη παράμετρο;

Έχω κολήσει όμως και στο εξής: Με ποια δομή θα αναπαραστείσω το γράφο και τις ακμές του, αλλά και με ποια δομή θα σώζω τα προσωρινά αποτελέσματα.

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

Παιδιά βοηθήστε με, μόνη μου δεν μπορώ να βγάλω άκρη!

[bokarinho]

Η C++ STL σου προσφέρει το map container, εφόσον λοιπόν έχουμε κορυφές και ακμές τότε πολύ απλά μία κορυφή θα έχει ένα όνομα και μία ακμή θα έχει μία τιμή. Δηλαδή εσύ αυτό που θέλεις να κάνεις είναι κάτι σαν:

weight = 10

"firstVertex"-------------------------> "secondVertex"

 

Διαβασε το πως δουλεύει το map και θα τα καταφέρεις.

[voulaji]

Που θα βρω το map container?

Αυτή η έκδοση της C, έχει πολλές διαφορές?

[georgemarios]

STL map example