logo

TechCodeview

Breedte eerst zoeken of BFS voor een grafiek

Breedte eerste zoekopdracht (BFS) is een fundamenteel algoritme voor het doorlopen van grafieken . Het houdt in dat u alle verbonden knooppunten van een grafiek niveau voor niveau bezoekt. In dit artikel gaan we dieper in op het concept van BFS en hoe het effectief op grafieken kan worden toegepast

Inhoudsopgave



Breedte eerste zoekopdracht (BFS) voor een grafiek:

Breedte eerste zoekopdracht (BFS) is een grafiekdoorloopalgoritme dat alle hoekpunten in een grafiek op de huidige diepte onderzoekt voordat naar de hoekpunten op het volgende diepteniveau wordt gegaan. Het begint bij een bepaald hoekpunt en bezoekt al zijn buren voordat het doorgaat naar het volgende niveau van buren. BFS wordt vaak gebruikt in algoritmen voor het vinden van paden, verbonden componenten en kortste-padproblemen in grafieken.

Relatie tussen BFS voor grafiek en BFS voor boom:

Breadth-First Traversal (BFS) voor een grafiek is vergelijkbaar met de Breedte-eerste doorgang van een boom .

De enige vangst hier is dat, in tegenstelling tot bomen , grafieken kan cycli bevatten, dus het kan zijn dat we weer op hetzelfde knooppunt terechtkomen. Om te voorkomen dat een knooppunt meerdere keren wordt verwerkt, verdelen we de hoekpunten in twee categorieën:



  • Bezocht en
  • Niet bezocht.

Een Booleaanse bezochte array wordt gebruikt om de bezochte hoekpunten te markeren. Voor de eenvoud wordt aangenomen dat alle hoekpunten bereikbaar zijn vanaf het startpunt. BFS toepassingen A Breadth First Search (BFS) voor een grafiekalgoritme:

Laten we het algoritme voor de BFS bespreken:

  1. Initialisatie: Plaats het startknooppunt in een wachtrij en markeer het als bezocht.
  2. Verkenning: Zolang de wachtrij niet leeg is:
    • Haal een knooppunt uit de wachtrij en bezoek het (druk bijvoorbeeld de waarde ervan af).
    • Voor elke niet-bezochte buur van het uit de wachtrij geplaatste knooppunt:
      • Zet de buurman in de rij.
      • Markeer de buurman als bezocht.
  3. Beëindiging: Herhaal stap 2 totdat de wachtrij leeg is.

Dit algoritme zorgt ervoor dat alle knooppunten in de grafiek eerst in de breedte worden bezocht, beginnend bij het startknooppunt.



Hoe werkt het BFS-algoritme?

Beginnend bij de wortel worden eerst alle knooppunten op een bepaald niveau bezocht en vervolgens worden de knooppunten van het volgende niveau doorlopen totdat alle knooppunten zijn bezocht.

Hiervoor wordt gebruik gemaakt van een wachtrij. Alle aangrenzende niet-bezochte knooppunten van het huidige niveau worden in de wachtrij geplaatst en de knooppunten van het huidige niveau worden gemarkeerd als bezocht en uit de wachtrij verwijderd.

Illustratie:

Laten we de werking van het algoritme begrijpen met behulp van het volgende voorbeeld.

Stap 1: Aanvankelijk zijn de wachtrij en bezochte arrays leeg.

hoe het script in Linux uit te voeren

Wachtrij en bezochte arrays zijn aanvankelijk leeg.

Stap 2: Duw knooppunt 0 in de wachtrij en markeer het als bezocht.

Duw knooppunt 0 in de wachtrij en markeer het als bezocht.

Duw knooppunt 0 in de wachtrij en markeer het als bezocht.

Stap 3: Verwijder knooppunt 0 van de voorkant van de wachtrij en bezoek de niet-bezochte buren en duw ze in de wachtrij.

Verwijder knooppunt 0 van de voorkant van de wachtrij, bezoek de niet-bezochte buren en schuif in de wachtrij.

Verwijder knooppunt 0 van de voorkant van de wachtrij, bezoek de niet-bezochte buren en schuif in de wachtrij.

Stap 4: Verwijder knooppunt 1 van de voorkant van de wachtrij en bezoek de niet-bezochte buren en duw ze in de wachtrij.

Verwijder knooppunt 1 van de voorkant van de wachtrij, bezoek de niet-bezochte buren en duw

Verwijder knooppunt 1 van de voorkant van de wachtrij, bezoek de niet-bezochte buren en duw

Stap 5: Verwijder knooppunt 2 van de voorkant van de wachtrij en bezoek de niet bezochte buren en duw ze in de wachtrij.

Verwijder knooppunt 2 van de voorkant van de wachtrij en bezoek de niet-bezochte buren en duw ze in de wachtrij.

Verwijder knooppunt 2 van de voorkant van de wachtrij en bezoek de niet bezochte buren en duw ze in de wachtrij.

Stap 6: Verwijder knooppunt 3 van de voorkant van de wachtrij en bezoek de niet-bezochte buren en duw ze in de wachtrij.
Omdat we kunnen zien dat alle buren van knooppunt 3 worden bezocht, ga je naar het volgende knooppunt dat vooraan in de wachtrij staat.

Verwijder knooppunt 3 van de voorkant van de wachtrij en bezoek de niet-bezochte buren en duw ze in de wachtrij.

Verwijder knooppunt 3 van de voorkant van de wachtrij en bezoek de niet-bezochte buren en duw ze in de wachtrij.

Stappen 7: Verwijder knooppunt 4 van de voorkant van de wachtrij en bezoek de niet bezochte buren en duw ze in de wachtrij.
Omdat we kunnen zien dat alle buren van knooppunt 4 worden bezocht, ga je naar het volgende knooppunt dat vooraan in de wachtrij staat.

Verwijder knooppunt 4 van de voorkant van de wachtrij en bezoek de niet bezochte buren en duw ze in de wachtrij.

Verwijder knooppunt 4 van de voorkant van de wachtrij en bezoek de niet bezochte buren en duw ze in de wachtrij.

Nu wordt de wachtrij leeg. Beëindig dus dit iteratieproces.

Implementatie van BFS voor Graph met behulp van de aangrenzende lijst:

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 & bezocht) {// Maak een wachtrij voor de BFS-wachtrij Q;  // Markeer het huidige knooppunt als bezocht en plaats het in de wachtrij bezocht[startNode] = true;  q.push(startknooppunt);  // Herhaal de wachtrij terwijl (!q.empty()) {// Haal een hoekpunt uit de wachtrij en druk het af int currentNode = q.front();  q.pop();  uit<< 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() {// Aantal hoekpunten in de grafiek int hoekpunten = 5;  // Aangrenzende lijstweergave van de grafiekvector> adjList(hoekpunten);  // Voeg randen toe aan de grafiek addEdge(adjList, 0, 1);  addEdge(adjLijst, 0, 2);  addEdge(adjLijst, 1, 3);  addEdge(adjLijst, 1, 4);  addEdge(adjLijst, 2, 4);  // Markeer alle hoekpunten als niet bezochte vector bezocht(hoekpunten, false);  // Voer BFS-traversal uit vanaf hoekpunt 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->gegevens = gegevens;  newNode->volgende = NULL;  retourneer newNode; } // Functie om een ​​rand aan de grafiek toe te voegen void addEdge(struct Node* adjList[], int u, int v) { struct Node* newNode = createNode(v);  newNode->volgende = adjList[u];  adjList[u] = newNode; } // Functie om Breadth First Search uit te voeren in een grafiek // weergegeven met behulp van de aangrenzende lijst void bfs(struct Node* adjList[], int hoekpunten, int startNode, int visit[]) {// Maak een wachtrij voor BFS int wachtrij[ MAX_VERTICES];  int voorkant = 0, achterkant = 0;  // Markeer het huidige knooppunt als bezocht en plaats het bezocht[startNode] = 1;  wachtrij[achter++] = startknooppunt;  // Herhaal de wachtrij terwijl (voorkant!= achterkant) {// Haal een hoekpunt uit de wachtrij en druk het af int currentNode = wachtrij[voor++];  printf('%d', currentNode);  // Haal alle aangrenzende hoekpunten op van het uit de wachtrij gehaalde hoekpunt // currentNode Als een aangrenzend punt nog niet is bezocht, // markeer het dan als bezocht en plaats het in de wachtrij struct Node* temp = adjList[currentNode];  while (temp != NULL) { int buur = temp->data;  if (! bezocht [buurman]) { bezocht [buurman] = 1;  wachtrij[achter++] = buurman;  } temp = temp->volgende;  } } } int main() {// Aantal hoekpunten in de grafiek int hoekpunten = 5;  // Aangrenzende lijstweergave van de grafiekstructuur Node* adjList[vertices];  voor (int i = 0; ik< 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 [] adjLijst;  @SuppressWarnings('unchecked') Grafiek(int hoekpunten) { this.vertices = hoekpunten;  adjList = nieuwe LinkedList[hoekpunten];  voor (int i = 0; ik< 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 wachtrij = nieuwe LinkedList();  boolean[] bezocht = nieuwe boolean[hoekpunten];  // Markeer het huidige knooppunt als bezocht en plaats het in de wachtrij bezocht[startNode] = true;  wachtrij.add(startknooppunt);  // Herhaal de wachtrij terwijl (!queue.isEmpty()) {// Haal een hoekpunt uit de wachtrij en druk het af int currentNode = wachtrij.poll();  Systeem.out.print(currentNode + '');  // Haal alle aangrenzende hoekpunten op van de uit de wachtrij verwijderde // vertex currentNode Als een aangrenzend niet // is bezocht, markeer het dan als bezocht en // zet het in de wachtrij voor (int buur: adjList[currentNode]) { if (!visited[neighbor] ) { bezocht[buurman] = waar;  wachtrij.add(buur);  } } } } } public class Main { public static void main(String[] args) {// Aantal hoekpunten in de grafiek int hoekpunten = 5;  // Maak een grafiek Grafiekgrafiek = nieuwe grafiek (hoekpunten);  // Voeg randen toe aan de grafiek graph.addEdge(0, 1);  grafiek.addEdge(0, 2);  grafiek.addEdge(1, 3);  grafiek.addEdge(1, 4);  grafiek.addEdge(2, 4);  // Voer BFS-traversal uit vanaf hoekpunt 0 System.out.print( 'Breadth First Traversal vanaf hoekpunt 0: ');  grafiek.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 [] adjLijst;  public Graph(int hoekpunten) { this.vertices = hoekpunten;  adjList = nieuwe lijst [hoekpunten];  voor (int i = 0; ik< vertices; ++i)  adjList[i] = new List ();  } // Functie om een ​​rand toe te voegen aan de grafiek public void AddEdge(int u, int v) { adjList[u].Add(v); } // Functie om Breadth First Search uit te voeren in een grafiek // weergegeven met behulp van de aangrenzende lijst public void BFS(int startNode) {// Maak een wachtrij voor BFS Queue wachtrij = nieuwe wachtrij ();  bool[] bezocht = nieuwe bool[hoekpunten];  // Markeer het huidige knooppunt als bezocht en plaats het in de wachtrij bezocht[startNode] = true;  wachtrij.Enqueue(startNode);  // Herhaal de wachtrij terwijl (queue.Count != 0) {// Haal een hoekpunt uit de wachtrij en druk het af int currentNode = wachtrij.Dequeue();  Console.Write(currentNode + '');  // Haal alle aangrenzende hoekpunten op van de uit de wachtrij verwijderde // vertex currentNode Als een aangrenzende niet // is bezocht, markeer deze dan als bezocht en // plaats deze in de wachtrij foreach(int buur in adjList[currentNode]) { if (!visited[neighbor] ) { bezocht[buurman] = waar;  wachtrij.Enqueue(buur);  } } } } } class MainClass { public static void Main(string[] args) {// Aantal hoekpunten in de grafiek int hoekpunten = 5;  // Maak een grafiek Grafiekgrafiek = nieuwe grafiek (hoekpunten);  // Voeg randen toe aan de grafiekgrafiek.AddEdge(0, 1);  grafiek.AddEdge(0, 2);  grafiek.AddEdge(1, 3);  grafiek.AddEdge(1, 4);  grafiek.AddEdge(2, 4);  // Voer BFS-traversal uit vanaf hoekpunt 0 Console.Write( 'Breadth First Traversal vanaf hoekpunt 0: ');  grafiek.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);>
Uitvoer 
Breadth First Traversal starting from vertex 0: 0 1 2 3 4>

Tijdcomplexiteit: O(V+E), waarbij V het aantal knooppunten is en E het aantal randen.
Hulpruimte: O(V)

Complexiteitsanalyse van het Breadth-First Search (BFS)-algoritme:

Tijdcomplexiteit van BFS-algoritme: O(V + E)

  • BFS onderzoekt alle hoekpunten en randen in de grafiek. In het ergste geval bezoekt het elk hoekpunt en elke rand één keer. Daarom is de tijdscomplexiteit van BFS O(V + E), waarbij V en E het aantal hoekpunten en randen in de gegeven grafiek zijn.

Ruimtecomplexiteit van BFS-algoritme: O(V)

  • BFS gebruikt een wachtrij om bij te houden welke hoekpunten bezocht moeten worden. In het ergste geval kan de wachtrij alle hoekpunten in de grafiek bevatten. Daarom is de ruimtecomplexiteit van BFS O(V), waarbij V en E het aantal hoekpunten en randen in de gegeven grafiek zijn.

Toepassingen van BFS in grafieken:

BFS heeft verschillende toepassingen in de grafentheorie en informatica, waaronder:

  • Kortste pad vinden: BFS kan worden gebruikt om het kortste pad tussen twee knooppunten in een ongewogen grafiek te vinden. Door tijdens het doorlopen de ouder van elk knooppunt bij te houden, kan het kortste pad worden gereconstrueerd.
  • Cyclusdetectie: BFS kan worden gebruikt om cycli in een grafiek te detecteren. Als een knooppunt tijdens de verplaatsing twee keer wordt bezocht, duidt dit op de aanwezigheid van een cyclus.
  • Verbonden componenten: BFS kan worden gebruikt om verbonden componenten in een grafiek te identificeren. Elke verbonden component is een reeks knooppunten die van elkaar kunnen worden bereikt.
  • Topologische sortering: BFS kan worden gebruikt om topologische sortering uit te voeren op een gerichte acyclische grafiek (DAG). Topologische sortering rangschikt de knooppunten in een lineaire volgorde, zodat voor elke rand (u, v) u vóór v in de volgorde verschijnt.
  • Niveauvolgorde door binaire bomen: BFS kan worden gebruikt om een ​​niveauvolgorde door een binaire boom uit te voeren. Deze doorgang bezoekt alle knooppunten op hetzelfde niveau voordat naar het volgende niveau wordt gegaan.
  • Netwerkroutering: BFS kan worden gebruikt om het kortste pad tussen twee knooppunten in een netwerk te vinden, waardoor het nuttig is voor het routeren van datapakketten in netwerkprotocollen.

Problemen met Broadth First Search of BFS voor een grafiek:

Ja nee

Problemen

Oefening
1. Zoek het niveau van een bepaald knooppunt in een ongerichte grafiek Koppeling
2. Minimaliseer het maximale aangrenzende verschil in een pad van linksboven naar rechtsonder Koppeling
10. Controleer of de bestemming van de gegeven matrix bereikbaar is met de vereiste celwaarden Koppeling

Veelgestelde vragen over Breadth First Search (BFS) voor een grafiek:

Vraag 1: Wat is BFS en hoe werkt het?

Antwoord: BFS is een algoritme voor het doorlopen van grafieken dat systematisch een grafiek onderzoekt door alle hoekpunten op een bepaald niveau te bezoeken voordat naar het volgende niveau wordt gegaan. Het begint vanaf een startpunt, plaatst het in een wachtrij en markeert het als bezocht. Vervolgens haalt het een hoekpunt uit de wachtrij, bezoekt het en plaatst al zijn niet-bezochte buren in de wachtrij. Dit proces gaat door totdat de wachtrij leeg is.

Vraag 2: Wat zijn de toepassingen van BFS?

Antwoord: BFS heeft verschillende toepassingen, waaronder het vinden van het kortste pad in een ongewogen grafiek, het detecteren van cycli in een grafiek, het topologisch sorteren van een gerichte acyclische grafiek (DAG), het vinden van verbonden componenten in een grafiek en het oplossen van puzzels zoals doolhoven en Sudoku.

Vraag 3: Wat is de tijdscomplexiteit van BFS?

Antwoord: De tijdscomplexiteit van BFS is O(V + E), waarbij V het aantal hoekpunten is en E het aantal randen in de grafiek.

Vraag 4: Wat is de ruimtecomplexiteit van BFS?

Antwoord: De ruimtecomplexiteit van BFS is O(V), omdat het een wachtrij gebruikt om de hoekpunten bij te houden die bezocht moeten worden.

Vraag 5: Wat zijn de voordelen van het gebruik van BFS?

Antwoord: BFS is eenvoudig te implementeren en efficiënt voor het vinden van het kortste pad in een ongewogen grafiek. Het garandeert ook dat alle hoekpunten in de grafiek worden bezocht.

Gerelateerde artikelen:

  • Recente artikelen over BFS
  • Diepte Eerste Traversal
  • Toepassingen van breedte-eerste traversal
  • Toepassingen van Depth First Search
  • Tijd- en ruimtecomplexiteit van breedte-eerste zoekopdracht (BFS)