logo

TechCodeview

Breitensuche oder BFS für ein Diagramm

Breitensuche (BFS) ist ein Grundprinzip Graph-Traversal-Algorithmus . Dabei werden alle verbundenen Knoten eines Diagramms Ebene für Ebene besucht. In diesem Artikel werden wir uns mit dem Konzept befassen BFS und wie es effektiv auf Diagramme angewendet werden kann

Inhaltsverzeichnis



Breitensuche (BFS) für ein Diagramm:

Breitensuche (BFS) ist ein Graph-Traversal-Algorithmus, der alle Scheitelpunkte in einem Diagramm in der aktuellen Tiefe untersucht, bevor er zu den Scheitelpunkten auf der nächsten Tiefenebene übergeht. Es beginnt an einem bestimmten Scheitelpunkt und besucht alle seine Nachbarn, bevor es zur nächsten Ebene von Nachbarn übergeht. BFS wird häufig in Algorithmen zur Pfadfindung, für Zusammenhangskomponenten und für Probleme mit kürzesten Pfaden in Diagrammen verwendet.

Beziehung zwischen BFS für Graph und BFS für Baum:

Der Breitendurchlauf (BFS) für einen Graphen ähnelt dem Breitenorientierte Durchquerung eines Baumes .

Der einzige Haken hier ist, dass im Gegensatz dazu Bäume , Grafiken kann Zyklen enthalten, sodass wir möglicherweise wieder zum selben Knoten gelangen. Um zu vermeiden, dass ein Knoten mehr als einmal verarbeitet wird, teilen wir die Eckpunkte in zwei Kategorien ein:



  • Besucht und
  • Nicht besucht.

Ein boolesches besuchtes Array wird verwendet, um die besuchten Scheitelpunkte zu markieren. Der Einfachheit halber wird angenommen, dass alle Scheitelpunkte vom Startscheitelpunkt aus erreichbar sind. BFS Verwendet A Breitensuche (BFS) für einen Graphalgorithmus:

Lassen Sie uns den Algorithmus für das BFS diskutieren:

Java-Objekt zu JSON
  1. Initialisierung: Stellen Sie den Startknoten in eine Warteschlange und markieren Sie ihn als besucht.
  2. Erkundung: Während die Warteschlange nicht leer ist:
    • Entfernen Sie einen Knoten aus der Warteschlange und besuchen Sie ihn (z. B. drucken Sie seinen Wert aus).
    • Für jeden nicht besuchten Nachbarn des aus der Warteschlange entfernten Knotens:
      • Den Nachbarn in die Warteschlange einreihen.
      • Markieren Sie den Nachbarn als besucht.
  3. Beendigung: Wiederholen Sie Schritt 2, bis die Warteschlange leer ist.

Dieser Algorithmus stellt sicher, dass alle Knoten im Diagramm in der Breite zuerst besucht werden, beginnend mit dem Startknoten.



Löschen aus einem binären Suchbaum

Wie funktioniert der BFS-Algorithmus?

Ausgehend von der Wurzel werden zuerst alle Knoten auf einer bestimmten Ebene besucht und dann die Knoten der nächsten Ebene durchlaufen, bis alle Knoten besucht sind.

Hierzu wird eine Warteschlange verwendet. Alle benachbarten, nicht besuchten Knoten der aktuellen Ebene werden in die Warteschlange verschoben und die Knoten der aktuellen Ebene werden als besucht markiert und aus der Warteschlange entfernt.

Illustration:

Lassen Sie uns die Funktionsweise des Algorithmus anhand des folgenden Beispiels verstehen.

Schritt 1: Anfänglich sind die Warteschlange und die besuchten Arrays leer.

Warteschlangen- und besuchte Arrays sind zunächst leer.

Schritt 2: Schieben Sie Knoten 0 in die Warteschlange und markieren Sie ihn als besucht.

Schieben Sie Knoten 0 in die Warteschlange und markieren Sie ihn als besucht.

Schieben Sie Knoten 0 in die Warteschlange und markieren Sie ihn als besucht.

Schritt 3: Entfernen Sie Knoten 0 von der Vorderseite der Warteschlange, besuchen Sie die nicht besuchten Nachbarn und schieben Sie sie in die Warteschlange.

Samen vs. Sporen
Entfernen Sie Knoten 0 von der Vorderseite der Warteschlange, besuchen Sie die nicht besuchten Nachbarn und schieben Sie ihn in die Warteschlange.

Entfernen Sie Knoten 0 von der Vorderseite der Warteschlange, besuchen Sie die nicht besuchten Nachbarn und schieben Sie ihn in die Warteschlange.

Schritt 4: Entfernen Sie Knoten 1 von der Vorderseite der Warteschlange, besuchen Sie die nicht besuchten Nachbarn und schieben Sie sie in die Warteschlange.

Entfernen Sie Knoten 1 von der Spitze der Warteschlange, besuchen Sie die nicht besuchten Nachbarn und drücken Sie ihn

Entfernen Sie Knoten 1 von der Spitze der Warteschlange, besuchen Sie die nicht besuchten Nachbarn und drücken Sie ihn

Schritt 5: Entfernen Sie Knoten 2 von der Vorderseite der Warteschlange, besuchen Sie die nicht besuchten Nachbarn und schieben Sie sie in die Warteschlange.

Entfernen Sie Knoten 2 von der Vorderseite der Warteschlange, besuchen Sie die nicht besuchten Nachbarn und schieben Sie sie in die Warteschlange.

Entfernen Sie Knoten 2 von der Vorderseite der Warteschlange, besuchen Sie die nicht besuchten Nachbarn und schieben Sie sie in die Warteschlange.

Schritt 6: Entfernen Sie Knoten 3 von der Vorderseite der Warteschlange, besuchen Sie die nicht besuchten Nachbarn und schieben Sie sie in die Warteschlange.
Da wir sehen können, dass jeder Nachbar von Knoten 3 besucht wird, wechseln Sie zum nächsten Knoten, der sich an der Spitze der Warteschlange befindet.

String in Ganzzahl in Java umwandeln
Entfernen Sie Knoten 3 von der Vorderseite der Warteschlange, besuchen Sie die nicht besuchten Nachbarn und schieben Sie sie in die Warteschlange.

Entfernen Sie Knoten 3 von der Vorderseite der Warteschlange, besuchen Sie die nicht besuchten Nachbarn und schieben Sie sie in die Warteschlange.

Schritte 7: Entfernen Sie Knoten 4 von der Vorderseite der Warteschlange, besuchen Sie die nicht besuchten Nachbarn und schieben Sie sie in die Warteschlange.
Da wir sehen können, dass alle Nachbarn von Knoten 4 besucht werden, wechseln Sie zum nächsten Knoten, der sich an der Spitze der Warteschlange befindet.

Entfernen Sie Knoten 4 von der Vorderseite der Warteschlange, besuchen Sie die nicht besuchten Nachbarn und schieben Sie sie in die Warteschlange.

Entfernen Sie Knoten 4 von der Vorderseite der Warteschlange, besuchen Sie die nicht besuchten Nachbarn und schieben Sie sie in die Warteschlange.

Jetzt ist die Warteschlange leer. Beenden Sie diesen Iterationsprozess.

Implementierung von BFS für Graph mithilfe der Adjazenzliste:

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, Vektor & besucht) { // Erstellen Sie eine Warteschlange für die BFS-Warteschlange Q;  // Den aktuellen Knoten als besucht markieren und in die Warteschlange einreihen besuchte[startNode] = true;  q.push(startNode);  // Durch die Warteschlange iterieren while (!q.empty()) { // Einen Scheitelpunkt aus der Warteschlange entfernen und ausdrucken 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() { // Anzahl der Eckpunkte im Diagramm int vertices = 5;  // Adjazenzlistendarstellung des Diagrammvektors> adjList(vertices);  // Kanten zum Diagramm hinzufügen addEdge(adjList, 0, 1);  addEdge(adjList, 0, 2);  addEdge(adjList, 1, 3);  addEdge(adjList, 1, 4);  addEdge(adjList, 2, 4);  // Alle Eckpunkte als nicht besuchten Vektor markieren besuchte(Vertices, false);  // BFS-Durchquerung ab Scheitelpunkt 0 durchführen 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->Daten = Daten;  newNode->next = NULL;  return newNode; } // Funktion zum Hinzufügen einer Kante zum Diagramm void addEdge(struct Node* adjList[], int u, int v) { struct Node* newNode = createNode(v);  newNode->next = adjList[u];  adjList[u] = newNode; } // Funktion zum Durchführen der Breitensuche in einem Diagramm // dargestellt durch Adjazenzliste void bfs(struct Node* adjList[], int vertices, int startNode, int besuchte[]) { // Erstellen Sie eine Warteschlange für BFS int queue[ MAX_VERTICES];  int vorne = 0, hinten = 0;  // Den aktuellen Knoten als besucht markieren und in die Warteschlange einreihen. besuchte[startNode] = 1;  queue[rear++] = startNode;  // Durch die Warteschlange iterieren while (front != Rear) { // Einen Scheitelpunkt aus der Warteschlange entfernen und ausdrucken int currentNode = queue[front++];  printf('%d ', currentNode);  // Alle benachbarten Scheitelpunkte des aus der Warteschlange entfernten Scheitelpunkts abrufen // currentNode Wenn ein benachbarter Knoten nicht besucht wurde, // dann ihn als besucht markieren und in die Warteschlange einreihen struct Node* temp = adjList[currentNode];  while (temp != NULL) { int neighbour = temp->data;  if (!visited[neighbor]) { besuchte[neighbor] = 1;  queue[rear++] = Nachbar;  } temp = temp->next;  } } } int main() { // Anzahl der Eckpunkte im Diagramm int vertices = 5;  // Adjazenzlistendarstellung des Graphen struct Node* adjList[vertices];  für (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[vertices];  für (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 queue = new LinkedList();  boolean[] besuchte = new boolean[eckpunkte];  // Den aktuellen Knoten als besucht markieren und in die Warteschlange einreihen besuchte[startNode] = true;  queue.add(startNode);  // Durch die Warteschlange iterieren while (!queue.isEmpty()) { // Einen Scheitelpunkt aus der Warteschlange entfernen und ausdrucken int currentNode = queue.poll();  System.out.print(currentNode + ' ');  // Alle benachbarten Scheitelpunkte des // aus der Warteschlange entfernten Scheitelpunkts currentNode abrufen. Wenn ein benachbarter Knoten // nicht besucht wurde, markieren Sie ihn als besucht und // stellen Sie ihn in die Warteschlange für (int neighbor : adjList[currentNode]) { if (!visited[neighbor] ) { besuchte[Nachbar] = true;  queue.add(neighbor);  } } } } } public class Main { public static void main(String[] args) { // Anzahl der Scheitelpunkte im Diagramm int vertices = 5;  // Einen Graphen erstellen Graph graph = new Graph(vertices);  // Kanten zum Diagramm hinzufügen graph.addEdge(0, 1);  graph.addEdge(0, 2);  graph.addEdge(1, 3);  graph.addEdge(1, 4);  graph.addEdge(2, 4);  // BFS-Traversal ab Scheitelpunkt 0 durchführen System.out.print( 'Breadth First Traversal ab Scheitelpunkt 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()>
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 = neue Liste [ Eckpunkte ];  für (int i = 0; i< vertices; ++i)  adjList[i] = new List ();  } // Funktion zum Hinzufügen einer Kante zum Diagramm public void AddEdge(int u, int v) { adjList[u].Add(v); } // Funktion zum Durchführen einer Breitensuche in einem Diagramm // dargestellt durch Adjazenzliste public void BFS(int startNode) { // Erstellen Sie eine Warteschlange für BFS Queue queue = neue Warteschlange ();  bool[] besuchte = new bool[vertices];  // Den aktuellen Knoten als besucht markieren und in die Warteschlange einreihen besuchte[startNode] = true;  queue.Enqueue(startNode);  // Durch die Warteschlange iterieren while (queue.Count != 0) { // Einen Scheitelpunkt aus der Warteschlange entfernen und ausdrucken int currentNode = queue.Dequeue();  Console.Write(currentNode + ' ');  // Alle benachbarten Scheitelpunkte des // aus der Warteschlange entfernten Scheitelpunkts currentNode abrufen. Wenn ein benachbarter Knoten // nicht besucht wurde, markieren Sie ihn als besucht und // stellen Sie ihn in die Warteschlange ein foreach(int neighbor in adjList[currentNode]) { if (!visited[neighbor] ) { besuchte[Nachbar] = true;  queue.Enqueue(neighbor);  } } } } } class MainClass { public static void Main(string[] args) { // Anzahl der Scheitelpunkte im Diagramm int vertices = 5;  // Einen Graphen erstellen Graph graph = new Graph(vertices);  // Kanten zum Diagramm hinzufügen graph.AddEdge(0, 1);  graph.AddEdge(0, 2);  graph.AddEdge(1, 3);  graph.AddEdge(1, 4);  graph.AddEdge(2, 4);  // BFS-Traversal ab Scheitelpunkt 0 durchführen Console.Write( 'Breadth First Traversal ab Scheitelpunkt 0: ');  graph.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);>
Ausgabe 
Breadth First Traversal starting from vertex 0: 0 1 2 3 4>

Zeitkomplexität: O(V+E), wobei V die Anzahl der Knoten und E die Anzahl der Kanten ist.
Hilfsraum: O(V)

Komplexitätsanalyse des BFS-Algorithmus (Breadth-First Search):

Zeitkomplexität des BFS-Algorithmus: O(V + E)

  • BFS untersucht alle Eckpunkte und Kanten im Diagramm. Im schlimmsten Fall besucht es jeden Scheitelpunkt und jede Kante einmal. Daher beträgt die Zeitkomplexität von BFS O(V + E), wobei V und E die Anzahl der Eckpunkte und Kanten im gegebenen Diagramm sind.

Raumkomplexität des BFS-Algorithmus: O(V)

  • BFS verwendet eine Warteschlange, um die Knoten zu verfolgen, die besucht werden müssen. Im schlimmsten Fall kann die Warteschlange alle Eckpunkte im Diagramm enthalten. Daher beträgt die Raumkomplexität von BFS O(V), wobei V und E die Anzahl der Eckpunkte und Kanten im gegebenen Diagramm sind.

Anwendungen von BFS in Diagrammen:

BFS hat verschiedene Anwendungen in der Graphentheorie und Informatik, darunter:

Löschen aus einem binären Suchbaum
  • Suche nach dem kürzesten Weg: BFS kann verwendet werden, um den kürzesten Weg zwischen zwei Knoten in einem ungewichteten Diagramm zu finden. Indem der übergeordnete Knoten jedes Knotens während der Durchquerung verfolgt wird, kann der kürzeste Pfad rekonstruiert werden.
  • Zykluserkennung: BFS kann verwendet werden, um Zyklen in einem Diagramm zu erkennen. Wenn ein Knoten während der Durchquerung zweimal besucht wird, deutet dies auf das Vorhandensein eines Zyklus hin.
  • Verbundene Komponenten: BFS kann verwendet werden, um verbundene Komponenten in einem Diagramm zu identifizieren. Jede verbundene Komponente besteht aus einer Reihe von Knoten, die voneinander erreichbar sind.
  • Topologische Sortierung: BFS kann verwendet werden, um eine topologische Sortierung für einen gerichteten azyklischen Graphen (DAG) durchzuführen. Durch die topologische Sortierung werden die Knoten in einer linearen Reihenfolge angeordnet, sodass für jede Kante (u, v) u in der Reihenfolge vor v erscheint.
  • Durchquerung der Ebenenreihenfolge von Binärbäumen: BFS kann verwendet werden, um eine Durchquerung der Ebenenreihenfolge eines Binärbaums durchzuführen. Bei dieser Durchquerung werden alle Knoten auf derselben Ebene besucht, bevor zur nächsten Ebene übergegangen wird.
  • Netzwerkrouting: BFS kann verwendet werden, um den kürzesten Weg zwischen zwei Knoten in einem Netzwerk zu finden, was es für die Weiterleitung von Datenpaketen in Netzwerkprotokollen nützlich macht.

Probleme bei der Breitensuche oder BFS für ein Diagramm:

Ja Nein

Probleme

Üben
1. Finden Sie die Ebene eines bestimmten Knotens in einem ungerichteten Diagramm Verknüpfung
2. Minimieren Sie den maximalen benachbarten Unterschied in einem Pfad von links oben nach rechts unten Verknüpfung
10. Überprüfen Sie, ob das Ziel der angegebenen Matrix mit den erforderlichen Zellwerten erreichbar ist Verknüpfung

FAQs zur Breitensuche (BFS) für ein Diagramm:

Frage 1: Was ist BFS und wie funktioniert es?

Antwort: BFS ist ein Graph-Traversal-Algorithmus, der einen Graphen systematisch untersucht, indem er alle Eckpunkte auf einer bestimmten Ebene besucht, bevor er zur nächsten Ebene übergeht. Es beginnt an einem Startscheitelpunkt, stellt ihn in eine Warteschlange und markiert ihn als besucht. Dann entfernt es einen Scheitelpunkt aus der Warteschlange, besucht ihn und stellt alle seine nicht besuchten Nachbarn in die Warteschlange ein. Dieser Vorgang wird fortgesetzt, bis die Warteschlange leer ist.

Frage 2: Welche Einsatzmöglichkeiten gibt es für BFS?

Antwort: BFS hat verschiedene Anwendungen, darunter das Finden des kürzesten Pfads in einem ungewichteten Graphen, das Erkennen von Zyklen in einem Graphen, das topoologische Sortieren eines gerichteten azyklischen Graphen (DAG), das Finden verbundener Komponenten in einem Graphen und das Lösen von Rätseln wie Labyrinthen und Sudoku.

Frage 3: Wie hoch ist die zeitliche Komplexität von BFS?

Antwort: Die Zeitkomplexität von BFS beträgt O(V + E), wobei V die Anzahl der Eckpunkte und E die Anzahl der Kanten im Diagramm ist.

Frage 4: Wie hoch ist die räumliche Komplexität von BFS?

Antwort: Die Raumkomplexität von BFS beträgt O(V), da es eine Warteschlange verwendet, um den Überblick über die Scheitelpunkte zu behalten, die besucht werden müssen.

Frage 5: Welche Vorteile bietet der Einsatz von BFS?

Antwort: BFS ist einfach zu implementieren und effizient beim Finden des kürzesten Pfads in einem ungewichteten Diagramm. Es garantiert auch, dass alle Scheitelpunkte im Diagramm besucht werden.

In Verbindung stehende Artikel:

  • Aktuelle Artikel zu BFS
  • Tiefendurchquerung
  • Anwendungen der Breiten-ersten-Traversierung
  • Anwendungen der Tiefensuche
  • Zeit- und Raumkomplexität der Breitensuche (BFS)