logo

TechCodeview

Leveys ensin -haku tai BFS kaaviolle

Breadth First Search (BFS) on perusasia graafin läpikulkualgoritmi . Se sisältää vierailun kaikissa kaavion yhdistetyissä solmuissa tasoittain. Tässä artikkelissa tarkastelemme käsitettä BFS ja kuinka sitä voidaan soveltaa kaavioihin tehokkaasti

Sisällysluettelo



Leveys ensin -haku (BFS) kaaviolle:

Breadth First Search (BFS) on graafin läpikulkualgoritmi, joka tutkii kaikki graafin kärjet nykyisellä syvyydellä ennen siirtymistä seuraavan syvyystason kärkipisteisiin. Se alkaa määritetystä kärjestä ja vierailee kaikissa naapureissaan ennen siirtymistään seuraavalle naapuritasolle. BFS Käytetään yleisesti algoritmeissa polunhakua, yhdistettyjä komponentteja ja lyhimmän polun ongelmia kuvaajien yhteydessä.

BFS for Graph ja BFS for Tree välinen suhde:

Leveys-First Traversal (BFS) kuvaajalle on samanlainen kuin Leveys-ensimmäinen puun läpikulku .

Ainoa saalis tässä on se, toisin kuin puita , kaavioita voi sisältää jaksoja, joten voimme päästä samaan solmuun uudelleen. Jotta solmua ei käsitellä useammin kuin kerran, jaamme kärjet kahteen luokkaan:



matka mutta
  • Vieraillut ja
  • Ei vieraillut.

Boolen vierailtua taulukkoa käytetään vierailtujen huippujen merkitsemiseen. Yksinkertaisuuden vuoksi oletetaan, että kaikki kärjet ovat saavutettavissa aloituspisteestä. BFS käyttää a Leveys ensin haku (BFS) kaavioalgoritmille:

Keskustellaan BFS:n algoritmista:

  1. Alustus: Jonota aloitussolmu jonoon ja merkitse se käydyksi.
  2. Tutkimus: Vaikka jono ei ole tyhjä:
    • Poista solmu jonosta ja vieraile siinä (esim. tulosta sen arvo).
    • Jokaiselle jonosta poistetun solmun vierailemattomalle naapurille:
      • Jonota naapuri jonoon.
      • Merkitse naapuri vierailluksi.
  3. Irtisanominen: Toista vaihetta 2, kunnes jono on tyhjä.

Tämä algoritmi varmistaa, että kaikissa graafin solmuissa käydään leveys-ensimmäisellä tavalla, alkaen aloitussolmusta.



Kuinka BFS-algoritmi toimii?

Juuresta alkaen käydään ensin kaikissa tietyn tason solmuissa ja sitten seuraavan tason solmut kulkevat, kunnes kaikki solmut ovat käyneet.

Tätä varten käytetään jonoa. Kaikki vierekkäiset nykyisen tason vierailemattomat solmut työnnetään jonoon ja nykyisen tason solmut merkitään vierailtuiksi ja pompataan jonosta.

Kuva:

Ymmärrämme algoritmin toimintaa seuraavan esimerkin avulla.

Vaihe 1: Aluksi jono ja vierailtu taulukot ovat tyhjiä.

Jono ja vierailtu taulukot ovat aluksi tyhjiä.

Vaihe2: Työnnä solmu 0 jonoon ja merkitse se käydyksi.

Työnnä solmu 0 jonoon ja merkitse se käydyksi.

Työnnä solmu 0 jonoon ja merkitse se käydyksi.

Vaihe 3: Poista solmu 0 jonon edestä ja vieraile vierailemattomissa naapureissa ja työnnä heidät jonoon.

Poista solmu 0 jonon edestä ja vieraili vierailemattomissa naapureissa ja työnnä jonoon.

Poista solmu 0 jonon edestä ja vieraili vierailemattomissa naapureissa ja työnnä jonoon.

Vaihe 4: Poista solmu 1 jonon edestä ja vieraile vierailemattomissa naapureissa ja työnnä heidät jonoon.

Poista solmu 1 jonon etuosasta ja vieraili vierailemattomissa naapureissa ja paina

Poista solmu 1 jonon edestä ja vieraili vierailemattomissa naapureissa ja paina

Vaihe 5: Poista solmu 2 jonon edestä ja vieraile vierailemattomissa naapureissa ja työnnä heidät jonoon.

Poista solmu 2 jonon edestä ja vieraile vierailemattomissa naapureissa ja työnnä heidät jonoon.

Poista solmu 2 jonon edestä ja vieraile vierailemattomissa naapureissa ja työnnä heidät jonoon.

Vaihe 6: Poista solmu 3 jonon edestä ja vieraile vierailemattomissa naapureissa ja työnnä heidät jonoon.
Kuten voimme nähdä, että jokaisessa solmun 3 naapurissa käydään, siirry seuraavaan solmuun, jotka ovat jonon edessä.

Poista solmu 3 jonon edestä ja vieraile vierailemattomissa naapureissa ja työnnä heidät jonoon.

Poista solmu 3 jonon edestä ja vieraile vierailemattomissa naapureissa ja työnnä heidät jonoon.

Vaiheet 7: Poista solmu 4 jonon edestä ja vieraile vierailemattomissa naapureissa ja työnnä heidät jonoon.
Kuten voimme nähdä, että jokaisessa solmun 4 naapurissa käydään, siirry seuraavaan solmuun, joka on jonon edessä.

Poista solmu 4 jonon edestä ja vieraile vierailemattomissa naapureissa ja työnnä se jonoon.

Poista solmu 4 jonon edestä ja vieraile vierailemattomissa naapureissa ja työnnä heidät jonoon.

Nyt jonosta tulee tyhjä, joten lopeta nämä iterointiprosessit.

BFS for Graph -sovelluksen käyttöönotto vierekkäisyysluettelon avulla:

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 aloitussolmu, vektori & vieraili) { // Luo jono BFS-jonolle q;  // Merkitse nykyinen solmu vierailluksi ja lisää se vieraillun jonoon[startSolmu] = true;  q.push(aloitussolmu);  // Iteroi jonon yli, kun (!q.empty()) { // Poista kärki jonosta ja tulosta se 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>& adjLista, int u, int v) { adjLista[u].push_back(v); } int main() { // Kuvaajan kärkien lukumäärä int vertices = 5;  // Graafivektorin vierekkäisyysluetteloesitys> adjList(vertices);  // Reunojen lisääminen kuvaajaan addEdge(adjList, 0, 1);  addEdge(adjList, 0, 2);  addEdge(adjList, 1, 3);  addEdge(adjList, 1, 4);  addEdge(adjList, 2, 4);  // Merkitse kaikki kärjet vierailemattomiksi vektoreiksi vierailtu(vertices, false);  // Suorita BFS-läpikulku alkaen kärjestä 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;  uusiSolmu->seuraava = NULL;  palauttaa newNode; } // Funktio graafiin reunan lisäämiseksi void addEdge(struct Node* adjList[], int u, int v) { struct Node* newNode = createNode(v);  uusiSolmu->seuraava = adjLista[u];  adjList[u] = uusiSolmu; } // Leveyshaku kaaviossa // esitetty vierekkäisyysluettelolla void bfs(struct Node* adjList[], int vertices, int aloitussolmu, int vieraili[]) { // Luo jono BFS int -jonolle[ MAX_VERTICES];  int edessä = 0, takana = 0;  // Merkitse nykyinen solmu vierailluksi ja lisää se vieraillun jonoon [aloitussolmu] = 1;  jono[taka++] = aloitussolmu;  // Iteroi jonon yli, kun (etu != taka) { // Pura kärki jonosta ja tulosta se int currentSolmu = jono[etu++];  printf('%d ', currentNode);  // Hae poistetun kärjen kaikki viereiset kärjet // nykyinenSolmu Jos viereisessä ei ole vieraillut, // merkitse se vierailluksi ja jonoon se struct Solmu* temp = adjList[nykyinenSolmu];  while (temp != NULL) { int naapuri = temp->data;  if (!vieraillut[naapuri]) { vieraili[naapuri] = 1;  jono[taka++] = naapuri;  } temp = temp->seuraava;  } } } int main() { // Kuvaajan kärkien lukumäärä int vertices = 5;  // Graafirakenteen vierekkäisyyslistaesitys Solmu* adjLista[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('tarkistamaton') Graph(int vertices) { this.vertices = vertices;  adjList = uusi 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 queue = new LinkedList();  boolean[] vieraili = uusi boolean[vertices];  // Merkitse nykyinen solmu vierailluksi ja lisää se vieraillun jonoon[startSolmu] = true;  queue.add(aloitussolmu);  // Iteroi jonon yli while (!queue.isEmpty()) { // Pura kärki jonosta ja tulosta se int currentNode = queue.poll();  System.out.print(currentNode + ' ');  // Hae jonosta poistetun // vertexin currentSolmu kaikki vierekkäiset kärjet Jos viereisessä ei // ole vierailtu, merkitse se vierailluksi ja // jonoon se kohteelle (int naapuri : adjList[nykyinenSolmu]) { if (!vieraillut[naapuri] ) { vieraili[naapuri] = tosi;  queue.add(naapuri);  } } } } } public class Main { public static void main(String[] args) { // Kuvaajan kärkien lukumäärä int vertices = 5;  // Luo graafi Graph graph = new Graph(vertices);  // Reunojen lisääminen graafiin graph.addEdge(0, 1);  graph.addEdge(0, 2);  graph.addEdge(1, 3);  graph.addEdge(1, 4);  graph.addEdge(2, 4);  // Suorita BFS-läpikulku pisteestä 0 alkaen System.out.print( 'Leveyden ensimmäinen läpikulku pisteestä 0: ');  graph.bfs(0);  } }>
Python 3 
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 = uusi lista [ vertices ];  for (int i = 0; i< vertices; ++i)  adjList[i] = new List ();  } // Funktio reunan lisäämiseksi graafiin public void LisääEdge(int u, int v) { adjLista[u].Add(v); } // Toiminto leveyshaun suorittamiseksi kaaviossa // vierekkäisyysluettelon avulla esitetty public void BFS(int startNode) { // Luo jono BFS-jonolle jono = uusi jono ();  bool[] vieraili = uusi bool[vertices];  // Merkitse nykyinen solmu vierailluksi ja lisää se vieraillun jonoon[startSolmu] = true;  jono.Enqueue(aloitussolmu);  // Iteroi jonon yli while (queue.Count != 0) { // Pura kärki jonosta ja tulosta se int currentNode = queue.Dequeue();  Console.Write(currentNode + ' ');  // Hae jonosta poistetun // vertex currentSolmu kaikki vierekkäiset kärjet Jos viereisessä ei ole // vierailtu, merkitse se vierailluksi ja // jonoon se foreach(int naapuri in adjList[currentSolmu]) { if (!visited[naapuri] ) { vieraili[naapuri] = tosi;  jono.Enqueue(naapuri);  } } } } } class MainClass { public static void Main(string[] args) { // Kuvaajan kärkien lukumäärä int vertices = 5;  // Luo graafi Graph graph = new Graph(vertices);  // Lisää reunoja graafin graafiin.AddEdge(0, 1);  graph.AddEdge(0, 2);  graph.AddEdge(1, 3);  graph.AddEdge(1, 4);  graph.AddEdge(2, 4);  // Suorita BFS-läpikulku huipusta 0 alkaen Console.Write( 'Leveys ensimmäinen läpikulku pisteestä 0: ');  kaavio.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);>
Lähtö 
Breadth First Traversal starting from vertex 0: 0 1 2 3 4>

Aika monimutkaisuus: O(V+E), jossa V on solmujen lukumäärä ja E on reunojen lukumäärä.
Aputila: O(V)

Leveyshakualgoritmin (BFS) monimutkaisuusanalyysi:

BFS-algoritmin aikamonimutkaisuus: O(V + E)

  • BFS tutkii kaikki graafin kärjet ja reunat. Pahimmassa tapauksessa se käy jokaisessa kärjessä ja reunassa kerran. Siksi BFS:n aikamonimutkaisuus on O(V + E), missä V ja E ovat pisteiden ja kulmien lukumäärä annetussa graafissa.

BFS-algoritmin tilan monimutkaisuus: O(V)

  • BFS käyttää jonoa pitääkseen kirjaa pisteistä, joissa täytyy käydä. Pahimmassa tapauksessa jono voi sisältää kaikki graafin kärjet. Siksi BFS:n avaruuden kompleksisuus on O(V), missä V ja E ovat pisteiden ja reunojen lukumäärä annetussa graafissa.

BFS:n sovellukset kaavioissa:

BFS:llä on useita sovelluksia graafiteoriassa ja tietojenkäsittelytieteessä, mukaan lukien:

  • Lyhimmän polun löytö: BFS:ää voidaan käyttää lyhimmän polun löytämiseen painottamattoman graafin kahden solmun välillä. Pitämällä kirjaa kunkin solmun emosta läpikäynnin aikana, lyhin polku voidaan rekonstruoida.
  • Jakson tunnistus: BFS:ää voidaan käyttää syklien havaitsemiseen kaaviossa. Jos solmussa käydään kahdesti läpikäynnin aikana, se osoittaa syklin olemassaolon.
  • Kytketyt komponentit: BFS:n avulla voidaan tunnistaa kytketyt komponentit kaaviossa. Jokainen yhdistetty komponentti on joukko solmuja, jotka voidaan tavoittaa toisistaan.
  • Topologinen lajittelu: BFS:ää voidaan käyttää topologiseen lajitteluun suunnatussa asyklisessä graafissa (DAG). Topologinen lajittelu järjestää solmut lineaariseen järjestykseen siten, että missä tahansa reunassa (u, v) u esiintyy järjestyksessä v:n edessä.
  • Binääripuiden tasojärjestyksen läpikäynti: BFS:ää voidaan käyttää binääripuun tasojärjestyksen läpikulkuun. Tämä läpikulku vierailee kaikissa solmuissa samalla tasolla ennen siirtymistä seuraavalle tasolle.
  • Verkkoreititys: BFS:ää voidaan käyttää lyhimmän polun löytämiseen verkon kahden solmun välillä, mikä tekee siitä hyödyllisen datapakettien reitittämisessä verkkoprotokollassa.

Ongelmia Breadth First -haussa tai kaavion BFS:ssä:

Kyllä ei

Ongelmia

Harjoitella
1. Etsi tietyn solmun taso ohjaamattomasta kuvaajasta Linkki
2. Minimoi suurin vierekkäinen ero polussa ylhäältä vasemmalta oikealle Linkki
10. Tarkista, onko tietyn Matrixin kohde tavoitettavissa vaadituilla soluarvoilla Linkki

Usein kysytyt kysymykset kaavion leveyshakusta (BFS):

Kysymys 1: Mikä on BFS ja miten se toimii?

Vastaus: BFS on graafin läpikulkualgoritmi, joka tutkii systemaattisesti graafia käymällä tietyn tason kaikissa kärjeissä ennen siirtymistä seuraavalle tasolle. Se alkaa aloituspisteestä, asettaa sen jonoon ja merkitsee sen vierailluksi. Sitten se poistaa jonosta kärkipisteen, vierailee siinä ja jonottaa kaikki vierailemattomat naapurit jonoon. Tämä prosessi jatkuu, kunnes jono on tyhjä.

Kysymys 2: Mitkä ovat BFS:n sovellukset?

Vastaus: BFS:llä on useita sovelluksia, kuten lyhimmän polun löytäminen painottamattomasta graafista, syklien havaitseminen kaaviossa, suunnatun asyklisen graafin (DAG) topologinen lajittelu, kaavion yhdistettyjen komponenttien löytäminen ja pulmien, kuten sokkeloiden ja Sudokun, ratkaiseminen.

Kysymys 3: Mikä on BFS:n aikamonimutkaisuus?

Vastaus: BFS:n aikamonimutkaisuus on O(V + E), jossa V on graafin kärkien lukumäärä ja E on graafin reunojen lukumäärä.

Kysymys 4: Mikä on BFS:n avaruuden monimutkaisuus?

Vastaus: BFS:n avaruuden monimutkaisuus on O(V), koska se käyttää jonoa pitääkseen kirjaa pisteistä, joissa täytyy käydä.

Kysymys 5: Mitä etuja BFS:n käytöstä on?

Vastaus: BFS on yksinkertainen toteuttaa ja tehokas lyhimmän polun löytämiseksi painottamattomasta graafista. Se takaa myös sen, että kaikki graafin kärjet käyvät läpi.

lateksi fonttikoot

Aiheeseen liittyvät artikkelit:

  • Viimeisimmät artikkelit BFS:stä
  • Syvyys ensimmäinen läpikulku
  • Breadth First Traversalin sovellukset
  • Ensimmäisen syvyyshaun sovellukset
  • Ajan ja tilan monimutkaisuus Leveys ensin -haku (BFS)