Μενού

Βάθος Πρώτη αναζήτηση (DFS) Πρόγραμμα C ++ για να διασχίσετε ένα γράφημα ή ένα δέντρο

  • Κύριος
  • Αλλα
  • Βάθος Πρώτη αναζήτηση (DFS) Πρόγραμμα C ++ για να διασχίσετε ένα γράφημα ή ένα δέντρο

depth first search c program traverse graph

Δοκιμάστε Το Όργανο Μας Για Την Εξάλειψη Των Προβλημάτων

Αυτό το σεμινάριο καλύπτει την πρώτη αναζήτηση βάθους (DFS) σε C ++ στην οποία ένα γράφημα ή δέντρο διασχίζεται κατά βάθος. Θα μάθετε επίσης τον αλγόριθμο και την εφαρμογή DFS:

Βάθος-πρώτη αναζήτηση (DFS) είναι μια ακόμη τεχνική που χρησιμοποιείται για να διασχίσει ένα δέντρο ή ένα γράφημα.

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

Μόλις επιτευχθεί ο κόμβος των φύλλων, το DFS υποχωρεί και αρχίζει να εξερευνά μερικούς κόμβους με παρόμοιο τρόπο.

=> Δείτε τον οδηγό εκπαίδευσης για αρχάριους C ++ εδώ.

Βάθος-πρώτη αναζήτηση

Τι θα μάθετε:

Πρώτη αναζήτηση βάθους (DFS) σε C ++

Σε αντίθεση με το BFS στο οποίο εξερευνούμε τους κόμβους κατά μήκος, στο DFS διερευνούμε τους κόμβους σε βάθος. Στο DFS χρησιμοποιούμε μια δομή δεδομένων στοίβας για την αποθήκευση των κόμβων που διερευνάται. Οι άκρες που μας οδηγούν σε ανεξερεύνητους κόμβους ονομάζονται «άκρες ανακάλυψης» ενώ οι άκρες που οδηγούν σε κόμβους που έχουν ήδη επισκεφτεί ονομάζονται «άκρες μπλοκ».

Στη συνέχεια, θα δούμε τον αλγόριθμο και τον ψευδοκώδικα για την τεχνική DFS.

Αλγόριθμος DFS

  • Βήμα 1: Εισαγάγετε τον ριζικό κόμβο ή τον αρχικό κόμβο ενός δέντρου ή ενός γραφήματος στη στοίβα.
  • Βήμα 2: Βάλτε το κορυφαίο στοιχείο από τη στοίβα και προσθέστε το στη λίστα επισκέψεων.
  • Βήμα 3: Βρείτε όλους τους παρακείμενους κόμβους του κόμβου που έχουν επισημανθεί ως επισκέφθηκε και προσθέστε αυτούς που δεν έχουν ακόμη επισκεφτεί, στη στοίβα.
  • Βήμα 4 : Επαναλάβετε τα βήματα 2 και 3 έως ότου η στοίβα είναι άδεια.

Ψευδοκώδικας

Ο ψευδοκωδικός για το DFS δίνεται παρακάτω.

Ο ψευδοκωδικός για DFS

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

Διασχίσεις με εικονογραφήσεις

Ας απεικονίσουμε τώρα τη διασταύρωση DFS ενός γραφήματος. Για λόγους σαφήνειας, θα χρησιμοποιήσουμε το ίδιο γράφημα που χρησιμοποιήσαμε στην εικόνα BFS.

DFS Εικονογραφήσεις με διαβάσεις

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

Σπρώξτε όλους τους γειτονικούς κόμβους στη στοίβα

Στη συνέχεια, παίρνουμε έναν από τους παρακείμενους κόμβους για να επεξεργαστούμε, δηλαδή το πάνω μέρος της στοίβας που είναι 1. Το επισημαίνουμε ως επισκέψιμο προσθέτοντάς το στη λίστα επισκέψεων. Τώρα αναζητήστε τους γειτονικούς κόμβους του 1. Καθώς το 0 βρίσκεται ήδη στη λίστα επισκέψεων, το αγνοούμε και επισκέπτουμε το 2 που είναι η κορυφή της στοίβας.

Εικόνα DFS - Βήμα 3

Στη συνέχεια, επισημαίνουμε τον κόμβο 2 ως επισκέφθηκε. Ο γειτονικός κόμβος 4 προστίθεται στη στοίβα.

Εικονογράφηση DFS Βήμα 4

Στη συνέχεια, σημειώνουμε 4 που είναι η κορυφή της στοίβας κατά την επίσκεψη. Ο κόμβος 4 έχει μόνο τον κόμβο 2 ως παρακείμενο που έχει ήδη επισκεφθεί, επομένως τον αγνοούμε.

Εικονογράφηση DFS Βήμα 5

Σε αυτό το στάδιο, μόνο ο κόμβος 3 υπάρχει στη στοίβα. Ο γειτονικός κόμβος 0 έχει ήδη επισκεφθεί, επομένως τον αγνοούμε. Τώρα σημειώνουμε το 3 ως επισκέφθηκε.

Εικονογράφηση DFS Βήμα 6

Τώρα η στοίβα είναι κενή και η λίστα επισκέψεων δείχνει την ακολουθία της πρώτης βάσης του δεδομένου γραφήματος.

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

Εφαρμογή βάθους-πρώτης αναζήτησης

Ας εφαρμόσουμε την τεχνική διέλευσης DFS χρησιμοποιώντας το C ++.

#include #include using namespace std; //graph class for DFS travesal class DFSGraph { int V; // No. of vertices list *adjList; // adjacency list void DFS_util(int v, bool visited()); // A function used by DFS public: // class Constructor DFSGraph(int V) { this->V = V; adjList = new list(V); } // function to add an edge to graph void addEdge(int v, int w){ adjList(v).push_back(w); // Add w to v’s list. } void DFS(); // DFS traversal function }; void DFSGraph::DFS_util(int v, bool visited()) { // current node v is visited visited(v) = true; cout << v << ' '; // recursively process all the adjacent vertices of the node list::iterator i; for(i = adjList(v).begin(); i != adjList(v).end(); ++i) if(!visited(*i)) DFS_util(*i, visited); } // DFS traversal void DFSGraph::DFS() { // initially none of the vertices are visited bool *visited = new bool(V); for (int i = 0; i < V; i++) visited(i) = false; // explore the vertices one by one by recursively calling DFS_util for (int i = 0; i < V; i++) if (visited(i) == false) DFS_util(i, visited); } int main() { // Create a graph DFSGraph gdfs(5); gdfs.addEdge(0, 1); gdfs.addEdge(0, 2); gdfs.addEdge(0, 3); gdfs.addEdge(1, 2); gdfs.addEdge(2, 4); gdfs.addEdge(3, 3); gdfs.addEdge(4, 4); cout << 'Depth-first traversal for the given graph:'<

Παραγωγή:

Διαδρομή πρώτου βάθους για το δεδομένο γράφημα:

0 1 2 4 3

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

Ανάλυση χρόνου εκτέλεσης

Η χρονική πολυπλοκότητα του DFS είναι η ίδια με το BFS, δηλ. O (| V | + | E |) όπου V είναι ο αριθμός κορυφών και E είναι ο αριθμός ακμών σε ένα δεδομένο γράφημα.

Παρόμοια με το BFS, ανάλογα με το αν το γράφημα είναι σπάνια ή πυκνοκατοικημένο, ο κυρίαρχος παράγοντας θα είναι κορυφές ή ακμές αντίστοιχα στον υπολογισμό της πολυπλοκότητας του χρόνου.

Επαναληπτικό DFS

Η εφαρμογή που φαίνεται παραπάνω για την τεχνική DFS είναι αναδρομικής φύσης και χρησιμοποιεί μια στοίβα κλήσεων λειτουργίας. Έχουμε μια άλλη παραλλαγή για την εφαρμογή του DFS, δηλαδή ' Επαναληπτική αναζήτηση βάθους-πρώτης '. Σε αυτό, χρησιμοποιούμε τη ρητή στοίβα για να κρατήσουμε τις κορυφές που επισκέπτεστε.

Έχουμε δείξει την εφαρμογή για επαναληπτικό DFS παρακάτω. Σημειώστε ότι η εφαρμογή είναι ίδια με το BFS εκτός από τον παράγοντα που χρησιμοποιούμε τη δομή δεδομένων στοίβας αντί για μια ουρά.

#include using namespace std; // graph class class Graph { int V; // No. of vertices list *adjList; // adjacency lists public: Graph(int V) //graph Constructor { this->V = V; adjList = new list(V); } void addEdge(int v, int w) // add an edge to graph { adjList(v).push_back(w); // Add w to v’s list. } void DFS(); // DFS traversal // utility function called by DFS void DFSUtil(int s, vector &visited); }; //traverses all not visited vertices reachable from start node s void Graph::DFSUtil(int s, vector &visited) { // stack for DFS stack dfsstack; // current source node inside stack dfsstack.push(s); while (!dfsstack.empty()) { // Pop a vertex s = dfsstack.top(); dfsstack.pop(); // display the item or node only if its not visited if (!visited(s)) { cout << s << ' '; visited(s) = true; } // explore all adjacent vertices of popped vertex. //Push the vertex to the stack if still not visited for (auto i = adjList(s).begin(); i != adjList(s).end(); ++i) if (!visited(*i)) dfsstack.push(*i); } } // DFS void Graph::DFS() { // initially all vertices are not visited vector visited(V, false); for (int i = 0; i < V; i++) if (!visited(i)) DFSUtil(i, visited); } //main program int main() { Graph gidfs(5); //create graph gidfs.addEdge(0, 1); gidfs.addEdge(0, 2); gidfs.addEdge(0, 3); gidfs.addEdge(1, 2); gidfs.addEdge(2, 4); gidfs.addEdge(3, 3); gidfs.addEdge(4, 4); cout << 'Output of Iterative Depth-first traversal: '; gidfs.DFS(); return 0; }

Παραγωγή:

Έξοδος του Iterative Depth-first traversal:

0 3 2 4 1

Χρησιμοποιούμε το ίδιο γράφημα που χρησιμοποιήσαμε στην αναδρομική εφαρμογή μας. Η διαφορά στην έξοδο είναι επειδή χρησιμοποιούμε τη στοίβα στην επαναληπτική υλοποίηση. Καθώς οι στοίβες ακολουθούν την παραγγελία LIFO, λαμβάνουμε μια διαφορετική ακολουθία DFS. Για να λάβουμε την ίδια ακολουθία, ίσως θέλουμε να εισαγάγουμε τις κορυφές με την αντίστροφη σειρά.

BFS εναντίον DFS

Μέχρι στιγμής έχουμε συζητήσει και τις δύο τεχνικές διασταύρωσης για γραφήματα, δηλαδή BFS και DFS.

Τώρα ας εξετάσουμε τις διαφορές μεταξύ των δύο.

BFSDFS
Περιέχει «Πρώτο εύρος αναζήτησης»Αντικείμενο για 'Βάθος-πρώτη αναζήτηση'
Οι κόμβοι διερευνώνται από επίπεδο σε επίπεδο.Οι κόμβοι διερευνώνται σε βάθος έως ότου υπάρχουν μόνο κόμβοι φύλλων και στη συνέχεια ακολουθούνται για να εξερευνήσουν άλλους μη επισκέψιμους κόμβους.
Το BFS εκτελείται με τη βοήθεια της δομής δεδομένων ουράς.Το DFS εκτελείται με τη βοήθεια της δομής δεδομένων στοίβας.
Χαμηλότερη απόδοση.Ταχύτερο από το BFS.
Χρήσιμο στην εύρεση της συντομότερης διαδρομής μεταξύ δύο κόμβων.Χρησιμοποιείται κυρίως για την ανίχνευση κύκλων σε γραφήματα.

Εφαρμογές του DFS

  • Ανίχνευση κύκλων στο γράφημα: Εάν βρούμε ένα πίσω άκρο κατά την εκτέλεση του DFS σε ένα γράφημα, μπορούμε να συμπεράνουμε ότι το γράφημα έχει έναν κύκλο. Ως εκ τούτου, το DFS χρησιμοποιείται για την ανίχνευση των κύκλων σε ένα γράφημα.
  • Pathfinding: Λαμβάνοντας υπόψη δύο κορυφές x και y, μπορούμε να βρούμε τη διαδρομή μεταξύ x και y χρησιμοποιώντας DFS. Ξεκινάμε με την κορυφή x και μετά πιέζουμε όλες τις κορυφές στο δρόμο προς τη στοίβα μέχρι να συναντήσουμε y. Τα περιεχόμενα της στοίβας δίνουν τη διαδρομή μεταξύ x και y.
  • Ελάχιστο δέντρο έκτασης και συντομότερη διαδρομή: Η διασταύρωση DFS του μη σταθμισμένου γραφήματος μας δίνει ένα ελάχιστο δέντρο έκτασης και τη συντομότερη διαδρομή μεταξύ των κόμβων.
  • Τοπολογική ταξινόμηση: Χρησιμοποιούμε τοπολογική ταξινόμηση όταν πρέπει να προγραμματίσουμε τις εργασίες από τις δεδομένες εξαρτήσεις μεταξύ των θέσεων εργασίας. Στο πεδίο της επιστήμης των υπολογιστών, το χρησιμοποιούμε κυρίως για την επίλυση εξαρτήσεων συμβόλων σε συνδέσμους, σειριοποίηση δεδομένων, προγραμματισμό εντολών κ.λπ. Το DFS χρησιμοποιείται ευρέως στην τοπολογική ταξινόμηση.

συμπέρασμα

Στα τελευταία δύο σεμινάρια, διερευνήσαμε περισσότερα σχετικά με τις δύο τεχνικές διέλευσης για γραφήματα, δηλαδή BFS και DFS. Έχουμε δει τις διαφορές καθώς και τις εφαρμογές και των δύο τεχνικών. Τα BFS και DFS επιτυγχάνουν βασικά το ίδιο αποτέλεσμα της επίσκεψης σε όλους τους κόμβους ενός γραφήματος, αλλά διαφέρουν στη σειρά της εξόδου και στον τρόπο με τον οποίο γίνεται.

Έχουμε επίσης δει την εφαρμογή και των δύο τεχνικών. Ενώ το BFS χρησιμοποιεί μια ουρά, το DFS χρησιμοποιεί στοίβες για να εφαρμόσει την τεχνική. Με αυτό, ολοκληρώνουμε το σεμινάριο για τις τεχνικές διέλευσης για γραφήματα. Μπορούμε επίσης να χρησιμοποιήσουμε BFS και DFS σε δέντρα.

λογισμικό για κατασκοπεία κινητών τηλεφώνων

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

=> Δείτε εδώ για να εξερευνήσετε τη λίστα με τα πλήρη σεμινάρια C ++.

Συνιστώμενη ανάγνωση

^