logo

TechCodeview

Breadth First Search eller BFS for en graf

Breadth First Search (BFS) er en grunnleggende algoritme for grafovergang . Det innebærer å besøke alle de tilkoblede nodene i en graf på en nivå-for-nivå måte. I denne artikkelen vil vi se nærmere på konseptet BFS og hvordan det kan brukes på grafer effektivt

Innholdsfortegnelse



Breadth First Search (BFS) for en graf:

Breadth First Search (BFS) er en grafoverløpsalgoritme som utforsker alle toppunktene i en graf på gjeldende dybde før du går videre til toppunktene på neste dybdenivå. Den starter ved et spesifisert toppunkt og besøker alle naboene før den går videre til neste nivå av naboer. BFS brukes ofte i algoritmer for veisøking, tilkoblede komponenter og korteste veiproblemer i grafer.

mylivecricket.

Forholdet mellom BFS for Graph og BFS for Tree:

Breadth-First Traversal (BFS) for en graf ligner på Bredde-første kryssing av et tre .

Den eneste fangsten her er at, i motsetning til trær , grafer kan inneholde sykluser, så vi kan komme til samme node igjen. For å unngå å behandle en node mer enn én gang deler vi toppunktene inn i to kategorier:



  • Besøkte og
  • Ikke besøkt.

En boolsk besøkt matrise brukes til å markere de besøkte toppunktene. For enkelhets skyld antas det at alle toppunktene er tilgjengelige fra startpunktet. BFS bruker en Breadth First Search (BFS) for en grafalgoritme:

La oss diskutere algoritmen for BFS:

  1. Initialisering: Sett startnoden i kø i en kø og merk den som besøkt.
  2. Utforskning: Mens køen ikke er tom:
    • Sett en node ut av køen og besøk den (skriv for eksempel ut verdien).
    • For hver ubesøkte nabo til noden som ikke er i kø:
      • Still naboen i køen.
      • Merk naboen som besøkt.
  3. Avslutning: Gjenta trinn 2 til køen er tom.

Denne algoritmen sikrer at alle noder i grafen besøkes på en bredde-først måte, med start fra startnoden.



Hvordan fungerer BFS-algoritmen?

Fra roten besøkes alle nodene på et bestemt nivå først, og deretter krysses nodene på neste nivå til alle nodene er besøkt.

For å gjøre dette brukes en kø. Alle de tilstøtende ubesøkte nodene på gjeldende nivå skyves inn i køen og nodene på gjeldende nivå merkes som besøkt og spratt ut av køen.

Illustrasjon:

La oss forstå hvordan algoritmen fungerer ved hjelp av følgende eksempel.

Trinn 1: Opprinnelig er køen og besøkte arrays tomme.

Køen og besøkte arrays er tomme til å begynne med.

Steg 2: Skyv node 0 inn i køen og merk den som besøkt.

Skyv node 0 inn i køen og merk den som besøkt.

Skyv node 0 inn i køen og merk den som besøkt.

Trinn 3: Fjern node 0 fra forsiden av køen og besøk de ubesøkte naboene og skyv dem inn i køen.

streng til char java
Fjern node 0 fra forsiden av køen og besøkte de ubesøkte naboene og skyv inn i køen.

Fjern node 0 fra forsiden av køen og besøkte de ubesøkte naboene og skyv inn i køen.

Trinn 4: Fjern node 1 fra forsiden av køen og besøk de ubesøkte naboene og skyv dem inn i køen.

Fjern node 1 fra forsiden av køen og besøkte de ubesøkte naboene og trykk

Fjern node 1 fra forsiden av køen og besøkte de ubesøkte naboene og trykk

Trinn 5: Fjern node 2 fra forsiden av køen og besøk de ubesøkte naboene og skyv dem inn i køen.

Fjern node 2 fra forsiden av køen og besøk de ubesøkte naboene og skyv dem inn i køen.

Fjern node 2 fra forsiden av køen og besøk de ubesøkte naboene og skyv dem inn i køen.

java-strenger

Trinn 6: Fjern node 3 fra forsiden av køen og besøk de ubesøkte naboene og skyv dem inn i køen.
Siden vi kan se at alle naboer til node 3 er besøkt, så flytt til neste node som står foran i køen.

Fjern node 3 fra forsiden av køen og besøk de ubesøkte naboene og skyv dem inn i køen.

Fjern node 3 fra forsiden av køen og besøk de ubesøkte naboene og skyv dem inn i køen.

Trinn 7: Fjern node 4 fra forsiden av køen og besøk de ubesøkte naboene og skyv dem inn i køen.
Siden vi kan se at alle naboer til node 4 er besøkt, så flytt til neste node som er foran i køen.

Fjern node 4 fra forsiden av køen og besøk de ubesøkte naboene og skyv dem inn i køen.

Fjern node 4 fra forsiden av køen og besøk de ubesøkte naboene og skyv dem inn i køen.

Nå blir køen tom, så avslutt disse iterasjonsprosessene.

Implementering av BFS for Graph ved å bruke 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økt) { // Opprett en kø for BFS-kø q;  // Marker gjeldende node som besøkt og sett den besøkte i kø[startNode] = true;  q.push(startNode);  // Iterer over køen mens (!q.empty()) { // Sett et vertex i kø fra køen og skriv det ut 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() { // Antall toppunkter i grafen int toppunkter = 5;  // Adjacency listerepresentasjon av grafvektoren> adjList(vertices);  // Legg til kanter til grafen addEdge(adjList, 0, 1);  addEdge(adjList, 0, 2);  addEdge(adjList, 1, 3);  addEdge(adjList, 1, 4);  addEdge(adjList, 2, 4);  // Merk alle toppunktene som ikke besøkt vektor besøkt(vertices, false);  // Utfør BFS-traversal fra toppunkt 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->neste = NULL;  returnere nyNode; } // Funksjon for å legge til en kant til grafen void addEdge(struct Node* adjList[], int u, int v) { struct Node* newNode = createNode(v);  newNode->neste = adjList[u];  adjList[u] = nyNode; } // Funksjon for å utføre Breadth First Search på en graf // representert ved hjelp av adjacency list void bfs(struct Node* adjList[], int vertices, int startNode, int visited[]) { // Opprett en kø for BFS int queue[ MAX_VERTICES];  int foran = 0, bak = 0;  // Marker gjeldende node som besøkt og sett den besøkte i kø[startNode] = 1;  kø[rear++] = startNode;  // Iterer over køen mens (front != rear) { // Sett et vertex i kø fra køen og skriv det ut int currentNode = kø[front++];  printf('%d ', gjeldende node);  // Hent alle tilstøtende toppunktene til det dekøde toppunktet // currentNode Hvis en tilstøtende ikke har blitt besøkt, // så merk den besøkt og sett den i kø struct Node* temp = adjList[currentNode];  while (temp != NULL) { int nabo = temp->data;  if (!besøkt[nabo]) { besøkt[nabo] = 1;  kø[rear++] = nabo;  } temp = temp->neste;  } } } int main() { // Antall toppunkter i grafen int toppunkter = 5;  // Adjacency listerepresentasjon av 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('umerket') 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[] besøkt = nye boolean[vertices];  // Marker gjeldende node som besøkt og sett den besøkte i kø[startNode] = true;  queue.add(startNode);  // Iterer over køen mens (!queue.isEmpty()) { // Sett et vertex i kø fra køen og skriv det ut int currentNode = queue.poll();  System.out.print(currentNode + ' ');  // Hent alle tilstøtende hjørner av den dekøde // vertex currentNode Hvis en tilstøtende ikke har // blitt besøkt, merk den som besøkt og // sett den i kø for (int neighbor : adjList[currentNode]) { if (!visited[nabo] ) { besøkt[nabo] = sant;  queue.add(nabo);  } } } } } public class Main { public static void main(String[] args) { // Antall toppunkter i grafen int vertices = 5;  // Lag en graf Graph graph = new Graph(vertices);  // Legg til kanter til grafen graph.addEdge(0, 1);  graph.addEdge(0, 2);  graph.addEdge(1, 3);  graph.addEdge(1, 4);  graph.addEdge(2, 4);  // Utfør BFS-traversal fra toppunkt 0 System.out.print( 'Bredth First Traversal starter 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 [vertekser];  for (int i = 0; i< vertices; ++i)  adjList[i] = new List ();  } // Funksjon for å legge til en kant til grafen public void AddEdge(int u, int v) { adjList[u].Add(v); } // Funksjon for å utføre Breadth First Search på en graf // representert ved bruk av adjacency list public void BFS(int startNode) { // Opprett en kø for BFS Queue kø = ny kø ();  bool[] besøkt = new bool[vertices];  // Marker gjeldende node som besøkt og sett den besøkte i kø[startNode] = true;  queue.Enqueue(startNode);  // Iterer over køen mens (queue.Count != 0) { // Sett et vertex i kø fra køen og skriv det ut int currentNode = queue.Dequeue();  Console.Write(currentNode + ' ');  // Hent alle tilstøtende hjørner av den dekøde // vertex currentNode Hvis en tilstøtende ikke har // blitt besøkt, merk den som besøkt og // sett den i kø foreach(int neighbor i adjList[currentNode]) { if (!visited[nabo]) ) { besøkt[nabo] = sant;  kø.Kø(nabo);  } } } } } class MainClass { public static void Main(string[] args) { // Antall toppunkter i grafen int vertices = 5;  // Lag en graf Graph graph = new Graph(vertices);  // Legg til kanter til grafen.AddEdge(0, 1);  graph.AddEdge(0, 2);  graph.AddEdge(1, 3);  graph.AddEdge(1, 4);  graph.AddEdge(2, 4);  // Utfør BFS-traversal fra toppunkt 0 Console.Write( 'Bredth First Traversal starter 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);>
Produksjon 
Breadth First Traversal starting from vertex 0: 0 1 2 3 4>

Tidskompleksitet: O(V+E), der V er antall noder og E er antall kanter.
Hjelpeplass: O(V)

pandas loc

Kompleksitetsanalyse av Breadth-First Search (BFS) Algoritme:

Tidskompleksiteten til BFS-algoritmen: O(V + E)

  • BFS utforsker alle toppunktene og kantene i grafen. I verste fall besøker den hver toppunkt og kant én gang. Derfor er tidskompleksiteten til BFS O(V + E), der V og E er antall toppunkter og kanter i den gitte grafen.

Romkompleksiteten til BFS-algoritmen: O(V)

  • BFS bruker en kø for å holde styr på toppunktene som må besøkes. I verste fall kan køen inneholde alle toppunktene i grafen. Derfor er romkompleksiteten til BFS O(V), der V og E er antall toppunkter og kanter i den gitte grafen.

Anvendelser av BFS i grafer:

BFS har forskjellige applikasjoner innen grafteori og informatikk, inkludert:

  • Korteste vei å finne: BFS kan brukes til å finne den korteste veien mellom to noder i en uvektet graf. Ved å holde styr på overordnet til hver node under gjennomkjøringen, kan den korteste veien rekonstrueres.
  • Syklusdeteksjon: BFS kan brukes til å oppdage sykluser i en graf. Hvis en node besøkes to ganger under gjennomkjøringen, indikerer det tilstedeværelsen av en syklus.
  • Tilkoblede komponenter: BFS kan brukes til å identifisere tilkoblede komponenter i en graf. Hver tilkoblet komponent er et sett med noder som kan nås fra hverandre.
  • Topologisk sortering: BFS kan brukes til å utføre topologisk sortering på en rettet asyklisk graf (DAG). Topologisk sortering ordner nodene i en lineær rekkefølge slik at for en hvilken som helst kant (u, v), vises u foran v i rekkefølgen.
  • Nivårekkefølgegjennomgang av binære trær: BFS kan brukes til å utføre en nivåordregjennomgang av et binært tre. Denne gjennomgangen besøker alle noder på samme nivå før den går til neste nivå.
  • Nettverksruting: BFS kan brukes til å finne den korteste veien mellom to noder i et nettverk, noe som gjør det nyttig for ruting av datapakker i nettverksprotokoller.

Problemer med Breadth First Search eller BFS for en graf:

Ja Nei

Problemer

Øve på
1. Finn nivået til en gitt node i en urettet graf Link
2. Minimer maksimal tilstøtende forskjell i en bane fra øverst til venstre til nederst til høyre Link
10. Sjekk om destinasjonen til gitt matrise er tilgjengelig med nødvendige celleverdier Link

Vanlige spørsmål om Breadth First Search (BFS) for en graf:

Spørsmål 1: Hva er BFS og hvordan fungerer det?

Svar: BFS er en graftraversalalgoritme som systematisk utforsker en graf ved å besøke alle toppunktene på et gitt nivå før du går videre til neste nivå. Den starter fra et startpunkt, setter det i kø i en kø og merker det som besøkt. Deretter setter den en toppunkt fra køen, besøker den og setter alle ubesøkte naboer i køen. Denne prosessen fortsetter til køen er tom.

Spørsmål 2: Hva er applikasjonene til BFS?

Svar: BFS har forskjellige applikasjoner, inkludert å finne den korteste veien i en uvektet graf, oppdage sykluser i en graf, topologisk sortering av en rettet asyklisk graf (DAG), finne tilkoblede komponenter i en graf og løse gåter som labyrinter og Sudoku.

Spørsmål 3: Hva er tidskompleksiteten til BFS?

Svar: Tidskompleksiteten til BFS er O(V + E), der V er antall toppunkter og E er antall kanter i grafen.

Spørsmål 4: Hva er romkompleksiteten til BFS?

Svar: Plasskompleksiteten til BFS er O(V), da den bruker en kø for å holde styr på hjørnene som må besøkes.

Spørsmål 5: Hva er fordelene med å bruke BFS?

Svar: BFS er enkelt å implementere og effektivt for å finne den korteste veien i en uvektet graf. Det garanterer også at alle toppunktene i grafen blir besøkt.

Relaterte artikler:

  • Nylige artikler om BFS
  • Depth First Traversal
  • Anvendelser av Breadth First Traversal
  • Anvendelser av Depth First Search
  • Tid og rom Complexity of Breadth First Search (BFS)