Prima ricerca in ampiezza (BFS) è un fondamentale algoritmo di attraversamento del grafico . Implica la visita di tutti i nodi connessi di un grafico livello per livello. In questo articolo esamineremo il concetto di BFS e come può essere applicato efficacemente ai grafici
Tabella dei contenuti
- Ricerca in ampiezza o BFS per un grafico
- Relazione tra BFS per Graph e BFS per Tree
- BFS (Breadth First Search) per un algoritmo grafico
- Come funziona l'algoritmo BFS?
- Implementazione di BFS per Graph utilizzando l'elenco di adiacenze
- Complessità dell'algoritmo BFS (Breadth-First Search).
- Applicazioni di BFS nei grafici
- Problemi sulla ricerca in ampiezza o BFS per un grafico
- Domande frequenti sulla ricerca BFS (Breadth First Search) per un grafico
Ricerca in ampiezza (BFS) per un grafico:
Prima ricerca in ampiezza (BFS) è un algoritmo di attraversamento del grafico che esplora tutti i vertici di un grafico alla profondità corrente prima di passare ai vertici al livello di profondità successivo. Inizia da un vertice specificato e visita tutti i vicini prima di passare al livello successivo di vicini. BFS è comunemente usato negli algoritmi per il pathfinding, i componenti connessi e i problemi del percorso più breve nei grafici.
Relazione tra BFS per Graph e BFS per Tree:
Il BFS (Breadth-First Traversal) per un grafico è simile a Attraversamento in larghezza di un albero .
L'unico problema qui è che, diversamente alberi , grafici può contenere cicli, quindi potremmo arrivare di nuovo allo stesso nodo. Per evitare di elaborare un nodo più di una volta, dividiamo i vertici in due categorie:
- Visitato e
- Non visitato.
Un array visitato booleano viene utilizzato per contrassegnare i vertici visitati. Per semplicità si assume che tutti i vertici siano raggiungibili dal vertice iniziale. BFS usi UN Ricerca Breadth First (BFS) per un algoritmo grafico:
Parliamo dell'algoritmo per il BFS:
- Inizializzazione: Accoda il nodo iniziale in una coda e contrassegnalo come visitato.
- Esplorazione: Mentre la coda non è vuota:
- Rimuovi dalla coda un nodo dalla coda e visitalo (ad esempio, stampane il valore).
- Per ogni vicino non visitato del nodo rimosso dalla coda:
- Accoda il vicino in coda.
- Contrassegna il vicino come visitato.
- Terminazione: Ripetere il passaggio 2 finché la coda non sarà vuota.
Questo algoritmo garantisce che tutti i nodi del grafo siano visitati in ampiezza, a partire dal nodo di partenza.
rimuove l'ultimo carattere dalla stringa
Come funziona l'algoritmo BFS?
Partendo dalla radice, vengono visitati prima tutti i nodi di un particolare livello e poi vengono attraversati i nodi del livello successivo fino a visitare tutti i nodi.
Per fare ciò viene utilizzata una coda. Tutti i nodi adiacenti non visitati del livello corrente vengono inseriti nella coda e i nodi del livello corrente vengono contrassegnati come visitati ed eliminati dalla coda.
Illustrazione:
Cerchiamo di comprendere il funzionamento dell'algoritmo con l'aiuto del seguente esempio.
Passo 1: Inizialmente gli array in coda e visitati sono vuoti.
La coda e gli array visitati sono inizialmente vuoti.
Passo 2: Metti il nodo 0 in coda e contrassegnalo come visitato.
Metti il nodo 0 in coda e contrassegnalo come visitato.
Passaggio 3: Rimuovi il nodo 0 dalla parte anteriore della coda e visita i vicini non visitati e spingili in coda.
tipo in JavaRimuovi il nodo 0 dalla parte anteriore della coda e visita i vicini non visitati e inseriscilo nella coda.
Passaggio 4: Rimuovi il nodo 1 dalla parte anteriore della coda e visita i vicini non visitati e spingili in coda.
Rimuovi il nodo 1 dalla parte anteriore della coda e visita i vicini non visitati e spingi
Passaggio 5: Rimuovi il nodo 2 dalla parte anteriore della coda e visita i vicini non visitati e spingili in coda.
Rimuovi il nodo 2 dalla parte anteriore della coda e visita i vicini non visitati e spingili in coda.
Passaggio 6: Rimuovi il nodo 3 dalla parte anteriore della coda e visita i vicini non visitati e spingili in coda.
Come possiamo vedere, tutti i vicini del nodo 3 vengono visitati, quindi spostati al nodo successivo che si trova in prima fila.zeri npRimuovi il nodo 3 dalla parte anteriore della coda e visita i vicini non visitati e spingili in coda.
Passaggi 7: Rimuovi il nodo 4 dalla parte anteriore della coda e visita i vicini non visitati e spingili in coda.
Come possiamo vedere, tutti i vicini del nodo 4 vengono visitati, quindi spostati al nodo successivo che si trova in prima fila.Rimuovi il nodo 4 dalla parte anteriore della coda e visita i vicini non visitati e spingili in coda.
Ora la coda diventa vuota, quindi termina questo processo di iterazione.
Implementazione di BFS per Graph utilizzando l'elenco di adiacenze:
C++ #include #include #include using namespace std; // Function to perform Breadth First Search on a graph // represented using adjacency list void bfs(vector>& adjLista, int startNode, vettore & visitato) { // Crea una coda per la coda BFS Q; // Contrassegna il nodo corrente come visitato e accodalo visitato[startNode] = true; q.push(startNode); // Itera sulla coda while (!q.empty()) { // Rimuove dalla coda un vertice e lo stampa 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() { // Numero di vertici nel grafico int vertici = 5; // Rappresentazione dell'elenco di adiacenza del vettore grafico> adjList(vertici); // Aggiunge bordi al grafico addEdge(adjList, 0, 1); aggiungiBordo(adjLista, 0, 2); aggiungiBordo(adjLista, 1, 3); addBordo(adjLista, 1, 4); aggiungiBordo(adjLista, 2, 4); // Contrassegna tutti i vertici come vettore non visitato visitato(vertices, false); // Esegue l'attraversamento BFS a partire dal vertice 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; nuovoNodo->successivo = NULL; restituire nuovoNodo; } // Funzione per aggiungere un bordo al grafico void addEdge(struct Node* adjList[], int u, int v) { struct Node* newNode = createNode(v); nuovoNodo->successivo = adjLista[u]; adjLista[u] = nuovoNodo; } // Funzione per eseguire la ricerca Breadth First su un grafico // rappresentato utilizzando l'elenco di adiacenza void bfs(struct Node* adjList[], int vertices, int startNode, int visit[]) { // Crea una coda per BFS int Queue[ MAX_VERTICI]; int anteriore = 0, posteriore = 0; // Contrassegna il nodo corrente come visitato e accodalo visitato[startNode] = 1; coda[posteriore++] = startNode; // Itera sulla coda while (front != posterior) { // Rimuove dalla coda un vertice e lo stampa int currentNode = tail[front++]; printf('%d ', currentNode); // Ottieni tutti i vertici adiacenti del vertice rimosso dalla coda // currentNode Se un adiacente non è stato visitato, // contrassegnalo come visitato e accodalo struct Node* temp = adjList[currentNode]; while (temp!= NULL) { int neighbor = temp->data; if (!visitato[vicino]) { visitato[vicino] = 1; coda[posteriore++] = vicino; } temp = temp->successivo; } } } int main() { // Numero di vertici nel grafico int vertici = 5; // Rappresentazione della lista di adiacenza della struttura del grafo 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; }> Giava import java.util.LinkedList; import java.util.Queue; // Class to represent a graph using adjacency list class Graph { int vertices; LinkedList [] adjLista; @SuppressWarnings('non selezionato') Graph(int vertici) { this.vertices = vertici; adjList = nuova LinkedList[vertici]; 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 coda = nuova Lista Collegata(); booleano[] visitato = nuovo booleano[vertici]; // Contrassegna il nodo corrente come visitato e accodalo visitato[startNode] = true; coda.add(startNode); // Itera sulla coda while (!queue.isEmpty()) { // Toglie dalla coda un vertice dalla coda e stampalo int currentNode = Queue.poll(); System.out.print(currentNode + ' '); // Ottieni tutti i vertici adiacenti del // vertice currentNode rimosso Se un adiacente non // è stato visitato, contrassegnalo come visitato e // accodalo per (int neighbor: adjList[currentNode]) { if (!visited[neighbor] ) { visitato[vicino] = true; coda.add(vicino); } } } } } public class Main { public static void main(String[] args) { // Numero di vertici nel grafico int vertici = 5; // Crea un grafico Graph graph = new Graph(vertices); // Aggiunge bordi al grafico graph.addEdge(0, 1); grafico.addEdge(0, 2); grafico.addEdge(1, 3); grafico.addEdge(1, 4); grafico.addEdge(2, 4); // Esegue l'attraversamento BFS a partire dal vertice 0 System.out.print( 'Breadth First Traversal a partire dal vertice 0: '); grafico.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 [] adjLista; public Graph(int vertici) { this.vertici = vertici; adjLista = nuova Lista [ vertici ]; for (int i = 0; i< vertices; ++i) adjList[i] = new List (); } // Funzione per aggiungere un bordo al grafico public void AddEdge(int u, int v) { adjList[u].Add(v); } // Funzione per eseguire la ricerca Breadth First su un grafico // rappresentato utilizzando l'elenco di adiacenza public void BFS(int startNode) { // Crea una coda per BFS Queue coda = nuova coda (); bool[] visitato = new bool[vertici]; // Contrassegna il nodo corrente come visitato e accodalo visitato[startNode] = true; coda.Enqueue(startNode); // Itera sulla coda while (queue.Count != 0) { // Rimuove dalla coda un vertice dalla coda e stampalo int currentNode = Queue.Dequeue(); Console.Write(currentNode + ' '); // Ottieni tutti i vertici adiacenti del vertice rimosso dalla coda // currentNode Se un adiacente non // è stato visitato, contrassegnalo come visitato e // accodalo foreach(int neighbor in adjList[currentNode]) { if (!visited[neighbor] ) { visitato[vicino] = true; coda.Enqueue(vicino); } } } } } class MainClass { public static void Main(string[] args) { // Numero di vertici nel grafico int vertici = 5; // Crea un grafico Graph graph = new Graph(vertices); // Aggiunge bordi al grafico graph.AddEdge(0, 1); grafico.AddEdge(0, 2); grafico.AddEdge(1, 3); grafico.AddEdge(1, 4); grafico.AddEdge(2, 4); // Esegue l'attraversamento BFS a partire dal vertice 0 Console.Write( 'Breadth First Traversal a partire dal vertice 0: '); grafico.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);> Produzione
Breadth First Traversal starting from vertex 0: 0 1 2 3 4>
Complessità temporale: O(V+E), dove V è il numero di nodi ed E è il numero di spigoli.
Spazio ausiliario: O(V)
Analisi della complessità dell'algoritmo BFS (Breadth-First Search):
Complessità temporale dell'algoritmo BFS: O(V + E)
- BFS esplora tutti i vertici e gli spigoli del grafico. Nel peggiore dei casi, visita ogni vertice e spigolo una volta. Pertanto, la complessità temporale di BFS è O(V + E), dove V ed E sono il numero di vertici e archi nel grafico dato.
Complessità spaziale dell'algoritmo BFS: O(V)
- BFS utilizza una coda per tenere traccia dei vertici che devono essere visitati. Nel peggiore dei casi, la coda può contenere tutti i vertici del grafico. Pertanto, la complessità spaziale di BFS è O(V), dove V ed E sono il numero di vertici e archi nel grafico dato.
Applicazioni di BFS nei grafici:
BFS ha varie applicazioni nella teoria dei grafi e nell'informatica, tra cui:
ordinamento delle bolle Java
- Ricerca del percorso più breve: BFS può essere utilizzato per trovare il percorso più breve tra due nodi in un grafico non ponderato. Tenendo traccia del genitore di ciascun nodo durante l'attraversamento, è possibile ricostruire il percorso più breve.
- Rilevamento del ciclo: BFS può essere utilizzato per rilevare i cicli in un grafico. Se un nodo viene visitato due volte durante l'attraversamento, indica la presenza di un ciclo.
- Componenti collegati: BFS può essere utilizzato per identificare i componenti connessi in un grafico. Ogni componente connessa è un insieme di nodi raggiungibili gli uni dagli altri.
- Ordinamento topologico: BFS può essere utilizzato per eseguire l'ordinamento topologico su un grafo aciclico diretto (DAG). L'ordinamento topologico dispone i nodi in un ordine lineare tale che per ogni arco (u, v), u appaia prima di v nell'ordine.
- Attraversamento dell'ordine di livello degli alberi binari: BFS può essere utilizzato per eseguire un attraversamento dell'ordine di livello di un albero binario. Questa traversata visita tutti i nodi allo stesso livello prima di passare al livello successivo.
- Instradamento di rete: BFS può essere utilizzato per trovare il percorso più breve tra due nodi in una rete, rendendolo utile per instradare i pacchetti di dati nei protocolli di rete.
Problemi sulla ricerca in ampiezza o BFS per un grafico:
| Si No | I problemi | Pratica |
|---|---|---|
| 1. | Trova il livello di un dato nodo in un grafico non orientato | Collegamento |
| 2. | Minimizza la massima differenza adiacente in un percorso da in alto a sinistra a in basso a destra | Collegamento |
| 10. | Controlla se la destinazione di una determinata matrice è raggiungibile con i valori richiesti delle celle | Collegamento |
Domande frequenti sulla ricerca BFS (Breadth First Search) per un grafico:
Domanda 1: Cos'è BFS e come funziona?
Risposta: BFS è un algoritmo di attraversamento del grafico che esplora sistematicamente un grafico visitando tutti i vertici ad un dato livello prima di passare al livello successivo. Inizia da un vertice iniziale, lo accoda in una coda e lo contrassegna come visitato. Quindi, rimuove un vertice dalla coda, lo visita e accoda tutti i suoi vicini non visitati nella coda. Questo processo continua finché la coda non è vuota.
Domanda 2: Quali sono le applicazioni di BFS?
Risposta: BFS ha varie applicazioni, tra cui trovare il percorso più breve in un grafico non ponderato, rilevare cicli in un grafico, ordinare topologicamente un grafico aciclico diretto (DAG), trovare componenti collegati in un grafico e risolvere enigmi come labirinti e Sudoku.
Domanda 3: Qual è la complessità temporale di BFS?
Risposta: La complessità temporale di BFS è O(V + E), dove V è il numero di vertici ed E è il numero di archi nel grafico.
Domanda 4: Qual è la complessità spaziale di BFS?
Risposta: La complessità spaziale di BFS è O(V), poiché utilizza una coda per tenere traccia dei vertici che devono essere visitati.
Domanda 5: Quali sono i vantaggi dell'utilizzo di BFS?
Risposta: BFS è semplice da implementare ed efficiente per trovare il percorso più breve in un grafico non ponderato. Garantisce inoltre che tutti i vertici del grafico siano visitati.
Articoli Correlati:
- Articoli recenti su BFS
- Prima traversata in profondità
- Applicazioni dell'attraversamento di prima ampiezza
- Applicazioni della ricerca in profondità
- Complessità temporale e spaziale della ricerca in ampiezza (BFS)