logo

TechCodeview

Breadth First Search alebo BFS pre graf

Breadth First Search (BFS) je základom algoritmus prechodu grafu . Zahŕňa návštevu všetkých pripojených uzlov grafu spôsobom úroveň po úrovni. V tomto článku sa pozrieme na koncept BFS a ako ho možno efektívne aplikovať na grafy

pokladňa pomocou git

Obsah



Breadth First Search (BFS) pre graf:

Breadth First Search (BFS) je algoritmus prechodu grafu, ktorý skúma všetky vrcholy v grafe v aktuálnej hĺbke pred prechodom na vrcholy na ďalšej úrovni hĺbky. Začína v určenom vrchole a navštevuje všetkých svojich susedov a potom prejde na ďalšiu úroveň susedov. BFS sa bežne používa v algoritmoch na hľadanie ciest, pripojených komponentov a problémov s najkratšou cestou v grafoch.

Vzťah medzi BFS pre graf a BFS pre strom:

Breadth-First Traversal (BFS) pre graf je podobný Prechod stromu do šírky .

Jediným háčikom je, že na rozdiel stromy , grafov môže obsahovať cykly, takže sa môžeme opäť dostať do toho istého uzla. Aby sme sa vyhli spracovaniu uzla viac ako raz, rozdeľujeme vrcholy do dvoch kategórií:



  • Navštívil a
  • Nenavštívené.

Na označenie navštívených vrcholov sa používa boolovské navštívené pole. Pre jednoduchosť sa predpokladá, že všetky vrcholy sú dosiahnuteľné z počiatočného vrcholu. BFS používa a Breadth First Search (BFS) pre grafový algoritmus:

Poďme diskutovať o algoritme pre BFS:

  1. Inicializácia: Zaraďte počiatočný uzol do frontu a označte ho ako navštívený.
  2. Prieskum: Kým rad nie je prázdny:
    • Vyraďte uzol z frontu a navštívte ho (napr. vytlačte jeho hodnotu).
    • Pre každého nenavštíveného suseda vyradeného uzla:
      • Zaraďte suseda do frontu.
      • Označte suseda ako navštíveného.
  3. Ukončenie: Opakujte krok 2, kým nebude front prázdny.

Tento algoritmus zaisťuje, že všetky uzly v grafe sú navštívené v šírke, začínajúc od počiatočného uzla.



Ako funguje algoritmus BFS?

Počnúc od koreňa sa najprv navštívia všetky uzly na určitej úrovni a potom sa prejdú uzly ďalšej úrovne, až kým sa nenavštívia všetky uzly.

Na tento účel sa používa rad. Všetky susedné nenavštívené uzly aktuálnej úrovne sa zaradia do frontu a uzly aktuálnej úrovne sa označia ako navštívené a vypustené z frontu.

Ilustrácia:

Poďme pochopiť fungovanie algoritmu pomocou nasledujúceho príkladu.

Krok 1: Na začiatku sú front a navštívené polia prázdne.

Front a navštívené polia sú spočiatku prázdne.

Krok 2: Zaradiť uzol 0 do fronty a označiť ho ako navštívený.

Zaradiť uzol 0 do fronty a označiť ho ako navštívený.

Zaradiť uzol 0 do fronty a označiť ho ako navštívený.

Krok 3: Odstráňte uzol 0 z prednej časti frontu a navštívte nenavštívených susedov a zaraďte ich do frontu.

Odstráňte uzol 0 z prednej časti frontu a navštívili nenavštívených susedov a zatlačte do frontu.

Odstráňte uzol 0 z prednej časti frontu a navštívili nenavštívených susedov a zatlačte do frontu.

Krok 4: Odstráňte uzol 1 z prednej časti frontu a navštívte nenavštívených susedov a zaraďte ich do frontu.

Odstráňte uzol 1 z prednej časti frontu a navštívili nenavštívených susedov a zatlačte

Odstráňte uzol 1 z prednej časti frontu a navštívili nenavštívených susedov a zatlačte

Krok 5: Odstráňte uzol 2 z prednej časti frontu a navštívte nenavštívených susedov a zatlačte ich do frontu.

Odstráňte uzol 2 z prednej časti frontu a navštívte nenavštívených susedov a zatlačte ich do frontu.

Odstráňte uzol 2 z prednej časti frontu a navštívte nenavštívených susedov a zatlačte ich do frontu.

Krok 6: Odstráňte uzol 3 z prednej časti frontu a navštívte nenavštívených susedov a zatlačte ich do frontu.
Ako vidíme, že sú navštívení všetci susedia uzla 3, prejdite na ďalší uzol, ktorý je v prednej časti frontu.

nginx
Odstráňte uzol 3 z prednej časti frontu a navštívte nenavštívených susedov a zatlačte ich do frontu.

Odstráňte uzol 3 z prednej časti frontu a navštívte nenavštívených susedov a zatlačte ich do frontu.

Kroky 7: Odstráňte uzol 4 z prednej časti frontu a navštívte nenavštívených susedov a zaraďte ich do frontu.
Ako vidíme, že sú navštívení všetci susedia uzla 4, prejdite na ďalší uzol, ktorý je v prednej časti frontu.

Odstráňte uzol 4 z prednej časti frontu a navštívte nenavštívených susedov a zatlačte ich do frontu.

Odstráňte uzol 4 z prednej časti frontu a navštívte nenavštívených susedov a zaraďte ich do frontu.

Teraz sa front vyprázdni, takže ukončite tento proces opakovania.

zablokované kontakty

Implementácia BFS pre Graph pomocou zoznamu susediacich krajín:

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, vector & navštívené) { // Vytvorenie frontu pre front BFS q;  // Označiť aktuálny uzol ako navštívený a zaradiť ho do frontu[startNode] = true;  q.push(startNode);  // Iterácia cez front while (!q.empty()) { // Dequeue vrchol z frontu a vytlačí ho 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() { // Počet vrcholov v grafe int vrcholov = 5;  // Reprezentácia zoznamu susediacich vektorov grafu> adjList(vertices);  // Pridanie hrán do grafu addEdge(adjList, 0, 1);  addEdge(adjList, 0, 2);  addEdge(adjList, 1, 3);  addEdge(adjList, 1, 4);  addEdge(adjList, 2, 4);  // Označte všetky vrcholy ako nenavštívený vektor navštívené(vrcholy, nepravda);  // Vykonajte prechod BFS od vrcholu 0 cout<< 'Breadth First Traversal starting from vertex '  '0: ';  bfs(adjList, 0, visited);  return 0; }>
C 
#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->dáta = dáta;  newNode->next = NULL;  return newNode; } // Funkcia na pridanie hrany do grafu void addEdge(struct Node* adjList[], int u, int v) { struct Node* newNode = createNode(v);  newNode->next = adjList[u];  adjList[u] = newNode; } // Funkcia na vykonanie šírky prvého vyhľadávania v grafe // reprezentovanom pomocou zoznamu susediacich void bfs(struct Node* adjList[], int vertices, int startNode, int visited[]) { // Vytvorenie frontu pre BFS int queue[ MAX_VERTICES];  vnútorné predné = 0, zadné = 0;  // Označiť aktuálny uzol ako navštívený a zaradiť ho do frontu[startNode] = 1;  fronta[zadny++] = startNode;  // Iterácia cez front while (front != zadný) { // Dequeue a vertex from queue and print it int currentNode = queue[front++];  printf('%d ', aktuálnyUzol);  // Získanie všetkých susedných vrcholov odradeného vrcholu // currentNode Ak susedný uzol nebol navštívený, // potom ho označte ako navštívený a zaraďte ho do frontu struct Node* temp = adjList[currentNode];  while (temp != NULL) { int sused = temp->data;  if (!navštívil[sused]) { navštívil[sused] = 1;  front[zadný++] = sused;  } temp = temp->ďalší;  } } } int main() { // Počet vrcholov v grafe int vrcholov = 5;  // Reprezentácia zoznamu susediacich štruktúr grafu Node* adjList[vertices];  pre (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; }>
Java 
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[vrcholy];  pre (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 fronta = new LinkedList();  boolean[] navštívené = new boolean[vertices];  // Označiť aktuálny uzol ako navštívený a zaradiť ho do frontu[startNode] = true;  queue.add(startNode);  // Iterácia frontu while (!queue.isEmpty()) { // Vyradí vrchol z frontu a vytlačí ho int currentNode = queue.poll();  System.out.print(currentNode + ' ');  // Získanie všetkých susedných vrcholov vyradeného // vrcholu currentNode Ak sused // nebol navštívený, potom ho označte ako navštívený a // zaraďte ho do frontu pre (int sused : adjList[currentNode]) { if (!visited[neighbor] ) { navštívený[sused] = true;  queue.add(neighbor);  } } } } } public class Main { public static void main(String[] args) { // Počet vrcholov v grafe int vertices = 5;  // Vytvorenie grafu Graf grafu = new Graph(vertices);  // Pridanie hrán do grafu graph.addEdge(0, 1);  graph.addEdge(0, 2);  graph.addEdge(1, 3);  graph.addEdge(1, 4);  graph.addEdge(2, 4);  // Vykonanie prechodu BFS počnúc vrcholom 0 System.out.print( 'Breadth First Traversal od vrcholu 0: ');  graf.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()>
C# 
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 = nový zoznam [ vrcholy ];  pre (int i = 0; i< vertices; ++i)  adjList[i] = new List ();  } // Funkcia na pridanie hrany do grafu public void AddEdge(int u, int v) { adjList[u].Add(v); } // Funkcia na vykonanie šírky prvého vyhľadávania na grafe // reprezentovaná pomocou zoznamu susedných vzťahov public void BFS(int startNode) { // Vytvorenie frontu pre BFS Queue front = nový front ();  bool[] navštívené = nové bool[vrcholy];  // Označiť aktuálny uzol ako navštívený a zaradiť ho do frontu[startNode] = true;  queue.Enqueue(startNode);  // Iterácia cez front while (queue.Count != 0) { // Vyradí vrchol z frontu a vytlačí ho int currentNode = queue.Dequeue();  Console.Write(currentNode + ' ');  // Získanie všetkých susedných vrcholov vyradeného // vrchola currentNode Ak sused // nebol navštívený, potom ho označte ako navštívený a // zaraďte ho do frontu (int sused v adjList[currentNode]) { if (!visited[neighbor] ) { navštívený[sused] = true;  fronta.Enqueue(sused);  } } } } } class MainClass { public static void Main(string[] args) { // Počet vrcholov v grafe int vertices = 5;  // Vytvorenie grafu Graf grafu = new Graph(vertices);  // Pridanie hrán do grafu grafu.AddEdge(0, 1);  graph.AddEdge(0, 2);  graph.AddEdge(1, 3);  graph.AddEdge(1, 4);  graph.AddEdge(2, 4);  // Vykonanie prechodu BFS počnúc vrcholom 0 Console.Write( 'Breadth First Traversal od vrcholu 0: ');  graf.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);>
Výkon 
Breadth First Traversal starting from vertex 0: 0 1 2 3 4>

Časová zložitosť: O(V+E), kde V je počet uzlov a E je počet hrán.
Pomocný priestor: O(V)

Analýza zložitosti algoritmu BFS (Breadth-First Search):

Časová zložitosť algoritmu BFS: O(V + E)

  • BFS skúma všetky vrcholy a hrany v grafe. V horšom prípade navštívi každý vrchol a hranu raz. Časová zložitosť BFS je teda O(V + E), kde V a E je počet vrcholov a hrán v danom grafe.

Priestorová zložitosť algoritmu BFS: O(V)

  • BFS používa front na sledovanie vrcholov, ktoré je potrebné navštíviť. V najhoršom prípade môže front obsahovať všetky vrcholy v grafe. Priestorová zložitosť BFS je teda O(V), kde V a E sú počty vrcholov a hrán v danom grafe.

Aplikácie BFS v grafoch:

BFS má rôzne aplikácie v teórii grafov a počítačovej vede, vrátane:

  • Hľadanie najkratšej cesty: BFS možno použiť na nájdenie najkratšej cesty medzi dvoma uzlami v neváženom grafe. Sledovaním rodiča každého uzla počas prechodu je možné rekonštruovať najkratšiu cestu.
  • Detekcia cyklu: BFS možno použiť na detekciu cyklov v grafe. Ak sa uzol navštívi dvakrát počas prechodu, indikuje to prítomnosť cyklu.
  • Pripojené komponenty: BFS možno použiť na identifikáciu pripojených komponentov v grafe. Každý pripojený komponent je množina uzlov, ktoré sa dajú dosiahnuť jeden od druhého.
  • Topologické triedenie: BFS možno použiť na vykonávanie topologického triedenia na orientovanom acyklickom grafe (DAG). Topologické triedenie usporiada uzly v lineárnom poradí tak, že pre akúkoľvek hranu (u, v) sa u objaví v poradí pred v.
  • Prechod binárnych stromov podľa poradia úrovní: BFS možno použiť na vykonanie prechodu binárneho stromu podľa poradia úrovne. Toto prechádzanie navštívi všetky uzly na rovnakej úrovni pred prechodom na ďalšiu úroveň.
  • Smerovanie siete: BFS možno použiť na nájdenie najkratšej cesty medzi dvoma uzlami v sieti, čo je užitočné na smerovanie dátových paketov v sieťových protokoloch.

Problémy pri prvom vyhľadávaní šírky alebo BFS pre graf:

Áno nie

Problémy

Prax
1. Nájdite úroveň daného uzla v neorientovanom grafe Odkaz
2. Minimalizujte maximálny susedný rozdiel v ceste z ľavého horného rohu do pravého dolného rohu Odkaz
10. Skontrolujte, či je cieľ danej matice dosiahnuteľný s požadovanými hodnotami buniek Odkaz

Často kladené otázky o šírke prvého vyhľadávania (BFS) pre graf:

Otázka 1: Čo je BFS a ako funguje?

odpoveď: BFS je algoritmus prechodu grafu, ktorý systematicky skúma graf navštívením všetkých vrcholov na danej úrovni pred prechodom na ďalšiu úroveň. Začne od počiatočného vrcholu, zaradí ho do frontu a označí ho ako navštívený. Potom vyradí vrchol z frontu, navštívi ho a zaradí všetkých jeho nenavštívených susedov do frontu. Tento proces pokračuje, kým sa front nevyprázdni.

Otázka 2: Aké sú aplikácie BFS?

odpoveď: BFS má rôzne aplikácie, vrátane hľadania najkratšej cesty v neváženom grafe, detekcie cyklov v grafe, topologického triedenia orientovaného acyklického grafu (DAG), hľadania spojených komponentov v grafe a riešenia hádaniek, ako sú bludisko a sudoku.

Otázka 3: Aká je časová zložitosť BFS?

odpoveď: Časová zložitosť BFS je O(V + E), kde V je počet vrcholov a E je počet hrán v grafe.

Otázka 4: Aká je vesmírna zložitosť BFS?

odpoveď: Priestorová zložitosť BFS je O(V), pretože používa front na sledovanie vrcholov, ktoré je potrebné navštíviť.

Otázka 5: Aké sú výhody používania BFS?

odpoveď: BFS sa jednoducho implementuje a je efektívny na nájdenie najkratšej cesty v neváženom grafe. Tiež zaručuje, že sú navštívené všetky vrcholy v grafe.

Súvisiace články:

  • Najnovšie články o BFS
  • Prvý prechod do hĺbky
  • Aplikácie Breadth First Traversal
  • Aplikácie hĺbkového prvého vyhľadávania
  • Časová a priestorová zložitosť prvého vyhľadávania šírky (BFS)