breadth first search c program traverse graph
Aquest tutorial cobreix la primera cerca de l'amplada en C ++ en la qual el gràfic o l'arbre es recorre en sentit ampli. També aprendreu l'algorisme i la implementació de BFS:
Aquest tutorial explícit de C ++ us proporcionarà una explicació detallada de les tècniques de recorregut que es poden realitzar en un arbre o gràfic.
El transversal és la tècnica amb la qual visitem tots els nodes del gràfic o d’un arbre. Hi ha dos mètodes estàndard de recorreguts.
- Primera cerca per amplada (BFS)
- Primera cerca (DFS)
=> Vegeu aquí per explorar la llista completa de tutorials de C ++.
què és un pla de prova a qa
Què aprendreu:
Tècnica Breadth First Search (BFS) a C ++
En aquest tutorial, analitzarem detalladament la tècnica de cerca de primera amplada.
En la tècnica de la primera travessia d'amplada, el gràfic o l'arbre es recorre ampli. Aquesta tècnica utilitza l’estructura de dades de la cua per emmagatzemar els vèrtexs o nodes i també per determinar quin vèrtex / node s’hauria d’ocupar a continuació.
L’algorisme de amplitud inicial comença amb el node arrel i després recorre tots els nodes adjacents. A continuació, selecciona el node més proper i explora tots els altres nodes sense visitar. Aquest procés es repeteix fins que s’exploren tots els nodes del gràfic.
Algorisme de cerca de amplada-primera
A continuació es mostra l'algorisme de la tècnica BFS.
Considereu G com un gràfic que recorrerem mitjançant l’algorisme BFS.
Sigui S el node arrel / inicial del gràfic.
- Pas 1: Comenceu amb el node S i poseu-lo a la cua.
- Pas 2: Repetiu els passos següents per a tots els nodes del gràfic.
- Pas 3: Desqueu S i processeu-lo.
- Pas 4: Posar a la cua tots els nodes adjacents de S i processar-los.
- (FI DE LAÇA)
- Pas 6: SORTIR
Pseudocodi
A continuació es dóna el pseudocodi per a la tècnica 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. endTraversals amb il·lustracions
Sigui 0 el node inicial o el node font. En primer lloc, el posem a la cua visitada i tots els seus nodes adjacents a la cua.
A continuació, agafem un dels nodes adjacents a processar, és a dir, 1. El marquem com a visitat traient-lo de la cua i posem els nodes adjacents a la cua (2 i 3 ja estan a la cua). Com que ja es visita 0, ho ignorem.
com ser un programador per a principiants
A continuació, retirem el node 2 i el marquem com a visitat. A continuació, el node adjacent 4 s’afegeix a la cua.
A continuació, retirem 3 de la cua i el marquem com a visitat. El node 3 només té un node adjacent, és a dir, 0 que ja es visita. Per tant, ho ignorem.
En aquesta etapa, només hi ha el node 4 a la cua. El seu node adjacent 2 ja està visitat, de manera que l’ignorem. Ara marquem 4 com a visitades.
A continuació, la seqüència present a la llista visitada és la primera amplada del gràfic donat.
Si observem el gràfic donat i la seqüència de recorregut, podem observar que, per a l'algorisme BFS, realment recorrem el gràfic en funció de la seva amplitud i després passem al següent nivell.
Implementació de 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): '< Sortida:
com inicialitzar la variable estàtica en c ++
Amplada-Primera travessa per al gràfic donat (amb 0 com a node d'inici):
0 1 2 3 4
Hem implementat el BFS al programa anterior. Tingueu en compte que el gràfic té la forma d’una llista d’adjacència i, a continuació, fem servir un iterador per recórrer la llista i realitzar BFS.
Hem utilitzat el mateix gràfic que hem utilitzat per il·lustrar com a entrada al programa per comparar la seqüència de recorregut.
Anàlisi del temps d'execució
Si V és el nombre de vèrtexs i E és el nombre d’arestes d’un gràfic, la complexitat temporal de BFS es pot expressar com O (| V | + | E |) . Dit això, també depèn de l'estructura de dades que fem servir per representar el gràfic.
Si fem servir la llista d’adjacències (com a la nostra implementació), la complexitat temporal serà O (| V | + | E |).
Si fem servir la matriu d’adjacència, la complexitat temporal és O (V ^ 2) .
A part de les estructures de dades utilitzades, també hi ha un factor de si el gràfic està densament poblat o poc poblat.
Quan el nombre de vèrtexs supera el nombre d’arestes, aleshores es diu que el gràfic està poc connectat, ja que hi haurà molts vèrtexs desconnectats. En aquest cas, la complexitat temporal del gràfic serà O (V).
D'altra banda, de vegades el gràfic pot tenir un nombre d'arestes superior al nombre de vèrtexs. En aquest cas, es diu que el gràfic és densament poblat. La complexitat temporal d’aquest gràfic és O (E).
Per concloure, el que significa l’expressió O (| V | + | E |) depèn de si el gràfic està dens o poc poblat, el factor dominant, és a dir, arestes o vèrtexs, determinarà la complexitat temporal del gràfic en conseqüència.
Aplicacions de BFS Traversal
- Recollida d'escombraries: La tècnica de recollida d’escombraries, “algoritme de Cheney”, utilitza un recorregut ampli per copiar la recollida d’escombraries.
- Emissió a xarxes: Un paquet viatja d’un node a un altre mitjançant la tècnica BFS de la xarxa de difusió per arribar a tots els nodes.
- Navegació GPS: Podem utilitzar BFS a la navegació GPS per trobar tots els nodes d’ubicació adjacents o veïns.
- Llocs web de xarxes socials: Donat a una persona 'P', podem trobar totes les persones a una distància, 'd' des de p utilitzant BFS fins als d nivells.
- Xarxes d'igual a igual: Una vegada més, BFS es pot utilitzar en xarxes peer to peer per trobar tots els nodes adjacents.
- Camí més curt i arbre d’extensió mínim al gràfic no ponderat: La tècnica BFS s’utilitza per trobar el camí més curt, és a dir, el camí amb el menor nombre d’arestes al gràfic sense ponderar. De la mateixa manera, també podem trobar un arbre d’extensió mínim mitjançant BFS al gràfic no ponderat.
Conclusió
La tècnica de cerca per primera amplada és un mètode que s’utilitza per recórrer tots els nodes d’un gràfic o d’un arbre de manera ampla.
Aquesta tècnica s'utilitza principalment per trobar el camí més curt entre els nodes d'un gràfic o en aplicacions que requereixen que visitem tots els nodes adjacents, com a les xarxes.
=> Feu clic aquí per obtenir el curs gratuït de C ++.
Lectura recomanada
- Arbre de cerca binària C ++: implementació i operacions de BST amb exemples
- Estructura de dades d’arbre B i arbre B + en C ++
- Implementació de gràfics a C ++ mitjançant la llista d’adjacències
- Estructura de dades de l'arbre binari en C ++
- 12 millors eines per crear gràfics de línies per crear gràfics de línies impressionants (CLASSIFICACIONS 2021)
- Arbre AVL i estructura de dades Heap a C ++
- Arbres a C ++: terminologia bàsica, tècniques transversals i tipus d’arbres de C ++
- Gràfic de causes i efectes: tècnica d'escriptura de casos dinàmics de prova per a una cobertura màxima amb menys casos de proves