Ψάχνω ἐδὼ καὶ πολὺ καιρὸ ἀλγόριθμο ποὺ νὰ ἐντοπίζει ΟΛΟΥΣ τοὺς κύκλους σὲ κατευθυνόμενο γράφημα ( directed graph ). Ἡ Dfs βρίσκει ἂν ὑπάρχει κύκλος, δὲν βρίσκει ὅλους τοὺς κύκλους ὅμως.
Τὸ μόνο ποὺ σκέφτηκα εἶναι νὰ ἀφαιροῦμε μία ἀκμή ( edge ) κάθε φορὰ ( ἔστω (x,y) ) καὶ νὰ βλέπουμε μὲ DFS ἂν ὑπάρχει μονοπάτι ἀπὸ τὸ y στὸ x ( καὶ μάλιστα κάθε μονοπάτι ! ). Ἄρα πολυπλοκότητα τρέχα γύρευε. Καμμιὰ καλύτερη ἰδέα;
Εὔρεση ὅλων τῶν κύκλων - κατευθυνόμενο γράφημα
- Κηπουρίδης
- Δημοσιεύσεις: 397
- Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm
Εὔρεση ὅλων τῶν κύκλων - κατευθυνόμενο γράφημα
Λύσεις θεμάτων ΠΔΠ: 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/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/
- Κηπουρίδης
- Δημοσιεύσεις: 397
- Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm
Re: Εὔρεση ὅλων τῶν κύκλων - κατευθυνόμενο γράφημα
Ἀπὸ ὅτι κατάλαβα μὲ πολὺ ψάξιμο, οἱ κύκλοι ποὺ μπορεῖ νὰ ἔχει ἕνα κατευθυνόμενο γράφημα εἶναι ἄπειροι, ὁπότε μόνο brute force λύσεις θὰ τὸ κατάφερναν.
Ἀρκετὰ βοηθητικό : Μὲ δύο dfs ἐντοπίζεις ὅλα τὰ strongly connected components, κὶ ἀφαιρεῖς τὶς edges ποὺ τὰ συνδέουν. Συνεχίζεις μὲ τὸν ἀλγόριθμο ποὺ περιέγραψα παραπάνω, καὶ ξανακοιτὰς γιὰ strongly connected components καὶ ξανά... μέχρι ποὺ δὲν σὲ ἔχουν μείνει edges.
Ἀρκετὰ βοηθητικό : Μὲ δύο 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/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/
Re: Εὔρεση ὅλων τῶν κύκλων - κατευθυνόμενο γράφημα
http://en.wikipedia.org/wiki/Strongly_c ... components
Και δες και τους αλγορίθμους : Tarjan's algorithm, Gabow's algorithm
Και δες και τους αλγορίθμους : Tarjan's algorithm, Gabow's algorithm
- Κηπουρίδης
- Δημοσιεύσεις: 397
- Εγγραφή: Παρ Φεβ 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/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/