logo

TechCodeview

Wyszukiwanie wszerz lub BFS dla wykresu

Wyszukiwanie wszerz (BFS) jest podstawą algorytm poruszania się po grafie . Polega na odwiedzaniu wszystkich połączonych węzłów grafu poziom po poziomie. W tym artykule przyjrzymy się pojęciu BFS i jak można je skutecznie zastosować do wykresów

Spis treści



Wyszukiwanie wszerz (BFS) wykresu:

Wyszukiwanie wszerz (BFS) to algorytm przechodzenia przez graf, który bada wszystkie wierzchołki grafu na bieżącej głębokości, zanim przejdzie do wierzchołków na następnym poziomie głębokości. Zaczyna się od określonego wierzchołka i odwiedza wszystkich swoich sąsiadów, zanim przejdzie do następnego poziomu sąsiadów. BFS jest powszechnie stosowany w algorytmach wyszukiwania ścieżek, połączonych komponentów i problemów z najkrótszą ścieżką na grafach.

Związek pomiędzy BFS dla wykresu i BFS dla drzewa:

Przechodzenie wszerz (BFS) dla wykresu jest podobne do Przechodzenie drzewa wszerz .

Jedynym haczykiem jest to, że w przeciwieństwie do tego drzewa , wykresy może zawierać cykle, więc możemy ponownie dojść do tego samego węzła. Aby uniknąć wielokrotnego przetwarzania węzła, dzielimy wierzchołki na dwie kategorie:



logika zdań
  • Odwiedziłem i
  • Nie odwiedzony.

Tablica odwiedzanych wartości logicznych służy do oznaczania odwiedzanych wierzchołków. Dla uproszczenia zakłada się, że wszystkie wierzchołki są osiągalne z wierzchołka początkowego. BFS wykorzystuje A Wyszukiwanie wszerz (BFS) algorytmu wykresu:

Omówmy algorytm dla BFS:

  1. Inicjalizacja: Umieść węzeł początkowy w kolejce i oznacz go jako odwiedzony.
  2. Badanie: Chociaż kolejka nie jest pusta:
    • Usuń węzeł z kolejki i odwiedź go (np. wydrukuj jego wartość).
    • Dla każdego nieodwiedzonego sąsiada usuniętego z kolejki węzła:
      • Ustaw sąsiada w kolejce.
      • Oznacz sąsiada jako odwiedzanego.
  3. Zakończenie: Powtarzaj krok 2, aż kolejka będzie pusta.

Algorytm ten gwarantuje, że wszystkie węzły na grafie będą odwiedzane wszerz, zaczynając od węzła początkowego.



Jak działa algorytm BFS?

Zaczynając od korzenia, najpierw odwiedzane są wszystkie węzły na danym poziomie, a następnie przemierzane są węzły następnego poziomu, aż do odwiedzenia wszystkich węzłów.

W tym celu używana jest kolejka. Wszystkie sąsiednie, nieodwiedzone węzły bieżącego poziomu są wypychane do kolejki, a węzły bieżącego poziomu są oznaczane jako odwiedzone i usuwane z kolejki.

Ilustracja:

Przyjrzyjmy się działaniu algorytmu na poniższym przykładzie.

Krok 1: Początkowo kolejka i odwiedzane tablice są puste.

Tablice kolejki i odwiedzane są początkowo puste.

Krok 2: Wciśnij węzeł 0 do kolejki i oznacz go jako odwiedzony.

Wciśnij węzeł 0 do kolejki i oznacz go jako odwiedzony.

Wciśnij węzeł 0 do kolejki i oznacz go jako odwiedzony.

Krok 3: Usuń węzeł 0 z przodu kolejki, odwiedź nieodwiedzonych sąsiadów i wepchnij ich do kolejki.

Usuń węzeł 0 z przodu kolejki, odwiedź nieodwiedzonych sąsiadów i wepchnij do kolejki.

Usuń węzeł 0 z przodu kolejki, odwiedź nieodwiedzonych sąsiadów i wepchnij do kolejki.

Krok 4: Usuń węzeł 1 z przodu kolejki, odwiedź nieodwiedzonych sąsiadów i wepchnij ich do kolejki.

Usuń węzeł 1 z przodu kolejki, odwiedź nieodwiedzonych sąsiadów i naciśnij

Usuń węzeł 1 z przodu kolejki, odwiedź nieodwiedzonych sąsiadów i naciśnij

Krok 5: Usuń węzeł 2 z przodu kolejki, odwiedź nieodwiedzonych sąsiadów i wepchnij ich do kolejki.

Usuń węzeł 2 z przodu kolejki, odwiedź nieodwiedzonych sąsiadów i wepchnij ich do kolejki.

Usuń węzeł 2 z przodu kolejki, odwiedź nieodwiedzonych sąsiadów i wepchnij ich do kolejki.

Krok 6: Usuń węzeł 3 z przodu kolejki, odwiedź nieodwiedzonych sąsiadów i wepchnij ich do kolejki.
Jak widzimy, że odwiedzani są wszyscy sąsiedzi węzła 3, należy zatem przejść do kolejnego węzła znajdującego się na początku kolejki.

if instrukcja Java
Usuń węzeł 3 z przodu kolejki, odwiedź nieodwiedzonych sąsiadów i wepchnij ich do kolejki.

Usuń węzeł 3 z przodu kolejki, odwiedź nieodwiedzonych sąsiadów i wepchnij ich do kolejki.

Kroki 7: Usuń węzeł 4 z przodu kolejki, odwiedź nieodwiedzonych sąsiadów i wepchnij ich do kolejki.
Jak widzimy, że odwiedzani są wszyscy sąsiedzi węzła 4, należy więc przejść do kolejnego węzła, który znajduje się na początku kolejki.

Usuń węzeł 4 z przodu kolejki, odwiedź nieodwiedzonych sąsiadów i wepchnij ich do kolejki.

Usuń węzeł 4 z przodu kolejki, odwiedź nieodwiedzonych sąsiadów i wepchnij ich do kolejki.

Teraz kolejka staje się pusta, więc zakończ proces iteracji.

Implementacja BFS dla Graph przy użyciu listy sąsiedztwa:

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, wektor & odwiedził) { // Utwórz kolejkę dla kolejki BFS Q;  // Oznacz bieżący węzeł jako odwiedzony i wstaw go do kolejki [startNode] = true;  q.push(węzeł startowy);  // Wykonaj iterację po kolejce while (!q.empty()) { // Usuń wierzchołek z kolejki i wydrukuj go 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() { // Liczba wierzchołków grafu int vertices = 5;  // Lista sąsiedztwa reprezentująca wektor wykresu> adjList(wierzchołki);  // Dodaj krawędzie do wykresu addEdge(adjList, 0, 1);  addEdge(adjList, 0, 2);  addEdge(adjList, 1, 3);  addEdge(adjList, 1, 4);  addEdge(adjList, 2, 4);  // Oznacz wszystkie wierzchołki jako wektory nieodwiedzone odwiedzone (wierzchołki, fałsz);  // Wykonaj przejście BFS zaczynając od wierzchołka 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->dane = dane;  nowyWęzeł->dalej = NULL;  zwróć nowy węzeł; } // Funkcja dodająca krawędź do wykresu void addEdge(struct Node* adjList[], int u, int v) { struct Node* newNode = createNode(v);  newNode->next = adjList[u];  adjList[u] = nowyWęzeł; } // Funkcja wykonująca przeszukiwanie wszerz na grafie // reprezentowanym przy użyciu listy sąsiedztwa void bfs(struct Node* adjList[], int vertices, int startNode, int odwiedzony[]) { // Utwórz kolejkę dla BFS int kolejka[ MAX_VERTICES];  int przód = 0, tył = 0;  // Oznacz bieżący węzeł jako odwiedzony i umieść go w kolejce jako odwiedzony[startNode] = 1;  kolejka[tył++] = węzeł startowy;  // Wykonaj iterację po kolejce while (front != rear) { // Usuń wierzchołek z kolejki i wydrukuj go int currentNode = kolejka[front++];  printf('%d ', bieżący węzeł);  // Pobierz wszystkie sąsiednie wierzchołki usuniętego z kolejki wierzchołka // currentNode Jeśli sąsiedni wierzchołek nie został odwiedzony, // zaznacz go jako odwiedzony i wstaw do kolejki struct Node* temp = adjList[currentNode];  while (temp != NULL) { int sąsiad = temp->dane;  if (!odwiedził[sąsiad]) { odwiedził[sąsiad] = 1;  kolejka[tył++] = sąsiad;  } temp = temp->następny;  } } } int main() { // Liczba wierzchołków grafu int vertices = 5;  // Reprezentacja struktury grafu na liście sąsiedztwa Węzeł* adjList[wierzchołki];  for (int i = 0; tj< 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; }>
Jawa 
import java.util.LinkedList; import java.util.Queue; // Class to represent a graph using adjacency list class Graph {  int vertices;  LinkedList [] lista przymiotników;  @SuppressWarnings('niezaznaczone') Wykres(int wierzchołki) { this.vertices = wierzchołki;  adjList = nowa LinkedList[wierzchołki];  for (int i = 0; tj< 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 kolejka = nowa lista połączona();  wartość logiczna[] odwiedzona = nowa wartość logiczna[wierzchołki];  // Oznacz bieżący węzeł jako odwiedzony i wstaw go do kolejki [startNode] = true;  kolejka.add(węzeł startowy);  // Wykonaj iterację po kolejce while (!queue.isEmpty()) { // Usuń wierzchołek z kolejki i wydrukuj go int currentNode =queue.poll();  System.out.print(bieżący węzeł + ' ');  // Pobierz wszystkie sąsiednie wierzchołki usuniętego z kolejki // wierzchołka currentNode Jeśli sąsiadujący // nie został odwiedzony, zaznacz go jako odwiedzony i // umieść go w kolejce dla (int sąsiad : adjList[currentNode]) { if (!visited[neighbor] ) { odwiedził[sąsiad] = prawda;  kolejka.add(sąsiad);  } } } } } public class Main { public static void main(String[] args) { // Liczba wierzchołków grafu int vertices = 5;  // Utwórz wykres Wykres graph = new Graph(vertices);  // Dodaj krawędzie do wykresu graph.addEdge(0, 1);  wykres.addEdge(0, 2);  wykres.addEdge(1, 3);  wykres.addEdge(1, 4);  wykres.addEdge(2, 4);  // Wykonaj przechodzenie BFS zaczynając od wierzchołka 0 System.out.print( 'Pierwsze przechodzenie wszerz zaczynając od wierzchołka 0: ');  wykres.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 [] lista przymiotników;  public Graph(int wierzchołki) { this.vertices = wierzchołki;  adjList = nowa lista [ wierzchołki ];  for (int i = 0; tj< vertices; ++i)  adjList[i] = new List ();  } // Funkcja dodająca krawędź do wykresu public void AddEdge(int u, int v) { adjList[u].Add(v); } // Funkcja wykonująca przeszukiwanie wszerz na wykresie // reprezentowana za pomocą listy sąsiedztwa public void BFS(int startNode) { // Utwórz kolejkę dla kolejki BFS kolejka = nowa kolejka ();  bool[] odwiedzono = nowy bool[wierzchołki];  // Oznacz bieżący węzeł jako odwiedzony i wstaw go do kolejki [startNode] = true;  kolejka.Enqueue(startNode);  // Wykonaj iterację po kolejce while (queue.Count != 0) { // Usuń wierzchołek z kolejki i wydrukuj go int currentNode = kolejka.Dequeue();  Console.Write(bieżący węzeł + ' ');  // Pobierz wszystkie sąsiednie wierzchołki usuniętego z kolejki // wierzchołka currentNode Jeśli sąsiadujący // nie został odwiedzony, zaznacz go jako odwiedzony i // umieść go w kolejce foreach(int sąsiad w adjList[currentNode]) { if (!visited[neighbor] ) { odwiedził[sąsiad] = prawda;  kolejka.Enqueue(sąsiad);  } } } } } class MainClass { public static void Main(string[] args) { // Liczba wierzchołków grafu int vertices = 5;  // Utwórz wykres Wykres graph = new Graph(vertices);  // Dodaj krawędzie do wykresu graph.AddEdge(0, 1);  wykres.AddEdge(0, 2);  wykres.DodajEdge(1, 3);  wykres.DodajEdge(1, 4);  wykres.DodajEdge(2, 4);  // Wykonaj przechodzenie BFS zaczynając od wierzchołka 0 Console.Write( 'Przechodzenie po pierwszej szerokości zaczynając od wierzchołka 0: ');  wykres.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);>
Wyjście 
Breadth First Traversal starting from vertex 0: 0 1 2 3 4>

Złożoność czasowa: O(V+E), gdzie V to liczba węzłów, a E to liczba krawędzi.
Przestrzeń pomocnicza: O(V)

Analiza złożoności algorytmu przeszukiwania wszerz (BFS):

Złożoność czasowa algorytmu BFS: O(V + E)

  • BFS bada wszystkie wierzchołki i krawędzie grafu. W najgorszym przypadku odwiedza raz każdy wierzchołek i krawędź. Dlatego złożoność czasowa BFS wynosi O(V + E), gdzie V i E to liczba wierzchołków i krawędzi w danym grafie.

Złożoność przestrzenna algorytmu BFS: O(V)

  • BFS używa kolejki do śledzenia wierzchołków, które należy odwiedzić. W najgorszym przypadku kolejka może zawierać wszystkie wierzchołki grafu. Dlatego złożoność przestrzenna BFS wynosi O(V), gdzie V i E to liczba wierzchołków i krawędzi w danym grafie.

Zastosowania BFS na wykresach:

BFS ma różne zastosowania w teorii grafów i informatyce, w tym:

  • Wyszukiwanie najkrótszej ścieżki: BFS można wykorzystać do znalezienia najkrótszej ścieżki między dwoma węzłami na grafie nieważonym. Śledząc rodzica każdego węzła podczas przechodzenia, można zrekonstruować najkrótszą ścieżkę.
  • Wykrywanie cyklu: BFS można wykorzystać do wykrywania cykli na wykresie. Jeśli w trakcie przejścia węzeł zostanie odwiedzony dwukrotnie, oznacza to obecność cyklu.
  • Połączone komponenty: BFS można wykorzystać do identyfikacji połączonych komponentów na wykresie. Każdy połączony komponent to zbiór węzłów, do których można się ze sobą połączyć.
  • Sortowanie topologiczne: BFS można wykorzystać do sortowania topologicznego na skierowanym grafie acyklicznym (DAG). Sortowanie topologiczne układa węzły w porządku liniowym w taki sposób, że dla dowolnej krawędzi (u, v) u pojawia się przed v w kolejności.
  • Kolejność poziomów w drzewach binarnych: BFS można wykorzystać do wykonywania przechodzenia przez drzewo binarne w kolejności poziomów. To przejście odwiedza wszystkie węzły na tym samym poziomie przed przejściem do następnego poziomu.
  • Routing sieciowy: BFS można wykorzystać do znalezienia najkrótszej ścieżki między dwoma węzłami w sieci, co czyni go przydatnym do routingu pakietów danych w protokołach sieciowych.

Problemy z wyszukiwaniem wszerz lub BFS dla wykresu:

Tak nie

Problemy

Ćwiczyć
1. Znajdź poziom danego węzła na grafie nieskierowanym Połączyć
2. Minimalizuj maksymalną sąsiednią różnicę na ścieżce od lewego górnego do prawego dolnego rogu Połączyć
10. Sprawdź, czy miejsce docelowe danej macierzy jest osiągalne przy wymaganych wartościach komórek Połączyć

Często zadawane pytania dotyczące wyszukiwania wykresu wszerz (BFS):

Pytanie 1: Co to jest BFS i jak działa?

Odpowiedź: BFS to algorytm przechodzenia po grafie, który systematycznie eksploruje graf, odwiedzając wszystkie wierzchołki na danym poziomie przed przejściem do następnego poziomu. Rozpoczyna się od wierzchołka początkowego, umieszcza go w kolejce i oznacza jako odwiedzony. Następnie usuwa wierzchołek z kolejki, odwiedza go i umieszcza w kolejce wszystkich nieodwiedzonych sąsiadów. Proces ten trwa do momentu opróżnienia kolejki.

Pytanie 2: Jakie są zastosowania BFS?

Odpowiedź: BFS ma różne zastosowania, w tym znajdowanie najkrótszej ścieżki na grafie nieważonym, wykrywanie cykli na grafie, topologiczne sortowanie skierowanego grafu acyklicznego (DAG), znajdowanie połączonych elementów na grafie i rozwiązywanie zagadek, takich jak labirynty i Sudoku.

Pytanie 3: Jaka jest złożoność czasowa BFS?

Odpowiedź: Złożoność czasowa BFS wynosi O(V + E), gdzie V to liczba wierzchołków, a E to liczba krawędzi w grafie.

Pytanie 4: Jaka jest złożoność przestrzenna BFS?

Odpowiedź: Złożoność przestrzenna BFS wynosi O(V), ponieważ wykorzystuje kolejkę do śledzenia wierzchołków, które należy odwiedzić.

Pytanie 5: Jakie są zalety korzystania z BFS?

Odpowiedź: BFS jest prosty w implementacji i skuteczny w znajdowaniu najkrótszej ścieżki na nieważonym wykresie. Gwarantuje również, że wszystkie wierzchołki grafu zostaną odwiedzone.

wyszukiwanie BFS

Powiązane artykuły:

  • Najnowsze artykuły na temat BFS
  • Głębokość pierwszego przejścia
  • Zastosowania pierwszego przejścia wszerz
  • Zastosowania wyszukiwania w głąb
  • Złożoność czasowo-przestrzenna pierwszego wyszukiwania wszerz (BFS)