Μενού

Breadth First Search (BFS) Πρόγραμμα C ++ για να διασχίσετε ένα γράφημα ή ένα δέντρο

  • Κύριος
  • Αλλα
  • Breadth First Search (BFS) Πρόγραμμα C ++ για να διασχίσετε ένα γράφημα ή ένα δέντρο

breadth first search c program traverse graph

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

Αυτό το σεμινάριο καλύπτει την Πρώτη Αναζήτηση στο Πλάτος σε C ++ στο οποίο Το Γράφημα ή το Δέντρο διασχίζεται Breadthwise. Θα μάθετε επίσης τον αλγόριθμο και την εφαρμογή BFS:

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

Το Traversal είναι η τεχνική με την οποία επισκέπτουμε κάθε κόμβο του γραφήματος ή ενός δέντρου. Υπάρχουν δύο τυπικές μέθοδοι διέλευσης.

  • Πρώτη αναζήτηση (BFS)
  • Αναζήτηση πρώτου βάθους (DFS)

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

καλύτερο πρόγραμμα για κλωνοποίηση σκληρού δίσκου

Πρώτη αναζήτηση στο C ++

Τι θα μάθετε:

Τεχνική Breadth First Search (BFS) σε C ++

Σε αυτό το σεμινάριο, θα συζητήσουμε λεπτομερώς την τεχνική αναζήτησης πρώτης έκτασης.

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

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

Αλγόριθμος Πρώτης Αναζήτησης Breadth

Παρακάτω δίνεται ο αλγόριθμος για την τεχνική BFS.

Σκεφτείτε το G ως γράφημα που θα διασχίσουμε χρησιμοποιώντας τον αλγόριθμο BFS.

Αφήστε το S να είναι ο ριζικός / αρχικός κόμβος του γραφήματος.

  • Βήμα 1: Ξεκινήστε με τον κόμβο S και τοποθετήστε τον στην ουρά.
  • Βήμα 2: Επαναλάβετε τα παρακάτω βήματα για όλους τους κόμβους στο γράφημα.
  • Βήμα 3: Dequeue S και επεξεργαστείτε το.
  • Βήμα 4: Τοποθετήστε όλους τους γειτονικούς κόμβους του S και επεξεργαστείτε τους.
  • (ΤΕΛΟΣ ΒΡΟΧΟΥ)
  • Βήμα 6: ΕΞΟΔΟΣ

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

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

Procedure BFS (G, s) G is the graph and s is the source node begin let q be queue to store nodes q.enqueue(s) //insert source node in the queue mark s as visited. while (q is not empty) //remove the element from the queue whose adjacent nodes are to be processed n = q.dequeue( ) //processing all the adjacent nodes of n for all neighbors m of n in Graph G if w is not visited q.enqueue (m) //Stores m in Q to in turn visit its adjacent nodes mark m as visited. end

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

BFS Illustrations Βήμα 1

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

BFS Illustrations Βήμα 2

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

οι καλύτεροι προγραμματιστές παιχνιδιών για να εργαστούν

BFS Illustrations Βήμα 3

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

BFS Illustrations Βήμα 4

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

BFS Illustrations Βήμα 5

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

BFS Illustrations Βήμα 6

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

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

Υλοποίηση BFS

#include #include using namespace std; // a directed graph class class DiGraph { int V; // No. of vertices // Pointer to an array containing adjacency lists list *adjList; public: DiGraph(int V); // Constructor // add an edge from vertex v to w void addEdge(int v, int w); // BFS traversal sequence starting with s ->starting node void BFS(int s); }; DiGraph::DiGraph(int V) { this->V = V; adjList = new list (V); } void DiGraph::addEdge(int v, int w) { adjList(v).push_back(w); // Add w to v’s list. } void DiGraph::BFS(int s) { // initially none of the vertices is visited bool *visited = new bool(V); for(int i = 0; i queue; // Mark the current node as visited and enqueue it visited(s) = true; queue.push_back(s); // iterator 'i' to get all adjacent vertices list ::iterator i; while(!queue.empty()) { // dequeue the vertex s = queue.front(); cout << s << ' '; queue.pop_front(); // get all adjacent vertices of popped vertex and process each if not already visited for (i = adjList(s).begin(); i != adjList(s).end(); ++i) { if (!visited(*i)) { visited(*i) = true; queue.push_back(*i); } } } } // main program int main() { // create a graph DiGraph dg(5); dg.addEdge(0, 1); dg.addEdge(0, 2); dg.addEdge(0, 3); dg.addEdge(1, 2); dg.addEdge(2, 4); dg.addEdge(3, 3); dg.addEdge(4, 4); cout << 'Breadth First Traversal for given graph (with 0 as starting node): '<

Παραγωγή:

πώς να προσθέσετε έναν ακέραιο σε έναν πίνακα στο java

Breadth-First Traversal για το δεδομένο γράφημα (με 0 ως κόμβο εκκίνησης):

0 1 2 3 4

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

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

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

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

Εάν χρησιμοποιούμε τη λίστα γειτνίασης (όπως στην εφαρμογή μας), τότε η πολυπλοκότητα του χρόνου είναι O (| V | + | E |).

Εάν χρησιμοποιούμε τη μήτρα παρακέντησης, τότε η πολυπλοκότητα του χρόνου είναι O (V^2) .

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

Όταν ο αριθμός των κορυφών υπερβαίνει τον αριθμό των άκρων, τότε το γράφημα λέγεται ότι είναι αραιά συνδεδεμένο καθώς θα υπάρχουν πολλές αποσυνδεδεμένες κορυφές. Σε αυτήν την περίπτωση, η χρονική πολυπλοκότητα του γραφήματος θα είναι O (V).

Από την άλλη πλευρά, μερικές φορές το γράφημα μπορεί να έχει μεγαλύτερο αριθμό ακμών από τον αριθμό κορυφών. Σε μια τέτοια περίπτωση, το γράφημα λέγεται ότι είναι πυκνοκατοικημένο. Η χρονική πολυπλοκότητα ενός τέτοιου γραφήματος είναι O (E).

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

Εφαρμογές του BFS Traversal

  • Συλλογή απορριμάτων: Η τεχνική συλλογής απορριμμάτων, ο 'αλγόριθμος Cheney' χρησιμοποιεί την πρώτη διασταύρωση για την αντιγραφή της συλλογής απορριμμάτων.
  • Μετάδοση σε δίκτυα: Ένα πακέτο ταξιδεύει από έναν κόμβο σε έναν άλλο χρησιμοποιώντας την τεχνική BFS στο δίκτυο μετάδοσης για να φτάσει σε όλους τους κόμβους.
  • Πλοήγηση GPS: Μπορούμε να χρησιμοποιήσουμε το BFS στην πλοήγηση GPS για να βρούμε όλους τους γειτονικούς ή γειτονικούς κόμβους τοποθεσίας.
  • Ιστοσελίδες κοινωνικής δικτύωσης: Λαμβάνοντας υπόψη ένα άτομο «P», μπορούμε να βρούμε όλα τα άτομα σε απόσταση, «d» από το p χρησιμοποιώντας BFS μέχρι τα d επίπεδα.
  • Δίκτυα Peer To Peer: Και πάλι το BFS μπορεί να χρησιμοποιηθεί σε δίκτυα peer to peer για να βρει όλους τους γειτονικούς κόμβους.
  • Συντομότερη διαδρομή και ελάχιστο δέντρο έκτασης στο μη σταθμισμένο γράφημα: Η τεχνική BFS χρησιμοποιείται για τον εντοπισμό της συντομότερης διαδρομής, δηλαδή της διαδρομής με τον μικρότερο αριθμό ακμών στο μη σταθμισμένο γράφημα. Ομοίως, μπορούμε επίσης να βρούμε ένα ελάχιστο δέντρο έκτασης χρησιμοποιώντας BFS στο μη σταθμισμένο γράφημα.

συμπέρασμα

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

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

=> Κάντε κλικ εδώ για το δωρεάν μάθημα C ++.

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

^