logo

TechCodeview

Platuma pirmā meklēšana vai BFS diagrammai

Meklēšana pirmajā vietā (BFS) ir fundamentāls grafu šķērsošanas algoritms . Tas ietver visu diagrammas savienoto mezglu apmeklēšanu katrā līmenī. Šajā rakstā mēs apskatīsim jēdzienu BFS un kā to var efektīvi pielietot grafikiem

Satura rādītājs



Diagrammas meklēšana pēc platuma vispirms (BFS):

Meklēšana pirmajā vietā (BFS) ir grafa šķērsošanas algoritms, kas pēta visas grafa virsotnes pašreizējā dziļumā, pirms pāriet uz virsotnēm nākamajā dziļuma līmenī. Tas sākas noteiktā virsotnē un apmeklē visus savus kaimiņus, pirms pāriet uz nākamo kaimiņu līmeni. BFS parasti izmanto algoritmos ceļa noteikšanai, savienotajiem komponentiem un īsākā ceļa problēmām grafikos.

Saistība starp BFS for Graph un BFS for Tree:

Diagrammas platuma pirmā šķērsošana (BFS) ir līdzīga Koka šķērsošana platumā .

rekha filmu aktrise

Vienīgais āķis šeit ir tas, ka atšķirībā no koki , grafiki var saturēt ciklus, tāpēc mēs varam atkal nonākt pie tā paša mezgla. Lai izvairītos no mezgla apstrādes vairāk nekā vienu reizi, mēs sadalām virsotnes divās kategorijās:



  • Apmeklēja un
  • Nav apmeklēts.

Būla apmeklētais masīvs tiek izmantots, lai atzīmētu apmeklētās virsotnes. Vienkāršības labad tiek pieņemts, ka visas virsotnes ir sasniedzamas no sākuma virsotnes. BFS lietojumiem a Diagrammas algoritma meklēšana pēc platuma vispirms (BFS):

Apspriedīsim BFS algoritmu:

  1. Inicializācija: Ievietojiet sākuma mezglu rindā un atzīmējiet to kā apmeklētu.
  2. Izpēte: Kamēr rinda nav tukša:
    • Izslēdziet mezglu no rindas un apmeklējiet to (piemēram, izdrukājiet tā vērtību).
    • Katram neapmeklētam rindu izslēgtā mezgla kaimiņam:
      • Ievietojiet kaimiņu rindā.
      • Atzīmējiet kaimiņu kā apmeklētu.
  3. Pārtraukšana: Atkārtojiet 2. darbību, līdz rinda ir tukša.

Šis algoritms nodrošina, ka visi grafa mezgli tiek apmeklēti pēc platuma, sākot no sākuma mezgla.



Kā darbojas BFS algoritms?

Sākot no saknes, vispirms tiek apmeklēti visi konkrētā līmeņa mezgli un pēc tam tiek šķērsoti nākamā līmeņa mezgli, līdz tiek apmeklēti visi mezgli.

Lai to izdarītu, tiek izmantota rinda. Visi blakus esošie pašreizējā līmeņa neapmeklētie mezgli tiek iespiesti rindā, un pašreizējā līmeņa mezgli tiek atzīmēti kā apmeklēti un izņemti no rindas.

Ilustrācija:

Ļaujiet mums saprast algoritma darbību, izmantojot šādu piemēru.

1. darbība: Sākotnēji rinda un apmeklētie masīvi ir tukši.

Rinda un apmeklētie masīvi sākotnēji ir tukši.

2. darbība: Iesūtiet mezglu 0 rindā un atzīmējiet to kā apmeklētu.

Iesūtiet mezglu 0 rindā un atzīmējiet to kā apmeklētu.

Iesūtiet mezglu 0 rindā un atzīmējiet to kā apmeklētu.

3. darbība: Noņemiet mezglu 0 no rindas priekšpuses un apmeklējiet neapmeklētos kaimiņus un ievietojiet tos rindā.

Noņemiet mezglu 0 no rindas priekšpuses un apmeklēja neapmeklētos kaimiņus un iestādiet rindā.

Noņemiet mezglu 0 no rindas priekšpuses un apmeklēja neapmeklētos kaimiņus un iestādiet rindā.

4. darbība: Noņemiet mezglu 1 no rindas priekšpuses un apmeklējiet neapmeklētos kaimiņus un ievietojiet tos rindā.

Noņemiet mezglu 1 no rindas priekšpuses un apmeklēja neapmeklētos kaimiņus un nospiediet

Noņemiet mezglu 1 no rindas priekšpuses un apmeklēja neapmeklētos kaimiņus un nospiediet

5. darbība: Noņemiet 2. mezglu no rindas priekšpuses un apmeklējiet neapmeklētos kaimiņus un ievietojiet tos rindā.

Noņemiet 2. mezglu no rindas priekšpuses un apmeklējiet neapmeklētos kaimiņus un ievietojiet tos rindā.

Noņemiet 2. mezglu no rindas priekšpuses un apmeklējiet neapmeklētos kaimiņus un ievietojiet tos rindā.

6. darbība: Noņemiet mezglu 3 no rindas priekšpuses un apmeklējiet neapmeklētos kaimiņus un ievietojiet tos rindā.
Kā mēs redzam, ka visi 3. mezgla kaimiņi ir apmeklēti, tāpēc pārejiet uz nākamo mezglu, kas atrodas rindas priekšpusē.

Noņemiet mezglu 3 no rindas priekšpuses un apmeklējiet neapmeklētos kaimiņus un ievietojiet tos rindā.

Noņemiet mezglu 3 no rindas priekšpuses un apmeklējiet neapmeklētos kaimiņus un ievietojiet tos rindā.

7. darbība: Noņemiet 4. mezglu no rindas priekšpuses un apmeklējiet neapmeklētos kaimiņus un ievietojiet tos rindā.
Kā redzams, visi 4. mezgla kaimiņi tiek apmeklēti, tāpēc pārejiet uz nākamo mezglu, kas atrodas rindas priekšpusē.

Noņemiet mezglu 4 no rindas priekšpuses un apmeklējiet neapmeklētos kaimiņus un ievietojiet tos rindā.

Noņemiet 4. mezglu no rindas priekšpuses un apmeklējiet neapmeklētos kaimiņus un ievietojiet tos rindā.

Tagad rinda kļūst tukša, tāpēc pārtrauciet šo iterācijas procesu.

BFS ieviešana grafikam, izmantojot blakus esošo sarakstu:

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, vektors & apmeklēts) { // Izveidojiet rindu BFS rindai q;  // Atzīmēt pašreizējo mezglu kā apmeklētu un ievietojiet to apmeklējumu rindā [startNode] = true;  q.push(startNode);  // Atkārtojiet rindu, kamēr (!q.empty()) { // Atvienojiet virsotni no rindas un izdrukājiet to 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() { // Virsotņu skaits grafā int virsotnes = 5;  // Grafika vektora blakus esošo sarakstu attēlojums> adjList(virsotnes);  // Pievienot grafikam malas addEdge(adjList, 0, 1);  addEdge(adjList, 0, 2);  addEdge(adjList, 1, 3);  addEdge(adjList, 1, 4);  addEdge(adjList, 2, 4);  // Atzīmēt visas virsotnes kā neapmeklētu vektoru apmeklēts(virsotnes, false);  // Veikt BFS šķērsošanu, sākot no virsotnes 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->dati = dati;  newNode->next = NULL;  atgriezties newNode; } // Funkcija malas pievienošanai grafikam void addEdge(struct Node* adjList[], int u, int v) { struct Node* newNode = createNode(v);  newNode->next = adjList[u];  adjList[u] = jaunsMezgls; } // Funkcija platuma pirmās meklēšanas veikšanai grafikā // attēlota, izmantojot blakus esošo sarakstu void bfs(struct Node* adjList[], int virsotnes, int startNode, int apmeklēja[]) { // Izveidot rindu BFS int rindai[ MAX_VERTICES];  int priekšā = 0, aizmugurē = 0;  // Atzīmēt pašreizējo mezglu kā apmeklētu un ievietojiet to apmeklētajā rindā [startNode] = 1;  rinda [aizmugure++] = startNode;  // Iterēt pa rindu, kamēr (priekšpuse != aizmugure) { // Ieslēgt virsotni no rindas un izdrukāt to int currentNode = queue[front++];  printf('%d ', currentNode);  // Iegūt visas atskaitītās virsotnes blakus esošās virsotnes // pašreizējaisNode Ja blakus esošais nav apmeklēts, // tad atzīmējiet to kā apmeklētu un ievietojiet to rindā struct Node* temp = adjList[pašreizējaisMezgls];  while (temp != NULL) { int kaimiņš = temp-> dati;  if (!apmeklēja[kaimiņš]) {apmeklēja[kaimiņš] = 1;  rinda [aizmugure++] = kaimiņš;  } temp = temp->nākamais;  } } } int main() { // Virsotņu skaits grafā int virsotnes = 5;  // Grafa struktūras blakus saraksta attēlojums Node* adjList[virsotnes];  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('unchecked') Graph(int virsotnes) { this.vertices = virsotnes;  adjList = jauns LinkedList[virsotnes];  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 rinda = jauns LinkedList();  Būla [] apmeklēja = jauns Būla [virsotnes];  // Atzīmēt pašreizējo mezglu kā apmeklētu un ievietojiet to apmeklējumu rindā [startNode] = true;  queue.add(startNode);  // Atkārtojiet rindu, kamēr (!queue.isEmpty()) { // Atvienojiet virsotni no rindas un izdrukājiet to int currentNode = queue.poll();  System.out.print(currentNode + ' ');  // Iegūt visas blakus esošās derindotās // virsotnes currentNode virsotnes Ja blakus esošais // nav apmeklēts, tad atzīmējiet to kā apmeklētu un // ievietojiet to rindā (int kaimiņš : adjList[pašreizējaisNode]) { if (!visited[neighbor] ) {apmeklēja[kaimiņš] = patiess;  rinda.pievienot(kaimiņš);  } } } } } public class Main { public static void main(String[] args) { // Grafa virsotņu skaits int virsotnes = 5;  // Izveidot grafiku Graph graph = new Graph(vertices);  // Grafa grafam pievieno malas.addEdge(0, 1);  graph.addEdge(0, 2);  graph.addEdge(1, 3);  graph.addEdge(1, 4);  graph.addEdge(2, 4);  // Veikt BFS šķērsošanu, sākot no virsotnes 0 System.out.print( 'Platuma pirmā apbraukšana, sākot no virsotnes 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 virsotnes) { this.vertices = virsotnes;  adjList = jauns saraksts [ virsotnes ];  for (int i = 0; i< vertices; ++i)  adjList[i] = new List ();  } // Funkcija malas pievienošanai grafikam public void AddEdge(int u, int v) { adjList[u].Add(v); } // Funkcija, lai grafikā veiktu pirmo platumu meklēšanu // attēlota, izmantojot blakus esošo sarakstu public void BFS(int startNode) { // Izveidot rindu BFS rindai rinda = jauna rinda ();  bool[] apmeklēja = jauns bool[virsotnes];  // Atzīmēt pašreizējo mezglu kā apmeklētu un ievietojiet to apmeklējumu rindā [startNode] = true;  rinda.Enqueue(startNode);  // Atkārtojiet rindu, kamēr (rinda.Skaits != 0) { // Atvienojiet virsotni no rindas un izdrukājiet to int currentNode = queue.Dequeue();  Console.Write(currentNode + ' ');  // Iegūt visas blakus esošās derindas virsotnes // virsotne currentNode Ja blakus esošais // nav apmeklēts, tad atzīmējiet to kā apmeklētu un // ievietojiet to rindā foreach(int kaimiņš in adjList[currentNode]) { if (!visited[neighbor] ) {apmeklēja[kaimiņš] = patiess;  rinda.Rinda(kaimiņš);  } } } } } class MainClass { public static void Main(string[] args) { // Grafa virsotņu skaits int virsotnes = 5;  // Izveidot grafiku Graph graph = new Graph(vertices);  // Grafa grafikam pievieno malas.PievienotEdge(0, 1);  grafiks.PievienotEdge(0, 2);  grafiks.PievienotEdge(1, 3);  grafiks.PievienotEdge(1, 4);  grafiks.PievienotEdge(2, 4);  // Veikt BFS šķērsošanu, sākot no virsotnes 0 Console.Write( 'Platuma pirmā apbraukšana, sākot no virsotnes 0: ');  grafiks.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);>
Izvade 
Breadth First Traversal starting from vertex 0: 0 1 2 3 4>

Laika sarežģītība: O(V+E), kur V ir mezglu skaits un E ir malu skaits.
Palīgtelpa: O(V)

Platuma pirmās meklēšanas (BFS) algoritma sarežģītības analīze:

BFS algoritma laika sarežģītība: O(V + E)

  • BFS izpēta visas grafa virsotnes un malas. Sliktākajā gadījumā tas vienu reizi apmeklē katru virsotni un malu. Tāpēc BFS laika sarežģītība ir O(V + E), kur V un E ir virsotņu un šķautņu skaits dotajā grafā.

BFS algoritma telpas sarežģītība: O(V)

  • BFS izmanto rindu, lai izsekotu virsotnēm, kuras jāapmeklē. Sliktākajā gadījumā rindā var būt visas grafa virsotnes. Tāpēc BFS telpas sarežģītība ir O(V), kur V un E ir virsotņu un malu skaits dotajā grafā.

BFS pielietojumi grafikos:

BFS ir dažādi pielietojumi grafu teorijā un datorzinātnēs, tostarp:

  • Īsākā ceļa atrašana: BFS var izmantot, lai atrastu īsāko ceļu starp diviem mezgliem nesvērtā grafikā. Sekojot katra mezgla vecākam pārvietošanās laikā, var rekonstruēt īsāko ceļu.
  • Cikla noteikšana: BFS var izmantot, lai noteiktu ciklus grafikā. Ja šķērsošanas laikā mezgls tiek apmeklēts divas reizes, tas norāda uz cikla klātbūtni.
  • Savienotie komponenti: BFS var izmantot, lai grafikā identificētu savienotos komponentus. Katrs savienotais komponents ir mezglu kopums, ko var sasniegt viens no otra.
  • Topoloģiskā šķirošana: BFS var izmantot, lai veiktu topoloģisko šķirošanu virzītā acikliskā grafā (DAG). Topoloģiskā šķirošana sakārto mezglus lineārā secībā tā, ka jebkurai malai (u, v) u secībā parādās pirms v.
  • Bināro koku līmeņu secības šķērsošana: BFS var izmantot, lai veiktu binārā koka līmeņa secības šķērsošanu. Šī šķērsošana apmeklē visus mezglus vienā līmenī, pirms pāriet uz nākamo līmeni.
  • Tīkla maršrutēšana: BFS var izmantot, lai atrastu īsāko ceļu starp diviem tīkla mezgliem, padarot to noderīgu datu pakešu maršrutēšanai tīkla protokolos.

Problēmas ar platuma pirmo meklēšanu vai diagrammas BFS:

Jā nē

Problēmas

Prakse
1. Atrodiet noteiktā mezgla līmeni nevirzītā grafikā Saite
2. Samaziniet maksimālo blakus esošo atšķirību ceļā no augšējās kreisās puses uz apakšējo labo pusi Saite
10. Pārbaudiet, vai dotās Matricas galamērķis ir sasniedzams ar nepieciešamajām šūnu vērtībām Saite

Bieži uzdotie jautājumi par diagrammas meklēšanu pirmajā platumā (BFS):

Jautājums 1: Kas ir BFS un kā tas darbojas?

Atbilde: BFS ir grafika šķērsošanas algoritms, kas sistemātiski pēta grafiku, apmeklējot visas virsotnes noteiktā līmenī, pirms pāriet uz nākamo līmeni. Tas sākas no sākuma virsotnes, ievieto to rindā un atzīmē to kā apmeklētu. Pēc tam tas no rindas noņem virsotni, apmeklē to un ierindo rindā visus savus neapmeklētos kaimiņus. Šis process turpinās, līdz rinda ir tukša.

2. jautājums: Kādi ir BFS pielietojumi?

Atbilde: BFS ir dažādas lietojumprogrammas, tostarp īsākā ceļa atrašana nesvērtā grafikā, ciklu noteikšana grafikā, virzīta acikliska grafika (DAG) topoloģiskā šķirošana, saistīto komponentu atrašana diagrammā un tādu mīklu risināšana kā labirinti un Sudoku.

3. jautājums: Kāda ir BFS laika sarežģītība?

Atbilde: BFS laika sarežģītība ir O(V + E), kur V ir virsotņu skaits un E ir grafa malu skaits.

4. jautājums: Kāda ir BFS kosmosa sarežģītība?

Atbilde: BFS telpas sarežģītība ir O(V), jo tā izmanto rindu, lai sekotu līdzi virsotnēm, kuras jāapmeklē.

5. jautājums: Kādas ir BFS izmantošanas priekšrocības?

Atbilde: BFS ir vienkārši ieviešams un efektīvs, lai atrastu īsāko ceļu nesvērtā grafikā. Tas arī garantē, ka tiek apmeklētas visas grafa virsotnes.

binārais koks java

Saistītie raksti:

  • Jaunākie raksti par BFS
  • Pirmā dziļuma šķērsošana
  • Platuma pirmās šķērsošanas pielietojumi
  • Pirmās dziļuma meklēšanas pielietojumi
  • Laiks un telpa, pirmā meklēšanas platuma sarežģītība (BFS)