Algoritmo de gráfico BFS (con código en C, C ++, Java y Python)

Tabla de contenido

Algoritmo BFS
Ejemplo de BFS
Pseudocódigo BFS
Ejemplos de Python, Java y C / C ++
Complejidad del algoritmo BFS
Aplicaciones del algoritmo BFS

En este tutorial, aprenderá sobre el algoritmo de búsqueda primero en amplitud. Además, encontrará ejemplos prácticos del algoritmo bfs en C, C ++, Java y Python.

Recorrer significa visitar todos los nodos de un gráfico. Breadth First Traversal o Breadth First Search es un algoritmo recursivo para buscar todos los vértices de un gráfico o estructura de datos de árbol.

Algoritmo BFS

Una implementación estándar de BFS coloca cada vértice del gráfico en una de dos categorías:

Visitó
No visitado

El propósito del algoritmo es marcar cada vértice como visitado evitando ciclos.

El algoritmo funciona de la siguiente manera:

Comience colocando cualquiera de los vértices del gráfico al final de una cola.
Tome el elemento del frente de la cola y agréguelo a la lista de visitas.
Cree una lista de los nodos adyacentes de ese vértice. Agregue los que no están en la lista de visitas al final de la cola.
Siga repitiendo los pasos 2 y 3 hasta que la cola esté vacía.

El gráfico puede tener dos partes desconectadas diferentes, por lo que para asegurarnos de cubrir cada vértice, también podemos ejecutar el algoritmo BFS en cada nodo

Ejemplo de BFS

Veamos cómo funciona el algoritmo Breadth First Search con un ejemplo. Usamos un gráfico no dirigido con 5 vértices.

Gráfico no dirigido con 5 vértices

Partimos del vértice 0, el algoritmo BFS comienza poniéndolo en la lista de Visitas y poniendo todos sus vértices adyacentes en la pila.

Visite el vértice inicial y agregue sus vértices adyacentes a la cola

A continuación, visitamos el elemento al principio de la cola, es decir, 1 y vamos a sus nodos adyacentes. Como ya se ha visitado 0, visitamos 2 en su lugar.

Visite el primer vecino del nodo de inicio 0, que es 1

El vértice 2 tiene un vértice adyacente no visitado en 4, así que lo agregamos al final de la cola y visitamos 3, que está al principio de la cola.

Visita 2 que se agregó a la cola antes para agregar sus vecinos

4 permanece en la cola

Solo 4 permanece en la cola, ya que el único nodo adyacente de 3, es decir, 0 ya está visitado. Lo visitamos.

Visite el último elemento restante en la pila para verificar si tiene vecinos no visitados

Dado que la cola está vacía, hemos completado el primer recorrido en anchura del gráfico.

Pseudocódigo BFS

 crear una cola Q marcar v como visitado y poner v en Q mientras Q no está vacío quitar la cabeza u de la marca Q y poner en cola todos los vecinos (no visitados) de u

Ejemplos de Python, Java y C / C ++

El código para el algoritmo de búsqueda Breadth First con un ejemplo se muestra a continuación. El código se ha simplificado para que podamos centrarnos en el algoritmo en lugar de otros detalles.

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; )