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

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

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

Δημοσίευση από Κηπουρίδης »

Ψάχνω ἐδὼ καὶ πολὺ καιρὸ ἀλγόριθμο ποὺ νὰ ἐντοπίζει ΟΛΟΥΣ τοὺς κύκλους σὲ κατευθυνόμενο γράφημα ( directed graph ). Ἡ Dfs βρίσκει ἂν ὑπάρχει κύκλος, δὲν βρίσκει ὅλους τοὺς κύκλους ὅμως.
Τὸ μόνο ποὺ σκέφτηκα εἶναι νὰ ἀφαιροῦμε μία ἀκμή ( edge ) κάθε φορὰ ( ἔστω (x,y) ) καὶ νὰ βλέπουμε μὲ DFS ἂν ὑπάρχει μονοπάτι ἀπὸ τὸ y στὸ x ( καὶ μάλιστα κάθε μονοπάτι ! ). Ἄρα πολυπλοκότητα τρέχα γύρευε. Καμμιὰ καλύτερη ἰδέα;
Λύσεις θεμάτων ΠΔΠ: https://pdp-archive.github.io/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/

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

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

Δημοσίευση από Κηπουρίδης »

Ἀπὸ ὅτι κατάλαβα μὲ πολὺ ψάξιμο, οἱ κύκλοι ποὺ μπορεῖ νὰ ἔχει ἕνα κατευθυνόμενο γράφημα εἶναι ἄπειροι, ὁπότε μόνο brute force λύσεις θὰ τὸ κατάφερναν.
Ἀρκετὰ βοηθητικό : Μὲ δύο dfs ἐντοπίζεις ὅλα τὰ strongly connected components, κὶ ἀφαιρεῖς τὶς edges ποὺ τὰ συνδέουν. Συνεχίζεις μὲ τὸν ἀλγόριθμο ποὺ περιέγραψα παραπάνω, καὶ ξανακοιτὰς γιὰ strongly connected components καὶ ξανά... μέχρι ποὺ δὲν σὲ ἔχουν μείνει edges.
Λύσεις θεμάτων ΠΔΠ: https://pdp-archive.github.io/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/

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

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

Δημοσίευση από sotiris »

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

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

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

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

Δημοσίευση από Κηπουρίδης »

Ἄλλο strongly connected components κὶ ἄλλο κύκλοι!
Ἐγὼ ἤθελα κάθε κύκλο ( γιὰ τὴν ἀκρίβεια κάθε ἀπλὸ κύκλο ἤθελα... ).
Λύσεις θεμάτων ΠΔΠ: https://pdp-archive.github.io/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/

Απάντηση