ISKANJE NAJPREJ V ŠIRINO ALI BFS ZA GRAF

Iskanje najprej v širino (BFS) je temeljni algoritem prečkanja grafa . Vključuje obisk vseh povezanih vozlišč grafa po stopnjah. V tem članku bomo preučili koncept BFS in kako ga je mogoče učinkovito uporabiti za grafe

Kazalo

Iskanje najprej v širino ali BFS za graf
Razmerje med BFS za graf in BFS za drevo
Iskanje najprej v širino (BFS) za grafični algoritem
Kako deluje algoritem BFS?
Implementacija BFS za Graph z uporabo seznama sosednosti
Kompleksnost algoritma iskanja v širino (BFS).
Uporaba BFS v grafih
Težave pri iskanju najprej v širino ali BFS za graf
Pogosta vprašanja o iskanju najprej v širino (BFS) za graf

Iskanje najprej v širino (BFS) za graf:

Iskanje najprej v širino (BFS) je algoritem za prečkanje grafa, ki raziskuje vse točke v grafu na trenutni globini, preden se premakne na točke na naslednji ravni globine. Začne se na določenem vozlišču in obišče vse svoje sosede, preden se premakne na naslednjo raven sosedov. BFS se običajno uporablja v algoritmih za iskanje poti, povezane komponente in težave z najkrajšo potjo v grafih.

Razmerje med BFS za graf in BFS za drevo:

Breadth-First Traversal (BFS) za graf je podoben Prehod drevesa v širino .

Edini ulov tukaj je, da za razliko od drevesa , grafi lahko vsebuje cikle, tako da lahko znova pridemo do istega vozlišča. Da bi se izognili večkratni obdelavi vozlišča, razdelimo vozlišča v dve kategoriji:

Obiskal in
Ni obiskano.

Logično obiskano polje se uporablja za označevanje obiskanih točk. Zaradi enostavnosti se predpostavlja, da so vsa oglišča dosegljiva iz začetnega oglišča. BFS uporablja a Iskanje najprej v širino (BFS) za grafični algoritem:

Pogovorimo se o algoritmu za BFS:

Inicializacija: Začetno vozlišče postavite v čakalno vrsto in ga označite kot obiskano.
Raziskovanje: Dokler čakalna vrsta ni prazna:
- Odstranite vozlišče iz čakalne vrste in ga obiščite (npr. natisnite njegovo vrednost).
- Za vsakega neobiskanega soseda vozlišča, ki je izločeno iz čakalne vrste:
  - Soseda uvrsti v čakalno vrsto.
  - Označi soseda kot obiskanega.
Prekinitev: Ponavljajte korak 2, dokler ni čakalna vrsta prazna.

Ta algoritem zagotavlja, da so vsa vozlišča v grafu obiskana v širino, začenši z začetnim vozliščem.

Kako deluje algoritem BFS?

Začenši od korena, se najprej obiščejo vsa vozlišča na določeni ravni, nato pa se prečkajo vozlišča naslednje ravni, dokler niso obiskana vsa vozlišča.

Za to se uporablja čakalna vrsta. Vsa sosednja neobiskana vozlišča trenutne ravni so potisnjena v čakalno vrsto, vozlišča trenutne ravni pa so označena kot obiskana in izločena iz čakalne vrste.

Ilustracija:

Razumejmo delovanje algoritma s pomočjo naslednjega primera.

Korak 1: Na začetku so čakalna vrsta in obiskani nizi prazni.

Čakalna vrsta in obiskani nizi so na začetku prazni.

2. korak: Potisnite vozlišče 0 v čakalno vrsto in ga označite kot obiskano.

Potisnite vozlišče 0 v čakalno vrsto in ga označite kot obiskano.

3. korak: Odstranite vozlišče 0 s sprednje strani čakalne vrste in obiščite neobiskane sosede ter jih potisnite v čakalno vrsto.
if in else v bash

Odstranite vozlišče 0 s sprednje strani čakalne vrste in obiskane neobiskane sosede ter potisnite v čakalno vrsto.

4. korak: Odstranite vozlišče 1 s sprednje strani čakalne vrste in obiščite neobiskane sosede ter jih potisnite v čakalno vrsto.

Odstranite vozlišče 1 s sprednje strani čakalne vrste in obiskajte neobiskane sosede ter potisnite

5. korak: Odstranite vozlišče 2 s sprednje strani čakalne vrste in obiščite neobiskane sosede ter jih potisnite v čakalno vrsto.

Odstranite vozlišče 2 s sprednje strani čakalne vrste in obiščite neobiskane sosede ter jih potisnite v čakalno vrsto.

6. korak: Odstranite vozlišče 3 s sprednje strani čakalne vrste in obiščite neobiskane sosede ter jih potisnite v čakalno vrsto.
Kot lahko vidimo, so vsi sosedi vozlišča 3 obiskani, zato se premaknite na naslednje vozlišče, ki je na začetku čakalne vrste.

Odstranite vozlišče 3 s sprednje strani čakalne vrste in obiščite neobiskane sosede ter jih potisnite v čakalno vrsto.

7. korak: Odstranite vozlišče 4 s sprednje strani čakalne vrste in obiščite neobiskane sosede ter jih potisnite v čakalno vrsto.
Kot lahko vidimo, so vsi sosedi vozlišča 4 obiskani, zato se premaknite na naslednje vozlišče, ki je na začetku čakalne vrste.

Odstranite vozlišče 4 s sprednje strani čakalne vrste in obiščite neobiskane sosede ter jih potisnite v čakalno vrsto.

Zdaj postane čakalna vrsta prazna, zato prekinite ta postopek ponavljanja.

Implementacija BFS za Graph z uporabo seznama sosednosti:

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 & visited) { // Ustvari čakalno vrsto za čakalno vrsto BFS q;  // Označi trenutno vozlišče kot obiskano in ga postavi v čakalno vrsto visited[startNode] = true;  q.push(startNode);  // Iteracija po čakalni vrsti while (!q.empty()) { // Odstrani točko iz čakalne vrste in jo natisni 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() { // Število točk v grafu int vertices = 5;  // Predstavitev seznama sosednosti vektorja grafa> adjList(vozlišča);  // Dodajanje robov grafu addEdge(adjList, 0, 1);  addEdge(adjList, 0, 2);  addEdge(adjList, 1, 3);  addEdge(adjList, 1, 4);  addEdge(adjList, 2, 4);  // Označi vse točke kot neobiskani vektor obiskano (točke, false);  // Izvedite prečkanje BFS, začenši od točke 0 cout<< 'Breadth First Traversal starting from vertex '  '0: ';  bfs(adjList, 0, visited);  return 0; }>

 #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->podatki = podatki;  novoVozlišče->naslednji = NULL;  vrni novo vozlišče; } // Funkcija za dodajanje roba grafu void addEdge(struct Node* adjList[], int u, int v) { struct Node* newNode = createNode(v);  newNode->next = adjList[u];  adjList[u] = novovozlišče; } // Funkcija za izvajanje iskanja najprej v širino na grafu // predstavljenem s seznamom sosednosti void bfs(struct Node* adjList[], int vertices, int startNode, int visited[]) { // Ustvari čakalno vrsto za BFS int queue[ MAX_VERTICES];  int spredaj = 0, zadaj = 0;  // Označi trenutno vozlišče kot obiskano in ga postavi v čakalno vrsto visited[startNode] = 1;  queue[rear++] = startNode;  // Iteracija po čakalni vrsti while (spredaj != zadaj) { // Odstrani točko iz čakalne vrste in jo natisni int currentNode = queue[front++];  printf('%d ', currentNode);  // Pridobi vsa sosednja vozlišča izločene iz čakalne vrste // currentNode Če sosednje vozlišče ni bilo obiskano, // ga označi kot obiskano in ga postavi v čakalno vrsto struct Node* temp = adjList[currentNode];  medtem ko (temp != NULL) { int bližnji = temp->data;  if (!visited[neighbor]) { visited[neighbor] = 1;  čakalna vrsta [zadaj++] = sosed;  } temp = temp->naprej;  } } } int main() { // Število točk v grafu int vertices = 5;  // Predstavitev seznama sosednosti grafa struct Node* adjList[vertices];  za (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 = nov LinkedList[točke];  za (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 čakalna vrsta = nov LinkedList();  logična vrednost [] obiskano = nova logična vrednost [točke];  // Označi trenutno vozlišče kot obiskano in ga postavi v čakalno vrsto visited[startNode] = true;  queue.add(startNode);  // Iteracija po čakalni vrsti while (!queue.isEmpty()) { // Odstrani točko iz čakalne vrste in jo natisni int currentNode = queue.poll();  System.out.print(currentNode + ' ');  // Pridobi vsa sosednja vozlišča // iz vrste iz vrste currentNode. Če sosednje vozlišče // ni bilo obiskano, ga označi kot obiskano in // postavi v čakalno vrsto za (int neighbor : adjList[currentNode]) { if (!visited[neighbor] ) { visited[neighbor] = true;  queue.add(sosed);  } } } } } public class Main { public static void main(String[] args) { // Število točk v grafu int vertices = 5;  // Ustvari graf Graph graph = new Graph(vertices);  // Dodajanje robov grafu graph.addEdge(0, 1);  graph.addEdge(0, 2);  graph.addEdge(1, 3);  graph.addEdge(1, 4);  graph.addEdge(2, 4);  // Izvedi prečkanje BFS, začenši od točke 0 System.out.print( 'Prvo prečkanje širine, začenši od točke 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()>

 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 seznam [ oglišča ];  za (int i = 0; i< vertices; ++i)  adjList[i] = new List ();  } // Funkcija za dodajanje roba grafu public void AddEdge(int u, int v) { adjList[u].Add(v); } // Funkcija za izvajanje iskanja najprej v širino na grafu // predstavljenem s seznamom sosednosti public void BFS(int startNode) { // Ustvari čakalno vrsto za čakalno vrsto BFS čakalna vrsta = nova čakalna vrsta ();  bool[] obiskano = nova bool[točke];  // Označi trenutno vozlišče kot obiskano in ga postavi v čakalno vrsto visited[startNode] = true;  queue.Enqueue(startNode);  // Iteracija po čakalni vrsti while (queue.Count != 0) { // Odstrani točko iz čakalne vrste in jo natisni int currentNode = queue.Dequeue();  Console.Write(currentNode + ' ');  // Pridobi vsa sosednja oglišča iz vrste // oglišča currentNode Če sosednje ni bilo // obiskano, ga označi kot obiskanega in // postavi v čakalno vrsto foreach(int neighbor in adjList[currentNode]) { if (!visited[neighbor] ) { visited[neighbor] = true;  queue.Enqueue(neighbor);  } } } } } class MainClass { public static void Main(string[] args) { // Število točk v grafu int vertices = 5;  // Ustvari graf Graph graph = new Graph(vertices);  // Dodajanje robov grafu graph.AddEdge(0, 1);  graph.AddEdge(0, 2);  graph.AddEdge(1, 3);  graph.AddEdge(1, 4);  graph.AddEdge(2, 4);  // Izvedi prečkanje BFS, začenši od točke 0 Console.Write( 'Prvo prečkanje širine, začenši od točke 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);>

Izhod

Breadth First Traversal starting from vertex 0: 0 1 2 3 4>

Časovna zapletenost: O(V+E), kjer je V število vozlišč in E število robov.
Pomožni prostor: O(V)

Analiza kompleksnosti algoritma iskanja v širino (BFS):

Časovna kompleksnost algoritma BFS: O(V + E)

BFS raziskuje vsa oglišča in robove v grafu. V najslabšem primeru enkrat obišče vsako točko in rob. Zato je časovna kompleksnost BFS O(V + E), kjer sta V in E število oglišč in robov v danem grafu.

Prostorska kompleksnost algoritma BFS: O(V)

BFS uporablja čakalno vrsto za sledenje točkam, ki jih je treba obiskati. V najslabšem primeru lahko čakalna vrsta vsebuje vsa vozlišča v grafu. Zato je prostorska kompleksnost BFS O(V), kjer sta V in E število oglišč in robov v danem grafu.

Uporaba BFS v grafih:

BFS ima različne aplikacije v teoriji grafov in računalništvu, vključno z:

Iskanje najkrajše poti: BFS se lahko uporablja za iskanje najkrajše poti med dvema vozliščema v neuteženem grafu. Če med prehodom spremljate nadrejeno vozlišče, je mogoče rekonstruirati najkrajšo pot.
Zaznavanje cikla: BFS se lahko uporablja za zaznavanje ciklov v grafu. Če je vozlišče obiskano dvakrat med prečkanjem, to kaže na prisotnost cikla.
Povezane komponente: BFS se lahko uporablja za prepoznavanje povezanih komponent v grafu. Vsaka povezana komponenta je niz vozlišč, ki jih je mogoče doseči drug od drugega.
Topološko razvrščanje: BFS se lahko uporablja za izvajanje topološkega razvrščanja na usmerjenem acikličnem grafu (DAG). Topološko razvrščanje razporedi vozlišča v linearnem vrstnem redu, tako da se za kateri koli rob (u, v) pojavi u pred v v vrstnem redu.
Prehod vrstnega reda ravni binarnih dreves: BFS se lahko uporablja za izvedbo prečkanja binarnega drevesa po vrstnem redu ravni. To prečkanje obišče vsa vozlišča na isti ravni, preden se premakne na naslednjo raven.
Omrežno usmerjanje: BFS se lahko uporablja za iskanje najkrajše poti med dvema vozliščema v omrežju, zaradi česar je uporaben za usmerjanje podatkovnih paketov v omrežnih protokolih.

Težave pri iskanju najprej v širino ali BFS za graf:

da ne	Težave	Vadite
1.	Poiščite raven danega vozlišča v neusmerjenem grafu	Povezava
2.	Zmanjšajte največjo sosednjo razliko na poti od zgornjega levega do spodnjega desnega	Povezava
10.	Preverite, ali je cilj dane matrike dosegljiv z zahtevanimi vrednostmi celic	Povezava

Pogosta vprašanja o iskanju najprej v širino (BFS) za graf:

Vprašanje 1: Kaj je BFS in kako deluje?

odgovor: BFS je algoritem za prečkanje grafa, ki sistematično raziskuje graf tako, da obišče vsa vozlišča na dani ravni, preden se premakne na naslednjo raven. Začne se z začetne točke, jo postavi v čakalno vrsto in označi kot obiskano. Nato odstrani vozlišče iz čakalne vrste, ga obišče in v čakalno vrsto uvrsti vse svoje neobiskane sosede. Ta postopek se nadaljuje, dokler ni čakalna vrsta prazna.

2. vprašanje: Kakšne so aplikacije BFS?

odgovor: BFS ima različne aplikacije, vključno z iskanjem najkrajše poti v neobteženem grafu, zaznavanjem ciklov v grafu, topološkim razvrščanjem usmerjenega acikličnega grafa (DAG), iskanjem povezanih komponent v grafu in reševanjem ugank, kot so labirinti in sudoku.

3. vprašanje: Kakšna je časovna zahtevnost BFS?

odgovor: Časovna kompleksnost BFS je O(V + E), kjer je V število vozlišč in E število robov v grafu.

4. vprašanje: Kakšna je prostorska kompleksnost BFS?

odgovor: Prostorska kompleksnost BFS je O(V), saj uporablja čakalno vrsto za sledenje točkam, ki jih je treba obiskati.

5. vprašanje: Kakšne so prednosti uporabe BFS?

odgovor: BFS je preprost za implementacijo in učinkovit za iskanje najkrajše poti v neuteženem grafu. Prav tako zagotavlja, da so obiskane vse točke v grafu.
pozdravljen svet java

Povezani članki:

Nedavni članki o BFS
Prvo prečenje globine
Aplikacije prehoda prve širine
Uporaba globinskega iskanja
Časovna in prostorska kompleksnost iskanja najprej v širino (BFS)