Algoritmo grafico BFS (con codice in C, C ++, Java e Python)

Sommario

Algoritmo BFS
Esempio BFS
Pseudocodice BFS
Esempi di Python, Java e C / C ++
Complessità algoritmo BFS
Applicazioni dell'algoritmo BFS

In questo tutorial imparerai a conoscere l'algoritmo di ricerca in ampiezza. Inoltre, troverai esempi funzionanti dell'algoritmo bfs in C, C ++, Java e Python.

Traversal significa visitare tutti i nodi di un grafo. Breadth First Traversal o Breadth First Search è un algoritmo ricorsivo per la ricerca in tutti i vertici di un grafico o di una struttura dati ad albero.

Algoritmo BFS

Un'implementazione BFS standard pone ogni vertice del grafico in una delle due categorie:

Visitato
Non visitato

Lo scopo dell'algoritmo è contrassegnare ogni vertice come visitato evitando i cicli.

L'algoritmo funziona come segue:

Inizia mettendo uno qualsiasi dei vertici del grafico in fondo a una coda.
Prendi l'elemento in primo piano della coda e aggiungilo all'elenco dei visitati.
Crea un elenco dei nodi adiacenti di quel vertice. Aggiungi quelli che non sono nell'elenco dei visitati in fondo alla coda.
Continua a ripetere i passaggi 2 e 3 finché la coda non è vuota.

Il grafico potrebbe avere due diverse parti disconnesse quindi per essere sicuri di coprire ogni vertice, possiamo anche eseguire l'algoritmo BFS su ogni nodo

Esempio BFS

Vediamo come funziona l'algoritmo di Breadth First Search con un esempio. Usiamo un grafo non orientato con 5 vertici.

Grafo non orientato con 5 vertici

Partiamo dal vertice 0, l'algoritmo BFS inizia mettendolo nella lista Visitate e mettendo tutti i suoi vertici adiacenti nello stack.

Visita il vertice di inizio e aggiungi i suoi vertici adiacenti alla coda

Successivamente, visitiamo l'elemento all'inizio della coda, ad esempio 1 e andiamo ai suoi nodi adiacenti. Poiché 0 è già stato visitato, visitiamo invece 2.

Visita il primo vicino del nodo iniziale 0, che è 1

Il vertice 2 ha un vertice adiacente non visitato in 4, quindi lo aggiungiamo in fondo alla coda e visitiamo 3, che si trova all'inizio della coda.

La visita 2 che è stata aggiunta alla coda in precedenza per aggiungere i suoi vicini

4 rimane in coda

Solo 4 rimangono in coda poiché l'unico nodo adiacente di 3 cioè 0 è già visitato. Lo visitiamo.

Visita l'ultimo oggetto rimanente nella pila per verificare se ha vicini non visitati

Poiché la coda è vuota, abbiamo completato il primo attraversamento in larghezza del grafico.

Pseudocodice BFS

 crea una coda Q segna v come visitato e metti v in Q mentre Q non è vuoto rimuovi la testa u del segno Q e accoda tutti i vicini (non visitati) di u

Esempi di Python, Java e C / C ++

Di seguito è mostrato il codice per l'algoritmo di ricerca Breadth First con un esempio. Il codice è stato semplificato in modo che possiamo concentrarci sull'algoritmo piuttosto che su altri dettagli.

Python Java C C +

 # BFS algorithm in Python import collections # BFS algorithm def bfs(graph, root): visited, queue = set(), collections.deque((root)) visited.add(root) while queue: # Dequeue a vertex from queue vertex = queue.popleft() print(str(vertex) + " ", end="") # If not visited, mark it as visited, and # enqueue it for neighbour in graph(vertex): if neighbour not in visited: visited.add(neighbour) queue.append(neighbour) if __name__ == '__main__': graph = (0: (1, 2), 1: (2), 2: (3), 3: (1, 2)) print("Following is Breadth First Traversal: ") bfs(graph, 0)

 // BFS algorithm in Java import java.util.*; public class Graph ( private int V; private LinkedList adj(); // Create a graph Graph(int v) ( V = v; adj = new LinkedList(v); for (int i = 0; i < v; ++i) adj(i) = new LinkedList(); ) // Add edges to the graph void addEdge(int v, int w) ( adj(v).add(w); ) // BFS algorithm void BFS(int s) ( boolean visited() = new boolean(V); LinkedList queue = new LinkedList(); visited(s) = true; queue.add(s); while (queue.size() != 0) ( s = queue.poll(); System.out.print(s + " "); Iterator i = adj(s).listIterator(); while (i.hasNext()) ( int n = i.next(); if (!visited(n)) ( visited(n) = true; queue.add(n); ) ) ) ) public static void main(String args()) ( Graph g = new Graph(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(3, 3); System.out.println("Following is Breadth First Traversal " + "(starting from vertex 2)"); g.BFS(2); ) )

 // BFS algorithm in C #include #include #define SIZE 40 struct queue ( int items(SIZE); int front; int rear; ); struct queue* createQueue(); void enqueue(struct queue* q, int); int dequeue(struct queue* q); void display(struct queue* q); int isEmpty(struct queue* q); void printQueue(struct queue* q); struct node ( int vertex; struct node* next; ); struct node* createNode(int); struct Graph ( int numVertices; struct node** adjLists; int* visited; ); // BFS algorithm void bfs(struct Graph* graph, int startVertex) ( struct queue* q = createQueue(); graph->visited(startVertex) = 1; enqueue(q, startVertex); while (!isEmpty(q)) ( printQueue(q); int currentVertex = dequeue(q); printf("Visited %d", currentVertex); struct node* temp = graph->adjLists(currentVertex); while (temp) ( int adjVertex = temp->vertex; if (graph->visited(adjVertex) == 0) ( graph->visited(adjVertex) = 1; enqueue(q, adjVertex); ) temp = temp->next; ) ) ) // Creating a node struct node* createNode(int v) ( struct node* newNode = malloc(sizeof(struct node)); newNode->vertex = v; newNode->next = NULL; return newNode; ) // Creating a graph struct Graph* createGraph(int vertices) ( struct Graph* graph = malloc(sizeof(struct Graph)); graph->numVertices = vertices; graph->adjLists = malloc(vertices * sizeof(struct node*)); graph->visited = malloc(vertices * sizeof(int)); int i; for (i = 0; i adjLists(i) = NULL; graph->visited(i) = 0; ) return graph; ) // Add edge void addEdge(struct Graph* graph, int src, int dest) ( // Add edge from src to dest struct node* newNode = createNode(dest); newNode->next = graph->adjLists(src); graph->adjLists(src) = newNode; // Add edge from dest to src newNode = createNode(src); newNode->next = graph->adjLists(dest); graph->adjLists(dest) = newNode; ) // Create a queue struct queue* createQueue() ( struct queue* q = malloc(sizeof(struct queue)); q->front = -1; q->rear = -1; return q; ) // Check if the queue is empty int isEmpty(struct queue* q) ( if (q->rear == -1) return 1; else return 0; ) // Adding elements into queue void enqueue(struct queue* q, int value) ( if (q->rear == SIZE - 1) printf("Queue is Full!!"); else ( if (q->front == -1) q->front = 0; q->rear++; q->items(q->rear) = value; ) ) // Removing elements from queue int dequeue(struct queue* q) ( int item; if (isEmpty(q)) ( printf("Queue is empty"); item = -1; ) else ( item = q->items(q->front); q->front++; if (q->front> q->rear) ( printf("Resetting queue "); q->front = q->rear = -1; ) ) return item; ) // Print the queue void printQueue(struct queue* q) ( int i = q->front; if (isEmpty(q)) ( printf("Queue is empty"); ) else ( printf("Queue contains "); for (i = q->front; i rear + 1; i++) ( printf("%d ", q->items(i)); ) ) ) int main() ( struct Graph* graph = createGraph(6); addEdge(graph, 0, 1); addEdge(graph, 0, 2); addEdge(graph, 1, 2); addEdge(graph, 1, 4); addEdge(graph, 1, 3); addEdge(graph, 2, 4); addEdge(graph, 3, 4); bfs(graph, 0); return 0; )

 // BFS algorithm in C++ #include #include using namespace std; class Graph ( int numVertices; list* adjLists; bool* visited; public: Graph(int vertices); void addEdge(int src, int dest); void BFS(int startVertex); ); // Create a graph with given vertices, // and maintain an adjacency list Graph::Graph(int vertices) ( numVertices = vertices; adjLists = new list(vertices); ) // Add edges to the graph void Graph::addEdge(int src, int dest) ( adjLists(src).push_back(dest); adjLists(dest).push_back(src); ) // BFS algorithm void Graph::BFS(int startVertex) ( visited = new bool(numVertices); for (int i = 0; i < numVertices; i++) visited(i) = false; list queue; visited(startVertex) = true; queue.push_back(startVertex); list::iterator i; while (!queue.empty()) ( int currVertex = queue.front(); cout << "Visited " << currVertex << " "; queue.pop_front(); for (i = adjLists(currVertex).begin(); i != adjLists(currVertex).end(); ++i) ( int adjVertex = *i; if (!visited(adjVertex)) ( visited(adjVertex) = true; queue.push_back(adjVertex); ) ) ) ) int main() ( Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(3, 3); g.BFS(2); return 0; )