logo

TechCodeview

První vyhledávání šířky nebo BFS pro graf

První vyhledávání do šířky (BFS) je základní algoritmus procházení grafu . Zahrnuje návštěvu všech připojených uzlů grafu způsobem úroveň po úrovni. V tomto článku se podíváme na koncept BFS a jak jej lze efektivně aplikovat na grafy

Obsah

První vyhledávání šířky (BFS) pro graf:

První vyhledávání do šířky (BFS) je algoritmus procházení grafu, který zkoumá všechny vrcholy v grafu v aktuální hloubce, než se přesune k vrcholům na další úrovni hloubky. Začíná v určeném vrcholu a navštěvuje všechny své sousedy, než se přesune na další úroveň sousedů. BFS se běžně používá v algoritmech pro hledání cest, připojených komponent a problémů s nejkratšími cestami v grafech.



Vztah mezi BFS pro graf a BFS pro strom:

Breadth-First Traversal (BFS) pro graf je podobný grafu Přechod stromu do šířky .

Jediný háček je v tom, že na rozdíl od stromy , grafy může obsahovat cykly, takže se můžeme znovu dostat ke stejnému uzlu. Abychom se vyhnuli zpracování uzlu více než jednou, rozdělujeme vrcholy do dvou kategorií:

  • Navštívil a
  • Nenavštíveno.

K označení navštívených vrcholů se používá booleovské navštívené pole. Pro jednoduchost se předpokládá, že všechny vrcholy jsou dosažitelné z počátečního vrcholu. BFS používá A Breadth First Search (BFS) pro grafový algoritmus:

java rovná se

Pojďme diskutovat o algoritmu pro BFS:

  1. Inicializace: Zařaďte počáteční uzel do fronty a označte jej jako navštívený.
  2. Průzkum: Zatímco fronta není prázdná:
    • Vyřaďte uzel z fronty a navštivte jej (např. vytiskněte jeho hodnotu).
    • Pro každého nenavštíveného souseda vyřazeného uzlu:
      • Zařaďte souseda do fronty.
      • Označte souseda jako navštíveného.
  3. Ukončení: Opakujte krok 2, dokud není fronta prázdná.

Tento algoritmus zajišťuje, že všechny uzly v grafu jsou navštíveny v první řadě, počínaje počátečním uzlem.

Jak funguje algoritmus BFS?

Počínaje kořenem jsou nejprve navštíveny všechny uzly na určité úrovni a poté se procházejí uzly další úrovně, dokud nejsou navštíveny všechny uzly.

K tomu se používá fronta. Všechny sousední nenavštívené uzly aktuální úrovně se zařadí do fronty a uzly aktuální úrovně jsou označeny jako navštívené a vyřazené z fronty.

Ilustrace:

Pojďme pochopit fungování algoritmu pomocí následujícího příkladu.

Krok 1: Zpočátku jsou fronta a navštívená pole prázdná.

Fronta a navštívená pole jsou zpočátku prázdná.

Krok 2: Zařadit uzel 0 do fronty a označit jej jako navštívený.

Zařadit uzel 0 do fronty a označit jej jako navštívený.

Zařadit uzel 0 do fronty a označit jej jako navštívený.

Krok 3: Odeberte uzel 0 z přední části fronty a navštivte nenavštívené sousedy a zařaďte je do fronty.

Odeberte uzel 0 z přední části fronty a navštívili nenavštívené sousedy a vložte je do fronty.

Odeberte uzel 0 z přední části fronty a navštívili nenavštívené sousedy a vložte je do fronty.

Krok 4: Odeberte uzel 1 z přední části fronty a navštivte nenavštívené sousedy a zařaďte je do fronty.

Odeberte uzel 1 z přední části fronty a navštívili nenavštívené sousedy a zatlačte

Odeberte uzel 1 z přední části fronty a navštívili nenavštívené sousedy a zatlačte

Krok 5: Odstraňte uzel 2 z přední části fronty a navštivte nenavštívené sousedy a zařaďte je do fronty.

Odstraňte uzel 2 z přední části fronty a navštivte nenavštívené sousedy a zařaďte je do fronty.

Odstraňte uzel 2 z přední části fronty a navštivte nenavštívené sousedy a zařaďte je do fronty.

Krok 6: Odstraňte uzel 3 z přední části fronty a navštivte nenavštívené sousedy a zařaďte je do fronty.
Jak vidíme, že jsou navštíveni všichni sousedé uzlu 3, přesuňte se na další uzel, který je v přední části fronty.

Odstraňte uzel 3 z přední části fronty a navštivte nenavštívené sousedy a zařaďte je do fronty.

Odstraňte uzel 3 z přední části fronty a navštivte nenavštívené sousedy a zařaďte je do fronty.

Kroky 7: Odstraňte uzel 4 z přední části fronty a navštivte nenavštívené sousedy a zařaďte je do fronty.
Jak vidíme, že jsou navštíveni všichni sousedé uzlu 4, přesuňte se na další uzel, který je v přední části fronty.

Odstraňte uzel 4 z přední části fronty a navštivte nenavštívené sousedy a zařaďte je do fronty.

Odstraňte uzel 4 z přední části fronty a navštivte nenavštívené sousedy a zařaďte je do fronty.

Nyní se fronta vyprázdní, takže ukončete tento proces iterace.

Implementace BFS pro Graph pomocí 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, vector & navštívil) { // Vytvořte frontu pro frontu BFS q;  // Označí aktuální uzel jako navštívený a zařadí jej do fronty[startNode] = true;  q.push(startNode);  // Iterace přes frontu while (!q.empty()) { // Dequeue vertex from queue and print it 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() { // Počet vrcholů v grafu int vrcholy = 5;  // Reprezentace seznamu sousedství vektoru grafu> adjList(vertices);  // Přidání hran do grafu addEdge(adjList, 0, 1);  addEdge(adjList, 0, 2);  addEdge(adjList, 1, 3);  addEdge(adjList, 1, 4);  addEdge(adjList, 2, 4);  // Označí všechny vrcholy jako nenavštívené vektory navštíveno(vrcholy, nepravda);  // Provede BFS traversal počínaje vrcholem 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;  novyUzel->dalsi = NULL;  return newNode; } // Funkce pro přidání hrany do grafu void addEdge(struct Node* adjList[], int u, int v) { struct Node* newNode = createNode(v);  newNode->next = adjList[u];  adjList[u] = novýUzel; } // Funkce pro provedení prvního vyhledávání šířky v grafu // reprezentovaném pomocí seznamu sousedství void bfs(struct Node* adjList[], int vertices, int startNode, int visit[]) { // Vytvořte frontu pro BFS int queue[ MAX_VERTICES];  vnitřní přední = 0, zadní = 0;  // Označí aktuální uzel jako navštívený a zařadí jej do fronty[startNode] = 1;  queue[zadní++] = startNode;  // Iterace přes frontu while (front != zadní) { // Dequeue vertex from queue and print it int currentNode = queue[front++];  printf('%d ', aktuálníUzel);  // Získání všech sousedních vrcholů vyřazeného vrcholu // currentNode Pokud sousední nebyl navštíven, // pak jej označte jako navštívený a zařaďte jej do fronty struct Node* temp = adjList[currentNode];  while (temp != NULL) { int soused = temp->data;  if (!navštívil[soused]) { navštívil[soused] = 1;  fronta[zadní++] = soused;  } temp = temp->dalsi;  } } } int main() { // Počet vrcholů v grafu int vrcholy = 5;  // Reprezentace seznamu sousedství struktury grafu 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; }>
Jáva 
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[vrcholy];  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 fronta = new LinkedList();  boolean[] navštíveno = nový boolean[vrcholy];  // Označí aktuální uzel jako navštívený a zařadí jej do fronty[startNode] = true;  queue.add(startNode);  // Iterace přes frontu while (!queue.isEmpty()) { // Vyřadí vrchol z fronty a vytiskne jej int currentNode = queue.poll();  System.out.print(currentNode + ' ');  // Získání všech sousedních vrcholů vyřazeného // vertex currentNode Pokud soused nebyl // navštíven, pak jej označte jako navštívený a // zařaďte jej do fronty pro (int soused : adjList[currentNode]) { if (!visited[neighbor] ) { navštíveno[soused] = true;  fronta.add(soused);  } } } } } public class Main { public static void main(String[] args) { // Počet vrcholů v grafu int vertices = 5;  // Vytvoření grafu Graph graph = new Graph(vertices);  // Přidání hran do grafu graph.addEdge(0, 1);  graph.addEdge(0, 2);  graph.addEdge(1, 3);  graph.addEdge(1, 4);  graph.addEdge(2, 4);  // Provede BFS traversal počínaje vrcholem 0 System.out.print( 'Breadth First Traversal začínající od vrcholu 0: ');  graf.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 = nový seznam [ vrcholy ];  for (int i = 0; i< vertices; ++i)  adjList[i] = new List ();  } // Funkce pro přidání hrany do grafu public void AddEdge(int u, int v) { adjList[u].Add(v); } // Funkce pro provedení Breadth First Search na grafu // reprezentovaná pomocí seznamu sousedství public void BFS(int startNode) { // Vytvoření fronty pro BFS Queue fronta = nová fronta ();  bool[] navštíveno = nový bool[vrcholy];  // Označí aktuální uzel jako navštívený a zařadí jej do fronty[startNode] = true;  queue.Enqueue(startNode);  // Iterace přes frontu while (queue.Count != 0) { // Vyřadí vrchol z fronty a vytiskne jej int currentNode = queue.Dequeue();  Console.Write(currentNode + ' ');  // Získání všech sousedních vrcholů vyřazeného // vrcholu currentNode Pokud soused nebyl // navštíven, pak jej označte jako navštívený a // zařaďte jej do fronty foreach(int soused v adjList[currentNode]) { if (!visited[neighbor] ) { navštíveno[soused] = true;  fronta.Enqueue(soused);  } } } } } class MainClass { public static void Main(string[] args) { // Počet vrcholů v grafu int vertices = 5;  // Vytvoření grafu Graph graph = new Graph(vertices);  // Přidání hran do grafu grafu.AddEdge(0, 1);  graph.AddEdge(0, 2);  graph.AddEdge(1, 3);  graph.AddEdge(1, 4);  graph.AddEdge(2, 4);  // Provede BFS průchod od vrcholu 0 Console.Write( 'Breadth First Traversal od vrcholu 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);>
Výstup 
Breadth First Traversal starting from vertex 0: 0 1 2 3 4>

Časová náročnost: O(V+E), kde V je počet uzlů a E je počet hran.
Pomocný prostor: O(V)

Analýza složitosti algoritmu BFS (Breadth-First Search):

Časová složitost algoritmu BFS: O(V + E)

  • BFS prozkoumá všechny vrcholy a hrany v grafu. V nejhorším případě navštíví každý vrchol a hranu jednou. Časová složitost BFS je tedy O(V + E), kde V a E je počet vrcholů a hran v daném grafu.

Prostorová složitost algoritmu BFS: O(V)

  • BFS používá frontu ke sledování vrcholů, které je třeba navštívit. V nejhorším případě může fronta obsahovat všechny vrcholy v grafu. Prostorová složitost BFS je tedy O(V), kde V a E jsou počty vrcholů a hran v daném grafu.

Aplikace BFS v grafech:

BFS má různé aplikace v teorii grafů a informatiky, včetně:

  • Hledání nejkratší cesty: BFS lze použít k nalezení nejkratší cesty mezi dvěma uzly v neváženém grafu. Sledováním rodiče každého uzlu během průchodu lze rekonstruovat nejkratší cestu.
  • Detekce cyklu: BFS lze použít k detekci cyklů v grafu. Pokud je uzel během průchodu navštíven dvakrát, znamená to přítomnost cyklu.
  • Připojené komponenty: BFS lze použít k identifikaci připojených komponent v grafu. Každá připojená komponenta je sada uzlů, které jsou navzájem dostupné.
  • Topologické řazení: BFS lze použít k provádění topologického třídění na řízeném acyklickém grafu (DAG). Topologické řazení uspořádá uzly v lineárním pořadí tak, že pro jakoukoli hranu (u, v) se u objeví v pořadí před v.
  • Procházení pořadí binárních stromů podle úrovně: BFS lze použít k provedení procházení binárního stromu podle pořadí úrovně. Toto procházení navštíví všechny uzly na stejné úrovni, než se přesune na další úroveň.
  • Směrování sítě: BFS lze použít k nalezení nejkratší cesty mezi dvěma uzly v síti, což je užitečné pro směrování datových paketů v síťových protokolech.

Problémy s Breadth First Search nebo BFS pro graf:

Ano ne

Problémy

Praxe
1. Najděte úroveň daného uzlu v neorientovaném grafu Odkaz
2. Minimalizujte maximální sousední rozdíl v cestě z levého horního rohu do pravého dolního rohu Odkaz
10. Zkontrolujte, zda je cíl dané matice dosažitelný s požadovanými hodnotami buněk Odkaz

Nejčastější dotazy týkající se prvního vyhledávání šířky (BFS) pro graf:

Otázka 1: Co je BFS a jak funguje?

Odpovědět: BFS je algoritmus procházení grafů, který systematicky zkoumá graf návštěvou všech vrcholů na dané úrovni, než přejde na další úroveň. Začne od počátečního vrcholu, zařadí jej do fronty a označí jej jako navštívený. Poté vyřadí z fronty vrchol, navštíví jej a zařadí všechny jeho nenavštívené sousedy do fronty. Tento proces pokračuje, dokud není fronta prázdná.

Otázka 2: Jaké jsou aplikace BFS?

Odpovědět: BFS má různé aplikace, včetně hledání nejkratší cesty v neváženém grafu, detekce cyklů v grafu, topologického třídění orientovaného acyklického grafu (DAG), hledání spojených komponent v grafu a řešení hádanek, jako jsou bludiště a sudoku.

Otázka 3: Jaká je časová složitost BFS?

Odpovědět: Časová složitost BFS je O(V + E), kde V je počet vrcholů a E je počet hran v grafu.

Otázka 4: Jaká je vesmírná složitost BFS?

Odpovědět: Prostorová složitost BFS je O(V), protože používá frontu ke sledování vrcholů, které je třeba navštívit.

Otázka 5: Jaké jsou výhody používání BFS?

Odpovědět: BFS se snadno implementuje a je efektivní pro nalezení nejkratší cesty v neváženém grafu. Zaručuje také, že budou navštíveny všechny vrcholy v grafu.

Související články:

  • Nedávné články o BFS
  • Hloubka první průchod
  • Aplikace Breadth First Traversal
  • Aplikace Depth First Search
  • Časová a prostorová složitost prvního vyhledávání šířky (BFS)