Σελίδα 1 από 1

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

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

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

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

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

Δημοσιεύτηκε: Τρί Απρ 05, 2011 4:45 pm
από pman
http://en.wikipedia.org/wiki/Strongly_c ... components

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

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

Δημοσιεύτηκε: Τρί Απρ 05, 2011 9:06 pm
από Κηπουρίδης
Ἄλλο strongly connected components κὶ ἄλλο κύκλοι!
Ἐγὼ ἤθελα κάθε κύκλο ( γιὰ τὴν ἀκρίβεια κάθε ἀπλὸ κύκλο ἤθελα... ).