Algoritmo de gráfico BFS (com código em C, C ++, Java e Python)

Índice

Algoritmo BFS
Exemplo BFS
Pseudocódigo BFS
Exemplos de Python, Java e C / C ++
Complexidade de Algoritmo BFS
Aplicativos de algoritmo BFS

Neste tutorial, você aprenderá sobre o algoritmo de pesquisa em amplitude. Além disso, você encontrará exemplos funcionais do algoritmo BFS em C, C ++, Java e Python.

Traversal significa visitar todos os nós de um gráfico. Breadth First Traversal ou Breadth First Search é um algoritmo recursivo para pesquisar todos os vértices de um gráfico ou estrutura de dados em árvore.

Algoritmo BFS

Uma implementação BFS padrão coloca cada vértice do gráfico em uma de duas categorias:

Visitou
Não visitou

O objetivo do algoritmo é marcar cada vértice como visitado, evitando ciclos.

O algoritmo funciona da seguinte maneira:

Comece colocando qualquer um dos vértices do gráfico no final de uma fila.
Pegue o item da frente da fila e adicione-o à lista de visitados.
Crie uma lista dos nós adjacentes desse vértice. Adicione aqueles que não estão na lista de visitados no final da fila.
Continue repetindo as etapas 2 e 3 até que a fila esteja vazia.

O gráfico pode ter duas partes desconectadas diferentes, portanto, para garantir que cobriremos todos os vértices, também podemos executar o algoritmo BFS em cada nó

Exemplo BFS

Vamos ver como o algoritmo de primeira pesquisa de amplitude funciona com um exemplo. Usamos um gráfico não direcionado com 5 vértices.

Gráfico não direcionado com 5 vértices

Começamos no vértice 0, o algoritmo BFS começa colocando-o na lista de Visitados e colocando todos os seus vértices adjacentes na pilha.

Visite start vertex e adicione seus vértices adjacentes à fila

Em seguida, visitamos o elemento na frente da fila, isto é, 1 e vamos para seus nós adjacentes. Como 0 já foi visitado, visitamos 2 em seu lugar.

Visite o primeiro vizinho do nó inicial 0, que é 1

O vértice 2 possui um vértice adjacente não visitado em 4, portanto, adicionamos isso ao final da fila e visitamos 3, que está na frente da fila.

A visita 2, que foi adicionada à fila anteriormente para adicionar seus vizinhos

4, permanece na fila

Apenas 4 permanecem na fila, pois o único nó adjacente de 3, ou seja, 0, já foi visitado. Nós o visitamos.

Visite o último item restante na pilha para verificar se há vizinhos não visitados

Como a fila está vazia, concluímos a primeira travessia em amplitude do gráfico.

Pseudocódigo BFS

 crie uma fila Q marque v como visitado e coloque v em Q enquanto Q não estiver vazio remova a cabeça u da marca Q e enfileire todos os vizinhos (não visitados) de u

Exemplos de Python, Java e C / C ++

O código para o algoritmo de primeira pesquisa de amplitude com um exemplo é mostrado abaixo. O código foi simplificado para que possamos nos concentrar no algoritmo em vez de outros detalhes.

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