Menu

Programme C ++ BFS (Breadth First Search) pour parcourir un graphique ou un arbre

  • Principal
  • Autre
  • Programme C ++ BFS (Breadth First Search) pour parcourir un graphique ou un arbre

breadth first search c program traverse graph

Ce didacticiel couvre la première recherche en largeur dans C ++ dans laquelle le graphique ou l'arborescence est parcouru dans le sens de la largeur. Vous apprendrez également l'algorithme et l'implémentation BFS:

Ce didacticiel explicite C ++ vous donnera une explication détaillée des techniques de traversée qui peuvent être effectuées sur un arbre ou un graphique.

La traversée est la technique à l'aide de laquelle nous visitons chaque nœud du graphe ou d'un arbre. Il existe deux méthodes standard de parcours.

  • Recherche en largeur d'abord (BFS)
  • Recherche en profondeur d'abord (DFS)

=> Voir ici pour explorer la liste complète des didacticiels C ++.

Recherche en largeur d

fonction de tri de bulles c ++

Ce que vous apprendrez:

Technique de recherche en largeur (BFS) en C ++

Dans ce didacticiel, nous aborderons en détail la technique de recherche en largeur d'abord.

Dans la technique de traversée en largeur d'abord, le graphe ou l'arbre est parcouru dans le sens de la largeur. Cette technique utilise la structure de données de la file d'attente pour stocker les sommets ou nœuds et également pour déterminer quel sommet / nœud doit être repris ensuite.

L'algorithme en largeur d'abord commence par le nœud racine, puis traverse tous les nœuds adjacents. Ensuite, il sélectionne le nœud le plus proche et explore tous les autres nœuds non visités. Ce processus est répété jusqu'à ce que tous les nœuds du graphe soient explorés.

Algorithme de recherche en largeur d'abord

Ci-dessous est l'algorithme pour la technique BFS.

Considérez G comme un graphe que nous allons parcourir en utilisant l'algorithme BFS.

Soit S le nœud racine / de départ du graphe.

  • Étape 1: Commencez par le nœud S et placez-le dans la file d'attente.
  • Étape 2: Répétez les étapes suivantes pour tous les nœuds du graphique.
  • Étape 3: Déposez S et traitez-le.
  • Étape 4: Mettez en file d'attente tous les nœuds adjacents de S et traitez-les.
  • [FIN DE BOUCLE]
  • Étape 6: SORTIR

Pseudocode

Le pseudo-code de la technique BFS est donné ci-dessous.

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

Traversées avec illustrations

Illustrations BFS Étape 1

Soit 0 le nœud de départ ou le nœud source. Tout d'abord, nous le mettons en file d'attente dans la file d'attente visitée et tous ses nœuds adjacents dans la file d'attente.

Illustrations BFS Étape 2

Ensuite, nous prenons l'un des nœuds adjacents à traiter, c'est-à-dire 1. Nous le marquons comme visité en le supprimant de la file d'attente et en plaçant ses nœuds adjacents dans la file d'attente (2 et 3 déjà en file d'attente). Comme 0 est déjà visité, nous l'ignorons.

Illustrations BFS Étape 3

comment utiliser le tri en java

Ensuite, nous retirons le nœud 2 de la file d'attente et le marquons comme visité. Ensuite, son nœud adjacent 4 est ajouté à la file d'attente.

Illustrations BFS Étape 4

Ensuite, nous retirons 3 de la file d'attente et le marquons comme visité. Le nœud 3 n'a qu'un seul nœud adjacent, c'est-à-dire 0 qui est déjà visité. Par conséquent, nous l'ignorons.

Illustrations BFS Étape 5

A ce stade, seul le nœud 4 est présent dans la file d'attente. Son nœud adjacent 2 est déjà visité, donc nous l'ignorons. Maintenant, nous marquons 4 comme visité.

Illustrations BFS Étape 6

Ensuite, la séquence présente dans la liste visitée est la traversée en largeur du graphe donné.

Si nous observons le graphe donné et la séquence de parcours, nous pouvons remarquer que pour l'algorithme BFS, nous parcourons en effet le graphe dans le sens de la largeur puis passons au niveau suivant.

Implémentation 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): '<

Production:

Traversée en largeur d'abord pour le graphe donné (avec 0 comme nœud de départ):

questions d'entrevue sur le savon et le repos

0 1 2 3 4

Nous avons implémenté le BFS dans le programme ci-dessus. Notez que le graphique se présente sous la forme d'une liste de contiguïté, puis nous utilisons un itérateur pour parcourir la liste et effectuer BFS.

Nous avons utilisé le même graphique que nous avons utilisé à des fins d'illustration comme entrée du programme pour comparer la séquence de parcours.

Analyse d'exécution

Si V est le nombre de sommets et E est le nombre d'arêtes d'un graphe, alors la complexité temporelle pour BFS peut être exprimée comme O (| V | + | E |) . Cela dit, cela dépend également de la structure de données que nous utilisons pour représenter le graphique.

Si nous utilisons la liste de contiguïté (comme dans notre implémentation), alors la complexité temporelle est O (| V | + | E |).

Si nous utilisons la matrice de contiguïté, alors la complexité temporelle est O (V ^ 2) .

Outre les structures de données utilisées, il existe également un facteur selon lequel le graphe est densément peuplé ou peu peuplé.

Lorsque le nombre de sommets dépasse le nombre d'arêtes, on dit que le graphe est faiblement connecté car il y aura de nombreux sommets déconnectés. Dans ce cas, la complexité temporelle du graphe sera O (V).

D'un autre côté, le graphe peut parfois avoir un nombre d'arêtes supérieur au nombre de sommets. Dans un tel cas, on dit que le graphe est densément peuplé. La complexité temporelle d'un tel graphe est O (E).

Pour conclure, ce que signifie l'expression O (| V | + | E |) dépend du fait que le graphe est densément ou peu peuplé, le facteur dominant c'est-à-dire les arêtes ou les sommets déterminera la complexité temporelle du graphe en conséquence.

Applications de BFS Traversal

  • Collecte des ordures: La technique de récupération de place, «l'algorithme de Cheney», utilise une traversée en largeur pour copier la récupération de place.
  • Diffusion dans les réseaux: Un paquet voyage d'un nœud à un autre en utilisant la technique BFS dans le réseau de diffusion pour atteindre tous les nœuds.
  • Navigation GPS: Nous pouvons utiliser BFS dans la navigation GPS pour trouver tous les nœuds de localisation adjacents ou voisins.
  • Sites Web de réseautage social: Étant donné une personne «P», nous pouvons trouver toutes les personnes à une distance, «d» de p en utilisant BFS jusqu'aux niveaux d.
  • Réseaux peer to peer: Encore une fois, BFS peut être utilisé dans les réseaux peer to peer pour trouver tous les nœuds adjacents.
  • Chemin le plus court et arbre couvrant minimum dans le graphique non pondéré: La technique BFS est utilisée pour trouver le chemin le plus court, c'est-à-dire le chemin avec le moins d'arêtes dans le graphe non pondéré. De même, nous pouvons également trouver un arbre couvrant minimum en utilisant BFS dans le graphe non pondéré.

Conclusion

La technique de recherche en largeur d'abord est une méthode qui permet de parcourir tous les nœuds d'un graphe ou d'un arbre de manière large.

Cette technique est principalement utilisée pour trouver le chemin le plus court entre les nœuds d'un graphe ou dans les applications qui nous obligent à visiter chaque nœud adjacent comme dans les réseaux.

=> Cliquez ici pour le cours C ++ gratuit.

lecture recommandée

^