RECHERCHE EN LARGEUR D'ABORD OU BFS POUR UN GRAPHIQUE

Recherche en largeur d'abord (BFS) est un élément fondamental algorithme de parcours graphique . Il s’agit de visiter tous les nœuds connectés d’un graphe de manière niveau par niveau. Dans cet article, nous examinerons le concept de BFS et comment il peut être appliqué efficacement aux graphiques

Table des matières

Recherche en largeur d'abord ou BFS pour un graphique
Relation entre BFS pour Graph et BFS pour Tree
Recherche en largeur d'abord (BFS) pour un algorithme graphique
Comment fonctionne l’algorithme BFS ?
Implémentation de BFS pour Graph à l'aide de la liste de contiguïté
Complexité de l'algorithme de recherche en largeur d'abord (BFS)
Applications de BFS dans les graphiques
Problèmes lors de la recherche en largeur d'abord ou BFS pour un graphique
FAQ sur la recherche en largeur d'abord (BFS) pour un graphique

Recherche en largeur d'abord (BFS) pour un graphique :

Recherche en largeur d'abord (BFS) est un algorithme de parcours de graphe qui explore tous les sommets d'un graphe à la profondeur actuelle avant de passer aux sommets du niveau de profondeur suivant. Il commence à un sommet spécifié et visite tous ses voisins avant de passer au niveau de voisins suivant. BFS est couramment utilisé dans les algorithmes de recherche de chemin, de composants connectés et de problèmes de chemin le plus court dans les graphiques.

Relation entre BFS pour Graph et BFS pour Arbre :

Le parcours en largeur en premier (BFS) pour un graphique est similaire au Traversée en largeur d'un arbre .

Le seul problème ici est que, contrairement à des arbres , graphiques peut contenir des cycles, nous pouvons donc revenir au même nœud. Pour éviter de traiter un nœud plus d'une fois, nous divisons les sommets en deux catégories :

erreur d'attribut python

Visité et
Non visité.

Un tableau booléen visité est utilisé pour marquer les sommets visités. Pour simplifier, on suppose que tous les sommets sont accessibles à partir du sommet de départ. BFS les usages un Recherche en largeur d'abord (BFS) pour un algorithme graphique :

Discutons de l'algorithme du BFS :

Initialisation : Mettez le nœud de départ dans une file d'attente et marquez-le comme visité.
Exploration: Tant que la file d'attente n'est pas vide :
- Retirez un nœud de la file d'attente et visitez-le (par exemple, imprimez sa valeur).
- Pour chaque voisin non visité du nœud retiré de la file d'attente :
  - Mettez le voisin dans la file d'attente.
  - Marquez le voisin comme visité.
Résiliation: Répétez l'étape 2 jusqu'à ce que la file d'attente soit vide.

Cet algorithme garantit que tous les nœuds du graphique sont visités en largeur, en commençant par le nœud de départ.

Comment fonctionne l’algorithme BFS ?

En partant de la racine, tous les nœuds d'un niveau particulier sont d'abord visités, puis les nœuds du niveau suivant sont parcourus jusqu'à ce que tous les nœuds soient visités.

Pour ce faire, une file d'attente est utilisée. Tous les nœuds adjacents non visités du niveau actuel sont poussés dans la file d'attente et les nœuds du niveau actuel sont marqués comme visités et retirés de la file d'attente.

Illustration:

Comprenons le fonctionnement de l'algorithme à l'aide de l'exemple suivant.

Étape 1: Initialement, la file d'attente et les tableaux visités sont vides.

La file d'attente et les tableaux visités sont initialement vides.

Étape 2: Poussez le nœud 0 dans la file d’attente et marquez-le comme visité.

Poussez le nœud 0 dans la file d’attente et marquez-le comme visité.

Étape 3: Supprimez le nœud 0 du début de la file d'attente, visitez les voisins non visités et placez-les dans la file d'attente.

Supprimez le nœud 0 du début de la file d'attente, visitez les voisins non visités et placez-le dans la file d'attente.

Étape 4: Supprimez le nœud 1 du début de la file d'attente, visitez les voisins non visités et placez-les dans la file d'attente.

Supprimez le nœud 1 du début de la file d'attente, visitez les voisins non visités et poussez

Étape 5 : Supprimez le nœud 2 du début de la file d'attente, visitez les voisins non visités et placez-les dans la file d'attente.

Supprimez le nœud 2 du début de la file d'attente, visitez les voisins non visités et placez-les dans la file d'attente.

Étape 6 : Supprimez le nœud 3 du début de la file d'attente, visitez les voisins non visités et placez-les dans la file d'attente.
Comme nous pouvons voir que tous les voisins du nœud 3 sont visités, passez donc au nœud suivant qui se trouve en tête de la file d'attente.
applet applet

Supprimez le nœud 3 du début de la file d'attente, visitez les voisins non visités et placez-les dans la file d'attente.

Étapes 7 : Supprimez le nœud 4 du début de la file d'attente, visitez les voisins non visités et placez-les dans la file d'attente.
Comme nous pouvons voir que tous les voisins du nœud 4 sont visités, passez donc au nœud suivant qui se trouve en tête de la file d'attente.

Supprimez le nœud 4 du début de la file d'attente, visitez les voisins non visités et placez-les dans la file d'attente.

Maintenant, la file d'attente devient vide, alors mettez fin à ce processus d'itération.

Implémentation de BFS pour Graph à l'aide de la liste de contiguïté :

C++

 #include  #include  #include  using namespace std; // Function to perform Breadth First Search on a graph // represented using adjacency list void bfs(vector>& adjList, int startNode, vecteur & visité) { // Créer une file d'attente pour la file d'attente BFS q;  // Marque le nœud actuel comme visité et le met en file d'attente visité[startNode] = true;  q.push(startNode);  // Parcourez la file d'attente while (!q.empty()) { // Retirez un sommet de la file d'attente et imprimez-le int currentNode = q.front();  q.pop();  cout<< currentNode << ' ';  // Get all adjacent vertices of the dequeued vertex  // currentNode If an adjacent has not been visited,  // then mark it visited and enqueue it  for (int neighbor : adjList[currentNode]) {  if (!visited[neighbor]) {  visited[neighbor] = true;  q.push(neighbor);  }  }  } } // Function to add an edge to the graph void addEdge(vector>& adjList, int u, int v) { adjList[u].push_back(v); } int main() { // Nombre de sommets dans le graphique int vertices = 5;  // Représentation par liste de contiguïté du vecteur graphique> adjList(sommets);  // Ajoute des arêtes au graphique addEdge(adjList, 0, 1);  addEdge(adjList, 0, 2);  addEdge(adjList, 1, 3);  addEdge(adjList, 1, 4);  addEdge(adjList, 2, 4);  // Marque tous les sommets comme vecteur non visité visité(sommets, faux);  // Effectue un parcours BFS à partir du sommet 0 cout<< 'Breadth First Traversal starting from vertex '  '0: ';  bfs(adjList, 0, visited);  return 0; }>

 #include  #include  #define MAX_VERTICES 100 // Structure to represent a node in adjacency list struct Node {  int data;  struct Node* next; }; // Function to create a new node struct Node* createNode(int data) {  struct Node* newNode  = (struct Node*)malloc(sizeof(struct Node));  newNode->données = données ;  nouveauNode->suivant = NULL ;  retourner nouveauNode ; } // Fonction pour ajouter une arête au graphique void addEdge(struct Node* adjList[], int u, int v) { struct Node* newNode = createNode(v);  newNode->next = adjList[u];  adjList[u] = newNode; } // Fonction pour effectuer une recherche en largeur d'abord sur un graphique // représentée à l'aide d'une liste de contiguïté void bfs(struct Node* adjList[], int vertices, int startNode, int visited[]) { // Créer une file d'attente pour BFS int queue[ MAX_VERTICES] ;  int avant = 0, arrière = 0 ;  // Marque le nœud actuel comme visité et le met en file d'attente visité[startNode] = 1;  queue[arrière++] = startNode;  // Parcourez la file d'attente while (front != Rear) { // Retirez un sommet de la file d'attente et imprimez-le int currentNode = queue[front++];  printf('%d ', nœud actuel);  // Récupère tous les sommets adjacents du sommet retiré de la file d'attente // currentNode Si un adjacent n'a pas été visité, // alors marquez-le comme visité et mettez-le en file d'attente struct Node* temp = adjList[currentNode];  while (temp != NULL) { int voisin = temp->data;  if (!visited[voisin]) { visité[voisin] = 1;  queue[arrière++] = voisin ;  } temp = temp->suivant;  } } } int main() { // Nombre de sommets dans le graphique int vertices = 5;  // Représentation par liste de contiguïté du graphe struct Node* adjList[vertices];  pour (int je = 0; je< vertices; ++i)  adjList[i] = NULL;  // Add edges to the graph  addEdge(adjList, 0, 1);  addEdge(adjList, 0, 2);  addEdge(adjList, 1, 3);  addEdge(adjList, 1, 4);  addEdge(adjList, 2, 4);  // Mark all the vertices as not visited  int visited[vertices];  for (int i = 0; i < vertices; ++i)  visited[i] = 0;  // Perform BFS traversal starting from vertex 0  printf(  'Breadth First Traversal starting from vertex 0: ');  bfs(adjList, vertices, 0, visited);  return 0; }>

Java

 import java.util.LinkedList; import java.util.Queue; // Class to represent a graph using adjacency list class Graph {  int vertices;  LinkedList [] adjListe ;  @SuppressWarnings('unchecked') Graph(int vertices) { this.vertices = vertices;  adjList = new LinkedList[vertices];  pour (int je = 0; je< vertices; ++i)  adjList[i] = new LinkedList();  }  // Function to add an edge to the graph  void addEdge(int u, int v) { adjList[u].add(v); }  // Function to perform Breadth First Search on a graph  // represented using adjacency list  void bfs(int startNode)  {  // Create a queue for BFS  Queue file d'attente = nouvelle LinkedList();  boolean[] visité = new boolean[vertices];  // Marque le nœud actuel comme visité et le met en file d'attente visité[startNode] = true;  queue.add(startNode);  // Parcourir la file d'attente while (!queue.isEmpty()) { // Supprimer un sommet de la file d'attente et l'imprimer int currentNode = queue.poll();  System.out.print(currentNode + ' ');  // Récupère tous les sommets adjacents du // sommet currentNode retiré de la file d'attente. Si un adjacent n'a pas // été visité, alors marquez-le comme visité et // mettez-le en file d'attente pour (int voisin : adjList[currentNode]) { if (!visited[neighbor] ) { visité[voisin] = vrai ;  file d'attente.add (voisin);  } } } } } public class Main { public static void main(String[] args) { // Nombre de sommets dans le graphe int vertices = 5;  // Créer un graphique Graph graph = new Graph(vertices);  // Ajoute des arêtes au graphique graph.addEdge(0, 1);  graph.addEdge(0, 2);  graph.addEdge(1, 3);  graph.addEdge(1, 4);  graph.addEdge(2, 4);  // Effectuer un parcours BFS à partir du sommet 0 System.out.print( 'Breadth First Traversal à partir du sommet 0 : ');  graph.bfs(0);  } }>

Python3

 from collections import deque # Function to perform Breadth First Search on a graph # represented using adjacency list def bfs(adjList, startNode, visited): # Create a queue for BFS q = deque() # Mark the current node as visited and enqueue it visited[startNode] = True q.append(startNode) # Iterate over the queue while q: # Dequeue a vertex from queue and print it currentNode = q.popleft() print(currentNode, end=' ') # Get all adjacent vertices of the dequeued vertex # If an adjacent has not been visited, then mark it visited and enqueue it for neighbor in adjList[currentNode]: if not visited[neighbor]: visited[neighbor] = True q.append(neighbor) # Function to add an edge to the graph def addEdge(adjList, u, v): adjList[u].append(v) def main(): # Number of vertices in the graph vertices = 5 # Adjacency list representation of the graph adjList = [[] for _ in range(vertices)] # Add edges to the graph addEdge(adjList, 0, 1) addEdge(adjList, 0, 2) addEdge(adjList, 1, 3) addEdge(adjList, 1, 4) addEdge(adjList, 2, 4) # Mark all the vertices as not visited visited = [False] * vertices # Perform BFS traversal starting from vertex 0 print('Breadth First Traversal starting from vertex 0:', end=' ') bfs(adjList, 0, visited) if __name__ == '__main__': main()>

 using System; using System.Collections.Generic; // Class to represent a graph using adjacency list class Graph {  int vertices;  List [] adjListe ;  public Graph(int vertices) { this.vertices = vertices;  adjList = nouvelle liste [sommets];  pour (int je = 0; je< vertices; ++i)  adjList[i] = new List ();  } // Fonction pour ajouter une arête au graphe public void AddEdge(int u, int v) { adjList[u].Add(v); } // Fonction pour effectuer une recherche en largeur sur un graphique // représentée à l'aide d'une liste de contiguïté public void BFS(int startNode) { // Créer une file d'attente pour la file d'attente BFS file d'attente = nouvelle file d'attente ();  bool[] visité = new bool[vertices];  // Marque le nœud actuel comme visité et le met en file d'attente visité[startNode] = true;  queue.Enqueue(startNode);  // Parcourir la file d'attente while (queue.Count != 0) { // Supprimer un sommet de la file d'attente et l'imprimer int currentNode = queue.Dequeue();  Console.Write(currentNode + '');  // Récupère tous les sommets adjacents du // sommet currentNode retiré de la file d'attente. Si un adjacent n'a pas // été visité, alors marquez-le comme visité et // mettez-le en file d'attente foreach(int voisin in adjList[currentNode]) { if (!visited[neighbor] ) { visité[voisin] = vrai ;  queue.Enqueue (voisin);  } } } } } class MainClass { public static void Main(string[] args) { // Nombre de sommets dans le graphe int vertices = 5;  // Créer un graphique Graph graph = new Graph(vertices);  // Ajoute des arêtes au graphique graph.AddEdge(0, 1);  graph.AddEdge(0, 2);  graph.AddEdge(1, 3);  graph.AddEdge(1, 4);  graph.AddEdge(2, 4);  // Effectue un parcours BFS à partir du sommet 0 Console.Write( 'Breadth First Traversal à partir du sommet 0 : ');  graphique.BFS(0);  } }>

Javascript

 // Class to represent a graph using adjacency list class Graph {  constructor() {  this.adjList = {};  }  // Function to add an edge to the graph  addEdge(u, v) {  if (!this.adjList[u]) this.adjList[u] = [];  this.adjList[u].push(v);  }  // Function to perform Breadth First Search on a graph represented using adjacency list  bfs(startNode) {  // Create a queue for BFS  const queue = [];  const visited = new Array(Object.keys(this.adjList).length).fill(false);  // Mark the current node as visited and enqueue it  visited[startNode] = true;  queue.push(startNode);  // Iterate over the queue  while (queue.length !== 0) {  // Dequeue a vertex from queue and print it  const currentNode = queue.shift();  console.log(currentNode + ' ');  // Get all adjacent vertices of the dequeued vertex currentNode  // If an adjacent has not been visited, then mark it visited and enqueue it  for (const neighbor of this.adjList[currentNode] || []) {  if (!visited[neighbor]) {  visited[neighbor] = true;  queue.push(neighbor);  }  }  }  } } // Create a graph const graph = new Graph(); // Add edges to the graph graph.addEdge(0, 1); graph.addEdge(0, 2); graph.addEdge(1, 3); graph.addEdge(1, 4); graph.addEdge(2, 4); // Perform BFS traversal starting from vertex 0 console.log('Breadth First Traversal starting from vertex 0: '); graph.bfs(0);>

Sortir

Breadth First Traversal starting from vertex 0: 0 1 2 3 4>

Complexité temporelle : O(V+E), où V est le nombre de nœuds et E est le nombre d’arêtes.
Espace auxiliaire : O(V)

Analyse de la complexité de l'algorithme de recherche en largeur d'abord (BFS) :

Complexité temporelle de l'algorithme BFS : O (V + E)

BFS explore tous les sommets et arêtes du graphique. Dans le pire des cas, il visite chaque sommet et chaque arête une fois. Par conséquent, la complexité temporelle de BFS est O(V + E), où V et E sont le nombre de sommets et d’arêtes dans le graphe donné.

Complexité spatiale de l'algorithme BFS : O(V)

BFS utilise une file d'attente pour garder une trace des sommets qui doivent être visités. Dans le pire des cas, la file d'attente peut contenir tous les sommets du graphe. Par conséquent, la complexité spatiale de BFS est O(V), où V et E sont le nombre de sommets et d’arêtes dans le graphe donné.

Applications de BFS dans les graphiques :

BFS a diverses applications en théorie des graphes et en informatique, notamment :

Recherche du chemin le plus court : BFS peut être utilisé pour trouver le chemin le plus court entre deux nœuds dans un graphe non pondéré. En gardant une trace du parent de chaque nœud pendant le parcours, le chemin le plus court peut être reconstruit.
Détection de cycles : BFS peut être utilisé pour détecter des cycles dans un graphique. Si un nœud est visité deux fois pendant le parcours, cela indique la présence d'un cycle.
Composants connectés : BFS peut être utilisé pour identifier les composants connectés dans un graphique. Chaque composant connecté est un ensemble de nœuds accessibles les uns aux autres.
Tri topologique : BFS peut être utilisé pour effectuer un tri topologique sur un graphe acyclique dirigé (DAG). Le tri topologique organise les nœuds dans un ordre linéaire tel que pour toute arête (u, v), u apparaisse avant v dans l'ordre.
Traversée de l'ordre de niveau des arbres binaires : BFS peut être utilisé pour effectuer un parcours par ordre de niveau d’un arbre binaire. Cette traversée visite tous les nœuds du même niveau avant de passer au niveau suivant.
Routage réseau : BFS peut être utilisé pour trouver le chemin le plus court entre deux nœuds d'un réseau, ce qui le rend utile pour acheminer les paquets de données dans les protocoles réseau.

Problèmes lors de la recherche en largeur d'abord ou BFS pour un graphique :

Oui Non	Problèmes	Pratique
1.	Trouver le niveau d'un nœud donné dans un graphique non orienté	Lien
2.	Minimiser la différence adjacente maximale dans un chemin du coin supérieur gauche au coin inférieur droit	Lien
dix.	Vérifiez si la destination d'une matrice donnée est accessible avec les valeurs requises des cellules	Lien

FAQ sur la recherche en largeur d'abord (BFS) pour un graphique :

Question 1: Qu’est-ce que BFS et comment ça marche ?

Répondre: BFS est un algorithme de parcours de graphe qui explore systématiquement un graphe en visitant tous les sommets d'un niveau donné avant de passer au niveau suivant. Il part d'un sommet de départ, le met en file d'attente et le marque comme visité. Ensuite, il retire un sommet de la file d'attente, le visite et met tous ses voisins non visités dans la file d'attente. Ce processus se poursuit jusqu'à ce que la file d'attente soit vide.

Question 2: Quelles sont les applications du BFS ?

Répondre: BFS a diverses applications, notamment la recherche du chemin le plus court dans un graphe non pondéré, la détection de cycles dans un graphe, le tri topologique d'un graphe acyclique orienté (DAG), la recherche de composants connectés dans un graphe et la résolution d'énigmes comme des labyrinthes et du Sudoku.

Question 3: Quelle est la complexité temporelle de BFS ?

Répondre: La complexité temporelle de BFS est O(V + E), où V est le nombre de sommets et E est le nombre d'arêtes du graphe.

Question 4 : Quelle est la complexité spatiale de BFS ?

Répondre: La complexité spatiale de BFS est O(V), car il utilise une file d'attente pour garder une trace des sommets qui doivent être visités.

Question 5 : Quels sont les avantages d’utiliser BFS ?

Répondre: BFS est simple à mettre en œuvre et efficace pour trouver le chemin le plus court dans un graphe non pondéré. Cela garantit également que tous les sommets du graphe sont visités.
logique propositionnelle

Articles Liés:

Articles récents sur BFS
Première traversée en profondeur
Applications de la traversée en largeur d'abord
Applications de la recherche en profondeur d’abord
Complexité temporelle et spatiale de la recherche en largeur d'abord (BFS)