logo

TechCodeview

Breadth First Search eller BFS for en graf

Breadth First Search (BFS) er en grundlæggende grafgennemløbsalgoritme . Det indebærer at besøge alle de forbundne noder i en graf på en niveau-for-niveau måde. I denne artikel vil vi se nærmere på begrebet BFS og hvordan det kan anvendes på grafer effektivt

Indholdsfortegnelse



Breadth First Search (BFS) for en graf:

Breadth First Search (BFS) er en grafgennemløbsalgoritme, der udforsker alle hjørnerne i en graf i den aktuelle dybde, før de går videre til hjørnerne på næste dybdeniveau. Den starter ved et bestemt toppunkt og besøger alle sine naboer, før den går videre til næste niveau af naboer. BFS bruges almindeligvis i algoritmer til stifinding, forbundne komponenter og korteste vejproblemer i grafer.

mylivecricket.

Forholdet mellem BFS for Graph og BFS for Tree:

Breadth-First Traversal (BFS) for en graf svarer til Bredde-første gennemgang af et træ .

Den eneste fangst her er, at i modsætning til træer , grafer kan indeholde cyklusser, så vi kan komme til den samme knude igen. For at undgå at behandle en node mere end én gang opdeler vi hjørnerne i to kategorier:



  • Besøgte og
  • Ikke besøgt.

Et boolsk besøgt array bruges til at markere de besøgte hjørner. For nemheds skyld antages det, at alle toppunkter er tilgængelige fra startpunktet. BFS bruger -en Breadth First Search (BFS) for en grafalgoritme:

Lad os diskutere algoritmen for BFS:

  1. Initialisering: Sæt startknuden i kø i en kø, og marker den som besøgt.
  2. Udforskning: Mens køen ikke er tom:
    • Sæt en node i kø fra køen og besøg den (udskriv f.eks. dens værdi).
    • For hver ubesøgt nabo til den ude af kø:
      • Stil naboen i køen.
      • Markér naboen som besøgt.
  3. Afslutning: Gentag trin 2, indtil køen er tom.

Denne algoritme sikrer, at alle noder i grafen besøges på en bredde-først måde, startende fra startknudepunktet.



Hvordan virker BFS-algoritmen?

Startende fra roden besøges alle noder på et bestemt niveau først, og derefter krydses noderne på det næste niveau, indtil alle noderne er besøgt.

For at gøre dette bruges en kø. Alle de tilstødende ubesøgte noder på det aktuelle niveau skubbes ind i køen, og noderne på det aktuelle niveau markeres som besøgte og spærres fra køen.

Illustration:

Lad os forstå algoritmens virkemåde ved hjælp af følgende eksempel.

Trin 1: Oprindeligt er kø og besøgte arrays tomme.

Kø og besøgte arrays er tomme i starten.

Trin 2: Skub node 0 ind i køen og marker den som besøgt.

Skub node 0 ind i køen og marker den som besøgt.

Skub node 0 ind i køen og marker den som besøgt.

Trin 3: Fjern node 0 fra forsiden af ​​køen og besøg de ubesøgte naboer og skub dem ind i køen.

streng for lang
Fjern node 0 fra forsiden af ​​køen og besøgte de ubesøgte naboer og skub ind i køen.

Fjern node 0 fra forsiden af ​​køen og besøgte de ubesøgte naboer og skub ind i køen.

Trin 4: Fjern node 1 fra forsiden af ​​køen og besøg de ubesøgte naboer og skub dem ind i køen.

Fjern node 1 fra forsiden af ​​køen og besøgte de ubesøgte naboer og skub

Fjern node 1 fra forsiden af ​​køen og besøgte de ubesøgte naboer og skub

Trin 5: Fjern node 2 fra forsiden af ​​køen og besøg de ubesøgte naboer og skub dem ind i køen.

Fjern node 2 fra forsiden af ​​køen og besøg de ubesøgte naboer og skub dem ind i køen.

Fjern node 2 fra forsiden af ​​køen og besøg de ubesøgte naboer og skub dem ind i køen.

java strenge

Trin 6: Fjern node 3 fra forsiden af ​​køen og besøg de ubesøgte naboer og skub dem ind i køen.
Da vi kan se, at alle naboer til node 3 er besøgt, så flyt til den næste node, der er foran i køen.

Fjern node 3 fra forsiden af ​​køen og besøg de ubesøgte naboer og skub dem ind i køen.

Fjern node 3 fra forsiden af ​​køen og besøg de ubesøgte naboer og skub dem ind i køen.

Trin 7: Fjern node 4 fra forsiden af ​​køen og besøg de ubesøgte naboer og skub dem ind i køen.
Da vi kan se, at alle naboer til node 4 er besøgt, så flyt til den næste node, der er foran i køen.

Fjern node 4 fra forsiden af ​​køen og besøg de ubesøgte naboer og skub dem ind i køen.

Fjern node 4 fra forsiden af ​​køen og besøg de ubesøgte naboer og skub dem ind i køen.

Nu bliver køen tom, så afslut disse iterationsprocesser.

Implementering af BFS for Graph ved hjælp af Adjacency List:

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 & besøgt) { // Opret en kø til BFS-kø q;  // Marker den aktuelle node som besøgt og sæt den i kø [startNode] = sand;  q.push(startNode);  // Iterér over køen, mens (!q.empty()) { // Sæt et vertex i kø fra køen og udskriv det 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() { // Antal toppunkter i grafen int toppunkter = 5;  // Adjacency listerepræsentation af grafvektoren> adjList(hjørnepunkter);  // Tilføj kanter til grafen addEdge(adjList, 0, 1);  addEdge(adjList, 0, 2);  addEdge(adjList, 1, 3);  addEdge(adjList, 1, 4);  addEdge(adjList, 2, 4);  // Marker alle hjørnerne som ikke besøgt vektor besøgt(hjørnepunkter, falsk);  // Udfør BFS-traversal startende fra vertex 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->data = data;  newNode->next = NULL;  returnere nyNode; } // Funktion til at tilføje en kant til grafen void addEdge(struct Node* adjList[], int u, int v) { struct Node* newNode = createNode(v);  newNode->next = adjList[u];  adjList[u] = nyNode; } // Funktion til at udføre Breadth First Search på en graf // repræsenteret ved hjælp af adjacency list void bfs(struct Node* adjList[], int vertices, int startNode, int visited[]) { // Opret en kø for BFS int queue[ MAX_VERTICES];  int front = 0, bagside = 0;  // Marker den aktuelle node som besøgt og sæt den i kø [startNode] = 1;  kø[rear++] = startNode;  // Iterér over køen, mens (front != rear) { // Sæt et vertex i kø fra køen og udskriv det int currentNode = kø[front++];  printf('%d ', nuværende node);  // Hent alle tilstødende hjørner af det udkøede vertex // currentNode Hvis en tilstødende ikke er blevet besøgt, // så marker den besøgt og sæt den i kø struct Node* temp = adjList[currentNode];  while (temp != NULL) { int nabo = temp->data;  if (!besøgt[nabo]) { besøgt[nabo] = 1;  kø[rear++] = nabo;  } temp = temp->næste;  } } } int main() { // Antal toppunkter i grafen int toppunkter = 5;  // Adjacency listerepræsentation af grafstrukturen Node* adjList[vertices];  for (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('ikke markeret') Graph(int vertices) { this.vertices = vertices;  adjList = new LinkedList[vertices];  for (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 kø = new LinkedList();  boolean[] visited = new boolean[vertices];  // Marker den aktuelle node som besøgt og sæt den i kø [startNode] = sand;  queue.add(startNode);  // Iterér over køen, mens (!queue.isEmpty()) { // Sæt et vertex i kø fra køen og udskriv det int currentNode = queue.poll();  System.out.print(currentNode + ' ');  // Hent alle tilstødende hjørner af den udkøede // vertex currentNode Hvis en tilstødende ikke er // blevet besøgt, så marker den besøgt og // sæt den i kø for (int neighbor : adjList[currentNode]) { if (!visited[nabo]) ) { besøgt[nabo] = sand;  kø.add(nabo);  } } } } } public class Main { public static void main(String[] args) { // Antal toppunkter i grafen int vertices = 5;  // Opret en graf Graph graph = new Graph(vertices);  // Tilføj kanter til grafen graph.addEdge(0, 1);  graph.addEdge(0, 2);  graph.addEdge(1, 3);  graph.addEdge(1, 4);  graph.addEdge(2, 4);  // Udfør BFS traversal startende fra toppunkt 0 System.out.print( 'Bredth First Traversal startende fra toppunkt 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 = ny liste [spidser];  for (int i = 0; i< vertices; ++i)  adjList[i] = new List ();  } // Funktion til at tilføje en kant til grafen public void AddEdge(int u, int v) { adjList[u].Add(v); } // Funktion til at udføre Breadth First Search på en graf // repræsenteret ved hjælp af adjacency list public void BFS(int startNode) { // Opret en kø for BFS Queue kø = ny kø ();  bool[] visited = new bool[vertices];  // Marker den aktuelle node som besøgt og sæt den i kø [startNode] = sand;  kø.Enqueue(startNode);  // Iterér over køen mens (queue.Count != 0) { // Sæt et vertex i kø fra køen og udskriv det int currentNode = queue.Dequeue();  Console.Write(currentNode + ' ');  // Hent alle tilstødende hjørner af den dequeued // vertex currentNode Hvis en tilstødende ikke er // blevet besøgt, så marker den besøgt og // sæt den i kø foreach(int neighbor i adjList[currentNode]) { if (!visited[nabo] ) { besøgt[nabo] = sand;  kø.Kø(nabo);  } } } } } class MainClass { public static void Main(string[] args) { // Antal toppunkter i grafen int vertices = 5;  // Opret en graf Graph graph = new Graph(vertices);  // Tilføj kanter til grafen.AddEdge(0, 1);  graph.AddEdge(0, 2);  graph.AddEdge(1, 3);  graph.AddEdge(1, 4);  graph.AddEdge(2, 4);  // Udfør BFS traversal startende fra toppunkt 0 Console.Write( 'Bredth First Traversal startende fra toppunkt 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);>
Produktion 
Breadth First Traversal starting from vertex 0: 0 1 2 3 4>

Tidskompleksitet: O(V+E), hvor V er antallet af noder og E er antallet af kanter.
Hjælpeplads: O(V)

pandas loc

Kompleksitetsanalyse af Breadth-First Search (BFS) Algoritme:

Tidskompleksitet af BFS-algoritme: O(V + E)

  • BFS udforsker alle toppunkter og kanter i grafen. I værste fald besøger den hver top og kant én gang. Derfor er tidskompleksiteten af ​​BFS O(V + E), hvor V og E er antallet af hjørner og kanter i den givne graf.

Rumkompleksitet af BFS-algoritme: O(V)

  • BFS bruger en kø til at holde styr på de hjørner, der skal besøges. I værste fald kan køen indeholde alle hjørnerne i grafen. Derfor er rumkompleksiteten af ​​BFS O(V), hvor V og E er antallet af hjørner og kanter i den givne graf.

Anvendelser af BFS i grafer:

BFS har forskellige applikationer inden for grafteori og datalogi, herunder:

  • Korteste vej: BFS kan bruges til at finde den korteste vej mellem to noder i en uvægtet graf. Ved at holde styr på forælderen til hver knude under gennemkørslen kan den korteste vej rekonstrueres.
  • Cyklus detektion: BFS kan bruges til at detektere cyklusser i en graf. Hvis en node besøges to gange under gennemkørslen, indikerer det tilstedeværelsen af ​​en cyklus.
  • Tilsluttede komponenter: BFS kan bruges til at identificere tilsluttede komponenter i en graf. Hver tilsluttet komponent er et sæt knudepunkter, der kan nås fra hinanden.
  • Topologisk sortering: BFS kan bruges til at udføre topologisk sortering på en rettet acyklisk graf (DAG). Topologisk sortering arrangerer noderne i en lineær rækkefølge, således at u for enhver kant (u, v) vises før v i rækkefølgen.
  • Niveauordregennemgang af binære træer: BFS kan bruges til at udføre en niveaurækkefølgegennemgang af et binært træ. Denne gennemkøring besøger alle noder på samme niveau, før den går til næste niveau.
  • Netværksrouting: BFS kan bruges til at finde den korteste vej mellem to noder i et netværk, hvilket gør det nyttigt til routing af datapakker i netværksprotokoller.

Problemer med Breadth First Search eller BFS for en graf:

Ja Nej

Problemer

Øve sig
1. Find niveauet for en given node i en udirigeret graf Link
2. Minimer maksimal tilstødende forskel i en sti fra øverst til venstre til nederst til højre Link
10. Tjek, om destinationen for den givne matrix kan nås med de nødvendige værdier af celler Link

Ofte stillede spørgsmål om Breadth First Search (BFS) for en graf:

Spørgsmål 1: Hvad er BFS, og hvordan virker det?

Svar: BFS er en grafgennemløbsalgoritme, der systematisk udforsker en graf ved at besøge alle hjørnerne på et givet niveau, før de går videre til næste niveau. Den starter fra et startpunkt, sætter den i kø i en kø og markerer den som besøgt. Derefter sætter den et toppunkt i køen fra køen, besøger det og sætter alle dets ubesøgte naboer i kø i køen. Denne proces fortsætter, indtil køen er tom.

Spørgsmål 2: Hvad er anvendelserne af BFS?

Svar: BFS har forskellige applikationer, herunder at finde den korteste vej i en uvægtet graf, detektere cyklusser i en graf, topologisk sortering af en rettet acyklisk graf (DAG), finde forbundne komponenter i en graf og løse gåder som labyrinter og Sudoku.

Spørgsmål 3: Hvad er tidskompleksiteten af ​​BFS?

Svar: Tidskompleksiteten af ​​BFS er O(V + E), hvor V er antallet af hjørner og E er antallet af kanter i grafen.

Spørgsmål 4: Hvad er rumkompleksiteten af ​​BFS?

Svar: Rumkompleksiteten af ​​BFS er O(V), da den bruger en kø til at holde styr på de hjørner, der skal besøges.

Spørgsmål 5: Hvad er fordelene ved at bruge BFS?

Svar: BFS er enkel at implementere og effektiv til at finde den korteste vej i en uvægtet graf. Det garanterer også, at alle hjørnerne i grafen bliver besøgt.

Relaterede artikler:

  • Seneste artikler om BFS
  • Dybde første gennemløb
  • Anvendelser af Breadth First Traversal
  • Anvendelser af Depth First Search
  • Tid og rum kompleksitet af Breadth First Search (BFS)