Εὔρεση ὅλων τῶν κύκλων - κατευθυνόμενο γράφημα

Ο τομέας μας. ;)
Απάντηση
Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 298
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

Εὔρεση ὅλων τῶν κύκλων - κατευθυνόμενο γράφημα

Δημοσίευση από Κηπουρίδης » Κυρ Απρ 03, 2011 11:43 pm

Ψάχνω ἐδὼ καὶ πολὺ καιρὸ ἀλγόριθμο ποὺ νὰ ἐντοπίζει ΟΛΟΥΣ τοὺς κύκλους σὲ κατευθυνόμενο γράφημα ( directed graph ). Ἡ Dfs βρίσκει ἂν ὑπάρχει κύκλος, δὲν βρίσκει ὅλους τοὺς κύκλους ὅμως.
Τὸ μόνο ποὺ σκέφτηκα εἶναι νὰ ἀφαιροῦμε μία ἀκμή ( edge ) κάθε φορὰ ( ἔστω (x,y) ) καὶ νὰ βλέπουμε μὲ DFS ἂν ὑπάρχει μονοπάτι ἀπὸ τὸ y στὸ x ( καὶ μάλιστα κάθε μονοπάτι ! ). Ἄρα πολυπλοκότητα τρέχα γύρευε. Καμμιὰ καλύτερη ἰδέα;
Εικόνα

Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 298
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

Re: Εὔρεση ὅλων τῶν κύκλων - κατευθυνόμενο γράφημα

Δημοσίευση από Κηπουρίδης » Τρί Απρ 05, 2011 11:05 am

Ἀπὸ ὅτι κατάλαβα μὲ πολὺ ψάξιμο, οἱ κύκλοι ποὺ μπορεῖ νὰ ἔχει ἕνα κατευθυνόμενο γράφημα εἶναι ἄπειροι, ὁπότε μόνο brute force λύσεις θὰ τὸ κατάφερναν.
Ἀρκετὰ βοηθητικό : Μὲ δύο dfs ἐντοπίζεις ὅλα τὰ strongly connected components, κὶ ἀφαιρεῖς τὶς edges ποὺ τὰ συνδέουν. Συνεχίζεις μὲ τὸν ἀλγόριθμο ποὺ περιέγραψα παραπάνω, καὶ ξανακοιτὰς γιὰ strongly connected components καὶ ξανά... μέχρι ποὺ δὲν σὲ ἔχουν μείνει edges.
Εικόνα

sotiris
Δημοσιεύσεις: 422
Εγγραφή: Τρί Φεβ 10, 2009 9:49 pm

Re: Εὔρεση ὅλων τῶν κύκλων - κατευθυνόμενο γράφημα

Δημοσίευση από sotiris » Τρί Απρ 05, 2011 4:45 pm

http://en.wikipedia.org/wiki/Strongly_c ... components

Και δες και τους αλγορίθμους : Tarjan's algorithm, Gabow's algorithm
Εικόνα

Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 298
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

Re: Εὔρεση ὅλων τῶν κύκλων - κατευθυνόμενο γράφημα

Δημοσίευση από Κηπουρίδης » Τρί Απρ 05, 2011 9:06 pm

Ἄλλο strongly connected components κὶ ἄλλο κύκλοι!
Ἐγὼ ἤθελα κάθε κύκλο ( γιὰ τὴν ἀκρίβεια κάθε ἀπλὸ κύκλο ἤθελα... ).
Εικόνα

Απάντηση