Breadth First Search (BFS) är en grundläggande algoritm för genomgång av grafer . Det innebär att man besöker alla anslutna noder i en graf på ett nivå-för-nivå sätt. I den här artikeln kommer vi att undersöka begreppet BFS och hur det kan tillämpas på grafer effektivt
Innehållsförteckning
- Breadth First Search eller BFS för en graf
- Relation mellan BFS för Graph och BFS för Tree
- Breadth First Search (BFS) för en grafalgoritm
- Hur fungerar BFS-algoritmen?
- Implementering av BFS för Graph med hjälp av Adjacency List
- Komplexiteten för Breadth-First Search-algoritmen (BFS).
- Tillämpningar av BFS i grafer
- Problem med Breadth First Search eller BFS för en graf
- Vanliga frågor om Breadth First Search (BFS) för en graf
Breadth First Search (BFS) för en graf:
Breadth First Search (BFS) är en grafövergångsalgoritm som utforskar alla hörn i en graf på det aktuella djupet innan man går vidare till hörnen på nästa djupnivå. Den börjar vid en specificerad vertex och besöker alla sina grannar innan den går vidare till nästa nivå av grannar. BFS används ofta i algoritmer för sökvägssökning, anslutna komponenter och kortaste vägproblem i grafer.
Relation mellan BFS för graf och BFS för träd:
Breadth-First Traversal (BFS) för en graf liknar den Bredth-First Traversering av ett träd .
Den enda haken här är att, till skillnad från träd , grafer kan innehålla cykler, så vi kan komma till samma nod igen. För att undvika att bearbeta en nod mer än en gång delar vi upp hörnen i två kategorier:
- Besökte och
- Ej besökt.
En boolesk besökt array används för att markera de besökta hörnen. För enkelhetens skull antas det att alla hörn är nåbara från startpunkten. BFS använder a Breadth First Search (BFS) för en grafalgoritm:
Låt oss diskutera algoritmen för BFS:
- Initiering: Ställ startnoden i en kö och markera den som besökt.
- Utforskning: Medan kön inte är tom:
- Ta bort en nod från kön och besök den (skriv till exempel ut dess värde).
- För varje obesökt granne till den avköade noden:
- Ställ in grannen i kön.
- Markera grannen som besökt.
- Uppsägning: Upprepa steg 2 tills kön är tom.
Denna algoritm säkerställer att alla noder i grafen besöks på ett bredd-först sätt, med början från startnoden.
Hur fungerar BFS-algoritmen?
Med start från roten besöks först alla noder på en viss nivå och sedan korsas noderna på nästa nivå tills alla noder besöks.
För att göra detta används en kö. Alla intilliggande obesökta noder på den aktuella nivån skjuts in i kön och noderna på den aktuella nivån markeras som besökta och tas bort från kön.
Illustration:
Låt oss förstå hur algoritmen fungerar med hjälp av följande exempel.
Steg 1: Inledningsvis är kön och besökta arrayer tomma.
Kön och besökta arrayer är tomma initialt.
Steg 2: Skjut in nod 0 i kön och markera den som besökt.
Skjut in nod 0 i kön och markera den som besökt.
Steg 3: Ta bort nod 0 från framsidan av kön och besök de obesökta grannarna och skjut in dem i kön.
Ta bort nod 0 från den främre delen av kön och besökte de obesökta grannarna och tryck in i kön.
Steg 4: Ta bort nod 1 från framsidan av kön och besök de obesökta grannarna och skjut in dem i kön.
Ta bort nod 1 från framsidan av kön och besökte de obesökta grannarna och tryck
Steg 5: Ta bort nod 2 från framsidan av kön och besök de obesökta grannarna och skjut in dem i kön.
Ta bort nod 2 från framsidan av kön och besök de obesökta grannarna och skjut in dem i kön.
Steg 6: Ta bort nod 3 från framsidan av kön och besök de obesökta grannarna och skjut in dem i kön.
Eftersom vi kan se att alla grannar till nod 3 besöks, så flytta till nästa nod som står längst fram i kön.Ta bort nod 3 från framsidan av kön och besök de obesökta grannarna och skjut in dem i kön.
Steg 7: Ta bort nod 4 från framsidan av kön och besök de obesökta grannarna och skjut in dem i kön.
Eftersom vi kan se att alla grannar till nod 4 besöks, så flytta till nästa nod som står längst fram i kön.Ta bort nod 4 från framsidan av kön och besök de obesökta grannarna och skjut in dem i kön.
Nu blir kön tom, så avsluta dessa iterationsprocesser.
Implementering av BFS för Graph med hjälp av 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, vektor & besökt) { // Skapa en kö för BFS-kö q; // Markera den aktuella noden som besökt och ställ den i kö[startNode] = sant; q.push(startNode); // Iterera över kön medan (!q.empty()) { // Ta ur en vertex från kön och skriv ut den 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() { // Antal hörn i grafen int hörn = 5; // Adjacency listrepresentation av grafvektorn> adjList(vertices); // Lägg till kanter till grafen addEdge(adjList, 0, 1); addEdge(adjList, 0, 2); addEdge(adjList, 1, 3); addEdge(adjList, 1, 4); addEdge(adjList, 2, 4); // Markera alla hörn som ej besökt vektor besökt(hörn, falskt); // Utför BFS-traversering med början från vertex 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; newNode->next = NULL; returnera nyNode; } // Funktion för att lägga till en kant till grafen void addEdge(struct Node* adjList[], int u, int v) { struct Node* newNode = createNode(v); newNode->next = adjList[u]; adjList[u] = newNode; } // Funktion för att utföra Breadth First Search på en graf // representerad med hjälp av adjacency list void bfs(struct Node* adjList[], int vertices, int startNode, int visited[]) { // Skapa en kö för BFS int queue[ MAX_VERTICES]; int fram = 0, bak = 0; // Markera den aktuella noden som besökt och ställ den i kö[startNode] = 1; queue[rear++] = startNode; // Iterera över kön medan (front != rear) { // Ta ur en vertex från kön och skriv ut den int currentNode = queue[front++]; printf('%d ', aktuell nod); // Hämta alla angränsande hörn av den avköade vertexen // currentNode Om en angränsande inte har besökts, // markera den sedan som besökt och ställ den i kö struct Node* temp = adjList[currentNode]; while (temp != NULL) { int neighbor = temp->data; if (!besökt[granne]) { besökte[granne] = 1; kö[rear++] = granne; } temp = temp->nästa; } } } int main() { // Antal hörn i grafen int hörn = 5; // Adjacency listrepresentation av grafstrukturen Node* adjList[vertices]; för (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 = new LinkedList[vertices]; för (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 kö = new LinkedList(); boolean[] visited = new boolean[vertices]; // Markera den aktuella noden som besökt och ställ den i kö[startNode] = sant; queue.add(startNode); // Iterera över kön medan (!queue.isEmpty()) { // Ta ur en vertex från kön och skriv ut den int currentNode = queue.poll(); System.out.print(currentNode + ' '); // Hämta alla angränsande hörn av den avköade // vertex currentNode Om en angränsande inte // har besökts, markera den som besökt och // ställ den i kö för (int neighbor : adjList[currentNode]) { if (!visited[neighbor] ) { besökt[granne] = sant; queue.add(granne); } } } } } public class Main { public static void main(String[] args) { // Antal hörn i grafen int vertices = 5; // Skapa en graf Graph graph = new Graph(vertices); // Lägg till kanter till grafen graph.addEdge(0, 1); graph.addEdge(0, 2); graph.addEdge(1, 3); graph.addEdge(1, 4); graph.addEdge(2, 4); // Utför BFS-traversal med början från vertex 0 System.out.print( 'Bredth First Traversal från vertex 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 vertices) { this.vertices = vertices; adjList = ny lista [hörn]; för (int i = 0; i< vertices; ++i) adjList[i] = new List (); } // Funktion för att lägga till en kant till grafen public void AddEdge(int u, int v) { adjList[u].Add(v); } // Funktion för att utföra Breadth First Search på en graf // representerad med hjälp av adjacency list public void BFS(int startNode) { // Skapa en kö för BFS Queue kö = ny kö (); bool[] visited = new bool[vertices]; // Markera den aktuella noden som besökt och ställ den i kö[startNode] = sant; queue.Enqueue(startNode); // Iterera över kön medan (queue.Count != 0) { // Ta ur en vertex från kön och skriv ut den int currentNode = queue.Dequeue(); Console.Write(currentNode + ' '); // Hämta alla angränsande hörn av den avköade // vertex currentNode Om en angränsande inte har // besökts, markera den som besökt och // ställ den i kö föreach(int neighbor i adjList[currentNode]) { if (!visited[neighbor] ) { besökt[granne] = sant; queue.Enqueue(granne); } } } } } class MainClass { public static void Main(string[] args) { // Antal hörn i grafen int vertices = 5; // Skapa en graf Graph graph = new Graph(vertices); // Lägg till kanter till grafen. AddEdge(0, 1); graph.AddEdge(0, 2); graph.AddEdge(1, 3); graph.AddEdge(1, 4); graph.AddEdge(2, 4); // Utför BFS-traversal med början från vertex 0 Console.Write( 'Bredth First Traversal från vertex 0: '); graph.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);> Produktion
Breadth First Traversal starting from vertex 0: 0 1 2 3 4>
Tidskomplexitet: O(V+E), där V är antalet noder och E är antalet kanter.
Hjälputrymme: O(V)
Komplexitetsanalys av Breadth-First Search (BFS) Algoritm:
Tidskomplexitet för BFS-algoritm: O(V + E)
- BFS utforskar alla hörn och kanter i grafen. I värsta fall besöker den varje vertex och kant en gång. Därför är tidskomplexiteten för BFS O(V + E), där V och E är antalet hörn och kanter i den givna grafen.
Rymdkomplexitet för BFS-algoritm: O(V)
- BFS använder en kö för att hålla reda på de hörn som behöver besökas. I värsta fall kan kön innehålla alla hörn i grafen. Därför är rymdkomplexiteten för BFS O(V), där V och E är antalet hörn och kanter i den givna grafen.
Tillämpningar av BFS i grafer:
BFS har olika tillämpningar inom grafteori och datavetenskap, inklusive:
- Hitta kortaste vägen: BFS kan användas för att hitta den kortaste vägen mellan två noder i en oviktad graf. Genom att hålla reda på föräldern till varje nod under genomgången kan den kortaste vägen rekonstrueras.
- Cykeldetektering: BFS kan användas för att detektera cykler i en graf. Om en nod besöks två gånger under genomgången indikerar det närvaron av en cykel.
- Anslutna komponenter: BFS kan användas för att identifiera anslutna komponenter i en graf. Varje ansluten komponent är en uppsättning noder som kan nås från varandra.
- Topologisk sortering: BFS kan användas för att utföra topologisk sortering på en riktad acyklisk graf (DAG). Topologisk sortering ordnar noderna i en linjär ordning så att för vilken kant som helst (u, v) visas u före v i ordningen.
- Nivåordningsgenomgång av binära träd: BFS kan användas för att utföra en nivåordningsövergång av ett binärt träd. Denna genomgång besöker alla noder på samma nivå innan den går till nästa nivå.
- Nätverksrouting: BFS kan användas för att hitta den kortaste vägen mellan två noder i ett nätverk, vilket gör det användbart för att dirigera datapaket i nätverksprotokoll.
Problem med Breadth First Search eller BFS för en graf:
| Ja Nej | Problem | Öva |
|---|---|---|
| 1. | Hitta nivån för en given nod i en oriktad graf | Länk |
| 2. | Minimera maximal intilliggande skillnad i en bana från övre vänstra till nedre höger | Länk |
| 10. | Kontrollera om destinationen för given matris kan nås med nödvändiga värden på celler | Länk |
Vanliga frågor om Breadth First Search (BFS) för en graf:
Fråga 1: Vad är BFS och hur fungerar det?
Svar: BFS är en grafövergångsalgoritm som systematiskt utforskar en graf genom att besöka alla hörn på en given nivå innan man går vidare till nästa nivå. Den startar från en startpunkt, ställer den i kö i en kö och markerar den som besökt. Sedan löser den en vertex från kön, besöker den och ställer alla obesökta grannar i kö i kön. Denna process fortsätter tills kön är tom.
Fråga 2: Vilka är tillämpningarna för BFS?
Svar: BFS har olika applikationer, inklusive att hitta den kortaste vägen i en oviktad graf, detektera cykler i en graf, topologisk sortering av en riktad acyklisk graf (DAG), hitta anslutna komponenter i en graf och lösa pussel som labyrinter och Sudoku.
Fråga 3: Vad är tidskomplexiteten för BFS?
Svar: Tidskomplexiteten för BFS är O(V + E), där V är antalet hörn och E är antalet kanter i grafen.
js global variabel
Fråga 4: Vad är rymdkomplexiteten hos BFS?
Svar: Utrymmeskomplexiteten för BFS är O(V), eftersom den använder en kö för att hålla reda på de hörn som behöver besökas.
Fråga 5: Vilka är fördelarna med att använda BFS?
Svar: BFS är enkelt att implementera och effektivt för att hitta den kortaste vägen i en oviktad graf. Det garanterar också att alla hörn i grafen besöks.
Relaterade artiklar:
- Senaste artiklar om BFS
- Depth First Traversal
- Tillämpningar av Breadth First Traversal
- Tillämpningar av Depth First Search
- Tid och rumskomplexitet i Breadth First Search (BFS)