Breadth First Search (BFS) este o fundamentală algoritm de traversare a graficelor . Aceasta implică vizitarea tuturor nodurilor conectate ale unui grafic, nivel cu nivel. În acest articol, vom analiza conceptul de BFS și cum poate fi aplicat în mod eficient graficelor

Cuprins

• Breadth First Search sau BFS pentru un grafic
• Relația dintre BFS pentru Graph și BFS pentru Arbore
• Breadth First Search (BFS) pentru un algoritm grafic
• Cum funcționează algoritmul BFS?
• Implementarea BFS pentru Graph folosind Lista de adiacență
• Complexitatea algoritmului BFS (Broadth-First Search).
• Aplicații ale BFS în grafice
• Probleme la Breadth First Search sau BFS pentru un grafic
• Întrebări frecvente despre Breadth First Search (BFS) pentru un grafic

Breadth First Search (BFS) pentru un grafic:

Breadth First Search (BFS) este un algoritm de traversare a graficului care explorează toate vârfurile dintr-un grafic la adâncimea curentă înainte de a trece la vârfurile la nivelul următor de adâncime. Începe de la un punct specificat și își vizitează toți vecinii înainte de a trece la următorul nivel de vecini. BFS este utilizat în mod obișnuit în algoritmi pentru identificarea căii, componentele conectate și problemele cu calea cea mai scurtă în grafice.

Relația dintre BFS pentru grafic și BFS pentru arbore:

Breadth-First Traversal (BFS) pentru un grafic este similar cu Lățimea-Prima traversare a unui copac .

Singura captură aici este că, spre deosebire de copaci , grafice poate conține cicluri, așa că putem ajunge din nou la același nod. Pentru a evita procesarea unui nod de mai multe ori, împărțim vârfurile în două categorii:

• Vizitat și
• Nu a fost vizitat.

O matrice booleană vizitată este folosită pentru a marca vârfurile vizitate. Pentru simplitate, se presupune că toate vârfurile sunt accesibile de la vârful de pornire. BFS utilizări A Breadth First Search (BFS) pentru un algoritm grafic:

Să discutăm despre algoritmul pentru BFS:

1. Inițializare: Puneți în coadă nodul de pornire într-o coadă și marcați-l ca vizitat.
2. Explorare: În timp ce coada nu este goală:
   • Scoateți din coadă un nod din coadă și vizitați-l (de exemplu, imprimați-i valoarea).
   • Pentru fiecare vecin nevizitat al nodului scos din coadă:
     • Pune vecinul în coadă.
     • Marcați vecinul ca vizitat.
3. Încetare: Repetați pasul 2 până când coada este goală.

Acest algoritm asigură că toate nodurile din grafic sunt vizitate în primul rând, începând de la nodul de pornire.

Cum funcționează algoritmul BFS?

Pornind de la rădăcină, toate nodurile de la un anumit nivel sunt vizitate mai întâi și apoi nodurile de la nivelul următor sunt parcurse până când toate nodurile sunt vizitate.

Pentru a face acest lucru este folosită o coadă. Toate nodurile adiacente nevizitate ale nivelului curent sunt împinse în coadă, iar nodurile nivelului curent sunt marcate ca vizitate și scoase din coadă.

elimina ultimul caracter din șir

Ilustrare:

Să înțelegem funcționarea algoritmului cu ajutorul exemplului următor.

Pasul 1: Inițial, coada și matricele vizitate sunt goale.

Coada și matricele vizitate sunt goale inițial.

Pasul 2: Împingeți nodul 0 în coadă și marcați-l ca vizitat.

Împingeți nodul 0 în coadă și marcați-l ca vizitat.

Pasul 3: Scoateți nodul 0 din partea din față a cozii și vizitați vecinii nevizitați și împingeți-i în coadă.

Scoateți nodul 0 din partea din față a cozii și vizitați vecinii nevizitați și introduceți în coadă.

Pasul 4: Scoateți nodul 1 din partea din față a cozii și vizitați vecinii nevizitați și împingeți-i în coadă.

Scoateți nodul 1 din partea din față a cozii și vizitați vecinii nevizitați și împingeți

Pasul 5: Scoateți nodul 2 din partea din față a cozii și vizitați vecinii nevizitați și împingeți-i în coadă.

Scoateți nodul 2 din partea din față a cozii și vizitați vecinii nevizitați și împingeți-i în coadă.

Pasul 6: Scoateți nodul 3 din partea din față a cozii și vizitați vecinii nevizitați și împingeți-i în coadă.
După cum putem vedea că fiecare vecin al nodului 3 este vizitat, deci treceți la următorul nod care se află în fața cozii.

dimensiune font latex

Scoateți nodul 3 din partea din față a cozii și vizitați vecinii nevizitați și împingeți-i în coadă.

Pașii 7: Scoateți nodul 4 din partea din față a cozii și vizitați vecinii nevizitați și împingeți-i în coadă.
După cum putem vedea că fiecare vecin al nodului 4 este vizitat, deci treceți la următorul nod care se află în fața cozii.

Scoateți nodul 4 din partea din față a cozii și vizitați vecinii nevizitați și împingeți-i în coadă.

Acum, coada devine goală, deci, încheiați acest proces de iterație.

Implementarea BFS pentru grafic folosind Lista de adiacență:

#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 & vizitat) { // Creați o coadă pentru coada BFS q;  // Marcați nodul curent ca vizitat și puneți-l în coadă [startNode] = true;  q.push(startNode);  // Iterați peste coadă while (!q.empty()) { // Scoateți din coadă un vârf din coadă și imprimați-l 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() { // Numărul de vârfuri din grafic int vârfuri = 5;  // Reprezentarea listei de adiacență a vectorului grafic> adjList(vertice);  // Adăugați muchii la grafic addEdge(adjList, 0, 1);  addEdge(adjList, 0, 2);  addEdge(adjList, 1, 3);  addEdge(adjList, 1, 4);  addEdge(adjList, 2, 4);  // Marcați toate nodurile ca fiind vector nevizitat vizitat(vertice, false);  // Efectuați traversarea BFS pornind de la vârful 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->date = date;  newNode->next = NULL;  return newNode; } // Funcție de adăugare a unei margini la grafic void addEdge(struct Node* adjList[], int u, int v) { struct Node* newNode = createNode(v);  newNode->next = adjList[u];  adjList[u] = newNode; } // Funcție pentru a efectua căutarea în lățimea întâi pe un grafic // reprezentată folosind lista de adiacență void bfs(struct Node* adjList[], int vertices, int startNode, int visited[]) { // Creați o coadă pentru BFS int queue[ MAX_VERTICE];  int fata = 0, spate = 0;  // Marcați nodul curent ca vizitat și puneți-l în coadă [startNode] = 1;  coada[spate++] = startNode;  // Iterați peste coadă while (front != rear) { // Scoateți un vârf din coadă și imprimați-l int currentNode = coada[front++];  printf('%d', currentNode);  // Obține toate nodurile adiacente ale vârfului scos din coadă // currentNode Dacă un adiacent nu a fost vizitat, // apoi marcați-l vizitat și puneți-l în coadă struct Node* temp = adjList[currentNode];  while (temp != NULL) { int vecin = temp->data;  if (!visited[neighbor]) { vizitat[neighbor] = 1;  coada[spate++] = vecin;  } temp = temp->next;  } } } int main() { // Numărul de vârfuri din grafic int vârfuri = 5;  // Reprezentarea listei de adiacență a structurii graf Node* adjList[vertices];  pentru (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') Graph(int vertices) { this.vertices = vertices;  adjList = new LinkedList[vertices];  pentru (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 coada = new LinkedList();  boolean[] vizitat = boolean nou[vertice];  // Marcați nodul curent ca vizitat și puneți-l în coadă [startNode] = true;  queue.add(startNode);  // Iterează peste coadă în timp ce (!queue.isEmpty()) { // Scoateți un vârf din coadă și îl imprimați int currentNode = queue.poll();  System.out.print(currentNode + ' ');  // Obține toate nodurile adiacente ale nodului curent scos din coadă // Dacă un adiacent nu a fost // vizitat, atunci marcați-l vizitat și // puneți-l în coadă pentru (int vecin : adjList[currentNode]) { if (!visited[neighbor] ) { vizitat[vecin] = adevărat;  queue.add(vecin);  } } } } } public class Main { public static void main(String[] args) { // Numărul de vârfuri din grafic int noduri = 5;  // Crearea unui grafic Graph graph = new Graph(vertices);  // Adăugați muchii la graficul graph.addEdge(0, 1);  graph.addEdge(0, 2);  graph.addEdge(1, 3);  graph.addEdge(1, 4);  graph.addEdge(2, 4);  // Efectuați traversarea BFS pornind de la vârful 0 System.out.print( 'Breadth First Traversal începând de la vârful 0: ');  graph.bfs(0);  } }>>>Python3

using System; using System.Collections.Generic; // Class to represent a graph using adjacency list class Graph {  int vertices;  List [] adjList;  public Graph(int vertices) { this.vertices = vertices;  adjList = Listă nouă [ vârfuri ];  pentru (int i = 0; i< vertices; ++i)  adjList[i] = new List ();  } // Funcție de adăugare a unei muchii la grafic public void AddEdge(int u, int v) { adjList[u].Add(v); } // Funcție pentru a efectua căutarea pe lățime pe un grafic // reprezentată folosind lista de adiacență public void BFS(int startNode) { // Creați o coadă pentru coada BFS coadă = coadă nouă ();  bool[] vizitat = new bool[vertices];  // Marcați nodul curent ca vizitat și puneți-l în coadă [startNode] = true;  queue.Enqueue(startNode);  // Iterați peste coadă while (queue.Count != 0) { // Scoateți un vârf din coadă și îl imprimați int currentNode = queue.Dequeue();  Console.Write(currentNode + ' ');  // Obține toate nodurile adiacente ale nodului curent scos din coadă // Dacă un adiacent nu a fost // vizitat, atunci marcați-l vizitat și // puneți-l în coadă foreach(int vecin în adjList[currentNode]) { if (!visited[neighbor] ) { vizitat[vecin] = adevărat;  coada.Coda de coada(vecin);  } } } } } class MainClass { public static void Main(string[] args) { // Numărul de vârfuri din grafic int noduri = 5;  // Crearea unui grafic Graph graph = new Graph(vertices);  // Adăugați muchii la graficul grafic.AddEdge(0, 1);  graph.AddEdge(0, 2);  graph.AddEdge(1, 3);  graph.AddEdge(1, 4);  graph.AddEdge(2, 4);  // Efectuați traversarea BFS pornind de la vârful 0 Consola.Write( 'Breadth First Traversal începând de la vârful 0: ');  grafic.BFS(0);  } }>>>Javascript

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

Complexitatea timpului: O(V+E), unde V este numărul de noduri și E este numărul de muchii.
Spațiu auxiliar: O(V)

Analiza complexității algoritmului Breadth-First Search (BFS):

Complexitatea timpului a algoritmului BFS: O(V + E)

• BFS explorează toate vârfurile și muchiile din grafic. În cel mai rău caz, vizitează fiecare vârf și margine o dată. Prin urmare, complexitatea de timp a BFS este O(V + E), unde V și E sunt numărul de vârfuri și muchii din graficul dat.

Complexitatea spațială a algoritmului BFS: O(V)

• BFS folosește o coadă pentru a ține evidența vârfurilor care trebuie vizitate. În cel mai rău caz, coada poate conține toate vârfurile din grafic. Prin urmare, complexitatea spațială a BFS este O(V), unde V și E sunt numărul de vârfuri și muchii din graficul dat.

Aplicații ale BFS în grafice:

BFS are diverse aplicații în teoria graficelor și informatică, inclusiv:

• Găsirea celei mai scurte căi: BFS poate fi folosit pentru a găsi calea cea mai scurtă între două noduri într-un grafic neponderat. Urmând evidența părintelui fiecărui nod în timpul traversării, cea mai scurtă cale poate fi reconstruită.
• Detectarea ciclului: BFS poate fi folosit pentru a detecta ciclurile într-un grafic. Dacă un nod este vizitat de două ori în timpul traversării, acesta indică prezența unui ciclu.
• Componente conectate: BFS poate fi folosit pentru a identifica componentele conectate într-un grafic. Fiecare componentă conectată este un set de noduri la care se poate ajunge unul de la celălalt.
• Sortare topologică: BFS poate fi utilizat pentru a efectua sortarea topologică pe un graf aciclic direcționat (DAG). Sortarea topologică aranjează nodurile într-o ordine liniară astfel încât pentru orice muchie (u, v), u apare înaintea v în ordine.
• Traversarea ordinului de nivel a arborilor binari: BFS poate fi folosit pentru a efectua o traversare în ordine de nivel a unui arbore binar. Această traversare vizitează toate nodurile de la același nivel înainte de a trece la nivelul următor.
• Rutare în rețea: BFS poate fi folosit pentru a găsi cea mai scurtă cale între două noduri dintr-o rețea, ceea ce îl face util pentru rutarea pachetelor de date în protocoalele de rețea.

Probleme la Breadth First Search sau BFS pentru un grafic:

Întrebări frecvente despre Breadth First Search (BFS) pentru un grafic:

Intrebarea 1: Ce este BFS și cum funcționează?

Răspuns: BFS este un algoritm de traversare a graficului care explorează sistematic un grafic vizitând toate vârfurile de la un anumit nivel înainte de a trece la nivelul următor. Pornește de la un vârf de pornire, îl pune în coadă într-o coadă și îl marchează ca vizitat. Apoi, scoate un vârf din coadă, îl vizitează și pune în coadă toți vecinii săi nevizitați în coadă. Acest proces continuă până când coada este goală.

Intrebarea 2: Care sunt aplicațiile BFS?

Răspuns: BFS are diverse aplicații, inclusiv găsirea celei mai scurte căi într-un grafic neponderat, detectarea ciclurilor într-un grafic, sortarea topologică a unui grafic aciclic direcționat (DAG), găsirea componentelor conectate într-un grafic și rezolvarea de puzzle-uri precum labirinturi și Sudoku.

Întrebarea 3: Care este complexitatea de timp a BFS?

Răspuns: Complexitatea temporală a BFS este O(V + E), unde V este numărul de vârfuri și E este numărul de muchii din grafic.

matrice în programarea c

Întrebarea 4: Care este complexitatea spațială a BFS?

Răspuns: Complexitatea spațială a BFS este O(V), deoarece folosește o coadă pentru a ține evidența vârfurilor care trebuie vizitate.

Întrebarea 5: Care sunt avantajele utilizării BFS?

Răspuns: BFS este simplu de implementat și eficient pentru a găsi calea cea mai scurtă într-un grafic neponderat. De asemenea, garantează că toate vârfurile din grafic sunt vizitate.

Articole similare:

• Articole recente despre BFS
• Adâncimea prima traversare
• Aplicații ale Breadth First Traversal
• Aplicații ale Depth First Search
• Complexitatea în timp și spațiu a lățimii prima căutare (BFS)