Breadth First Search (BFS) és fonamental algorisme de recorregut de gràfics . Implica visitar tots els nodes connectats d'un gràfic d'una manera nivell per nivell. En aquest article, analitzarem el concepte de BFS i com es pot aplicar als gràfics de manera eficaç

Taula de contingut

• Breadth First Search o BFS per a un gràfic
• Relació entre BFS per a gràfic i BFS per a arbre
• Breadth First Search (BFS) per a un algorisme gràfic
• Com funciona l'algoritme BFS?
• Implementació de BFS per a gràfics mitjançant la llista d'adjacència
• Complexitat de l'algoritme de cerca en amplitud (BFS).
• Aplicacions de BFS en gràfics
• Problemes amb Breadth First Search o BFS per a un gràfic
• Preguntes freqüents sobre Breadth First Search (BFS) per a un gràfic

Breadth First Search (BFS) per a un gràfic:

Breadth First Search (BFS) és un algorisme de recorregut de gràfics que explora tots els vèrtexs d'un gràfic a la profunditat actual abans de passar als vèrtexs al següent nivell de profunditat. Comença en un vèrtex especificat i visita tots els seus veïns abans de passar al següent nivell de veïns. BFS s'utilitza habitualment en algorismes per a la cerca de camins, components connectats i problemes de camí més curt en gràfics.

Relació entre BFS per a gràfic i BFS per a arbre:

El recorregut de l'amplada primer (BFS) per a un gràfic és similar al Amplada-Primera Travessia d'un arbre .

L'únic problema aquí és que, a diferència arbres , gràfics pot contenir cicles, de manera que podem tornar al mateix node. Per evitar processar un node més d'una vegada, dividim els vèrtexs en dues categories:

• Visitat i
• No visitat.

S'utilitza una matriu booleana visitada per marcar els vèrtexs visitats. Per simplificar, s'assumeix que tots els vèrtexs són accessibles des del vèrtex inicial. BFS usos a Breadth First Search (BFS) per a un algorisme gràfic:

Parlem de l'algorisme per al BFS:

1. Inicialització: Col·loqueu el node inicial a una cua i marqueu-lo com a visitat.
2. Exploració: Mentre la cua no estigui buida:
   • Traieu un node de la cua i visiteu-lo (p. ex., imprimiu-ne el valor).
   • Per a cada veí no visitat del node retirat de la cua:
     • Posa el veí a la cua.
     • Marca el veí com a visitat.
3. Terminació: Repetiu el pas 2 fins que la cua estigui buida.

Aquest algorisme assegura que tots els nodes del gràfic es visiten d'una manera ample, començant pel node inicial.

Com funciona l'algoritme BFS?

A partir de l'arrel, primer es visiten tots els nodes d'un nivell particular i després es recorren els nodes del següent nivell fins que es visiten tots els nodes.

c booleà

Per fer-ho s'utilitza una cua. Tots els nodes adjacents no visitats del nivell actual s'envien a la cua i els nodes del nivell actual es marquen com a visitats i es surten de la cua.

Il·lustració:

Entenem el funcionament de l'algorisme amb l'ajuda de l'exemple següent.

Pas 1: Inicialment, la cua i les matrius visitades estan buides.

La cua i les matrius visitades estan buides inicialment.

Pas 2: Introduïu el node 0 a la cua i marqueu-lo com a visitat.

Introduïu el node 0 a la cua i marqueu-lo com a visitat.

Pas 3: Traieu el node 0 de la part davantera de la cua i visiteu els veïns no visitats i introduïu-los a la cua.

Traieu el node 0 de la part davantera de la cua i visiteu els veïns no visitats i introduïu-lo a la cua.

Pas 4: Traieu el node 1 de la part davantera de la cua i visiteu els veïns no visitats i introduïu-los a la cua.

Traieu el node 1 de la part davantera de la cua i visiteu els veïns no visitats i premeu

Pas 5: Traieu el node 2 de la part davantera de la cua i visiteu els veïns no visitats i introduïu-los a la cua.

Traieu el node 2 de la part davantera de la cua i visiteu els veïns no visitats i introduïu-los a la cua.

Pas 6: Traieu el node 3 de la part davantera de la cua i visiteu els veïns no visitats i introduïu-los a la cua.
Com podem veure que es visiten tots els veïns del node 3, passeu al següent node que es troba al davant de la cua.

Traieu el node 3 de la part davantera de la cua i visiteu els veïns no visitats i introduïu-los a la cua.

Pas 7: Traieu el node 4 de la part davantera de la cua i visiteu els veïns no visitats i introduïu-los a la cua.
Com podem veure que es visiten tots els veïns del node 4, passeu al següent node que es troba al davant de la cua.

Traieu el node 4 de la part davantera de la cua i visiteu els veïns no visitats i introduïu-los a la cua.

Ara, la cua es queda buida, per tant, finalitza aquest procés d'iteració.

Implementació de BFS per a gràfics mitjançant la llista d'adjacència:

#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, vector & visitat) { // Crea una cua per a la cua BFS q;  // Marca el node actual com a visitat i posa a la cua el que ha visitat[startNode] = true;  q.push(startNode);  // Recorre la cua mentre (!q.empty()) { // Treu un vèrtex de la cua i imprimeix-lo 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 vèrtexs al gràfic int vèrtexs = 5;  // Representació de la llista d'adjacència del vector gràfic> adjList(vèrtexs);  // Afegeix vores al gràfic addEdge(adjList, 0, 1);  addEdge(adjList, 0, 2);  addEdge(adjList, 1, 3);  addEdge(adjList, 1, 4);  addEdge(adjList, 2, 4);  // Marca tots els vèrtexs com a vectors no visitats visitat (vèrtexs, fals);  // Realitzeu la travessa BFS a partir del vèrtex 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->dades = dades;  nouNode->següent = NULL;  retornar nouNode; } // Funció per afegir una vora al gràfic void addEdge(struct Node* adjList[], int u, int v) { struct Node* newNode = createNode(v);  nouNode->següent = adjList[u];  adjList[u] = nouNode; } // Funció per realitzar la primera cerca de l'amplada en un gràfic // representat mitjançant la llista d'adjacència void bfs(struct Node* adjList[], int vèrtex, int startNode, int visited[]) { // Crea una cua per a BFS int queue[ MAX_VERTICES];  int davant = 0, posterior = 0;  // Marca el node actual com a visitat i posa a la cua el que ha visitat[startNode] = 1;  cua[rear++] = startNode;  // Iterar sobre la cua mentre (front != posterior) { // Treu un vèrtex de la cua i imprimeix-lo int currentNode = queue[front++];  printf('%d', currentNode);  // Obté tots els vèrtexs adjacents del vèrtex descuat // currentNode Si no s'ha visitat un adjacent, // llavors marca'l visitat i posa-lo a la cua struct Node* temp = adjList[currentNode];  while (temp != NULL) { int veí = temp->dades;  if (!visitat[veí]) { visitat[veí] = 1;  cua[rear++] = veí;  } temp = temp->següent;  } } } int main() { // Nombre de vèrtexs al gràfic int vèrtexs = 5;  // Representació de la llista d'adjacència de l'estructura del gràfic Node* adjList[vèrtex];  per (int i = 0; i< 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; }>

import java.util.LinkedList; import java.util.Queue; // Class to represent a graph using adjacency list class Graph {  int vertices;  LinkedList [] adjList;  @SuppressWarnings('unchecked') Gràfic(int vèrtexs) { this.vertices = vèrtexs;  adjList = nova LinkedList[vèrtexs];  per (int i = 0; i< 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 cua = new LinkedList();  booleà[] visitat = booleà nou[vèrtexs];  // Marca el node actual com a visitat i posa a la cua el que ha visitat[startNode] = true;  queue.add(startNode);  // Itera sobre la cua mentre (!queue.isEmpty()) { // Treu un vèrtex de la cua i imprimeix-lo int currentNode = queue.poll();  System.out.print(currentNode + ' ');  // Obteniu tots els vèrtexs adjacents del // vèrtex currentNode retirat de la cua Si no s'ha // visitat un adjacent, aleshores marqueu-lo com a visitat i // poseu-lo a la cua per (int veí : adjList[currentNode]) { if (!visited[neighbor] ) { visitat[veí] = cert;  queue.add(veí);  } } } } } public class Main { public static void main(String[] args) { // Nombre de vèrtexs al gràfic int vèrtexs = 5;  // Crear un gràfic Graph graph = new Graph(vèrtexs);  // Afegeix arestes al gràfic graph.addEdge(0, 1);  graph.addEdge(0, 2);  graph.addEdge(1, 3);  graph.addEdge(1, 4);  graph.addEdge(2, 4);  // Realitzeu el recorregut BFS a partir del vèrtex 0 System.out.print('Primer recorregut de l'amplada a partir del vèrtex 0: ');  graph.bfs(0);  } }>>>Python 3

using System; using System.Collections.Generic; // Class to represent a graph using adjacency list class Graph {  int vertices;  List [] adjList;  public Graph(int vèrtexs) { this.vertices = vèrtexs;  adjList = llista nova [ vèrtexs ];  per (int i = 0; i< vertices; ++i)  adjList[i] = new List ();  } // Funció per afegir una vora al gràfic public void AddEdge(int u, int v) { adjList[u].Add(v); } // Funció per dur a terme la cerca d'amplada primer en un gràfic // representat mitjançant la llista d'adjacència public void BFS(int startNode) { // Crea una cua per a la cua BFS queue = cua nova ();  bool[] visitat = nou bool[vèrtex];  // Marca el node actual com a visitat i posa a la cua el que ha visitat[startNode] = true;  queue.Enqueue(startNode);  // Iterar sobre la cua mentre (queue.Count != 0) { // Treu la cua d'un vèrtex de la cua i imprimeix-lo int currentNode = queue.Dequeue();  Console.Write(currentNode + ' ');  // Obté tots els vèrtexs adjacents del // vèrtex currentNode retirat de la cua Si no s'ha // visitat un adjacent, aleshores marqueu-lo com a visitat i // poseu-lo a la cua foreach(int veí a adjList[currentNode]) { if (!visited[neighbor] ) { visitat[veí] = cert;  queue.Enqueue(veí);  } } } } } class MainClass { public static void Main(string[] args) { // Nombre de vèrtexs al gràfic int vèrtexs = 5;  // Crear un gràfic Graph graph = new Graph(vèrtexs);  // Afegeix arestes al gràfic del gràfic.AddEdge(0, 1);  graph.AddEdge(0, 2);  graph.AddEdge(1, 3);  graph.AddEdge(1, 4);  graph.AddEdge(2, 4);  // Realitzeu el recorregut BFS a partir del vèrtex 0 Console.Write( 'Breadth First Traversal a partir del vèrtex 0: ');  gràfic.BFS(0);  } }>>>Javascript

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

Complexitat temporal: O(V+E), on V és el nombre de nodes i E és el nombre d'arestes.
Espai auxiliar: O(V)

Anàlisi de complexitat de l'algoritme de cerca en amplitud (BFS):

Complexitat temporal de l'algoritme BFS: O(V + E)

• BFS explora tots els vèrtexs i arestes del gràfic. En el pitjor dels casos, visita cada vèrtex i aresta una vegada. Per tant, la complexitat temporal de BFS és O(V + E), on V i E són el nombre de vèrtexs i arestes del gràfic donat.

Complexitat espacial de l'algoritme BFS: O(V)

• BFS utilitza una cua per fer un seguiment dels vèrtexs que cal visitar. En el pitjor dels casos, la cua pot contenir tots els vèrtexs del gràfic. Per tant, la complexitat espacial de BFS és O(V), on V i E són el nombre de vèrtexs i arestes del gràfic donat.

Aplicacions de BFS en gràfics:

BFS té diverses aplicacions en teoria de grafs i informàtica, incloent:

• Trobada del camí més curt: BFS es pot utilitzar per trobar el camí més curt entre dos nodes en un gràfic no ponderat. Si feu un seguiment del pare de cada node durant el recorregut, es pot reconstruir el camí més curt.
• Detecció de cicle: BFS es pot utilitzar per detectar cicles en un gràfic. Si un node es visita dues vegades durant el recorregut, indica la presència d'un cicle.
• Components connectats: BFS es pot utilitzar per identificar components connectats en un gràfic. Cada component connectat és un conjunt de nodes als quals es pot accedir els uns dels altres.
• Ordenació topològica: BFS es pot utilitzar per fer una ordenació topològica en un graf acíclic dirigit (DAG). L'ordenació topològica ordena els nodes en un ordre lineal de manera que per a qualsevol aresta (u, v), u apareix abans de v en l'ordre.
• Travessament de l'ordre de nivell dels arbres binaris: BFS es pot utilitzar per realitzar un recorregut per ordre de nivell d'un arbre binari. Aquest recorregut visita tots els nodes al mateix nivell abans de passar al següent nivell.
• Enrutament de xarxa: BFS es pot utilitzar per trobar el camí més curt entre dos nodes d'una xarxa, cosa que el fa útil per encaminar paquets de dades en protocols de xarxa.

Problemes amb Breadth First Search o BFS per a un gràfic:

Preguntes freqüents sobre Breadth First Search (BFS) per a un gràfic:

Pregunta 1: Què és BFS i com funciona?

Resposta: BFS és un algorisme de recorregut de gràfics que explora sistemàticament un gràfic visitant tots els vèrtexs d'un nivell determinat abans de passar al següent nivell. Comença des d'un vèrtex inicial, el posa a la cua i el marca com a visitat. Aleshores, treu un vèrtex de la cua, el visita i posa a la cua tots els seus veïns no visitats. Aquest procés continua fins que la cua estigui buida.

Pregunta 2: Quines són les aplicacions de BFS?

Resposta: BFS té diverses aplicacions, com ara trobar el camí més curt en un gràfic no ponderat, detectar cicles en un gràfic, ordenar topològicament un gràfic acíclic dirigit (DAG), trobar components connectats en un gràfic i resoldre trencaclosques com laberints i Sudoku.

Pregunta 3: Quina és la complexitat temporal de BFS?

Resposta: La complexitat temporal de BFS és O(V + E), on V és el nombre de vèrtexs i E és el nombre d'arestes del gràfic.

Pregunta 4: Quina és la complexitat espacial de BFS?

Resposta: La complexitat espacial de BFS és O(V), ja que utilitza una cua per fer un seguiment dels vèrtexs que cal visitar.

Pregunta 5: Quins són els avantatges d'utilitzar BFS?

Resposta: BFS és senzill d'implementar i eficient per trobar el camí més curt en un gràfic no ponderat. També garanteix que es visiten tots els vèrtexs del gràfic.

string.compare c#

Articles relacionats:

• Articles recents sobre BFS
• Primer recorregut de profunditat
• Aplicacions de Breadth First Traversal
• Aplicacions de Depth First Search
• Complexitat temporal i espacial de la primera cerca en amplitud (BFS)