Algorithme BFS Graph (avec code en C, C ++, Java et Python)

Table des matières

Algorithme BFS
Exemple BFS
Pseudocode BFS
Exemples Python, Java et C / C ++
Complexité de l'algorithme BFS
Applications d'algorithme BFS

Dans ce didacticiel, vous découvrirez le premier algorithme de recherche en largeur. Vous trouverez également des exemples fonctionnels de l'algorithme bfs en C, C ++, Java et Python.

Traverser signifie visiter tous les nœuds d'un graphe. Breadth First Traversal ou Breadth First Search est un algorithme récursif pour rechercher tous les sommets d'un graphe ou d'une arborescence de données.

Algorithme BFS

Une implémentation BFS standard place chaque sommet du graphe dans l'une des deux catégories suivantes:

A visité
Non visité

Le but de l'algorithme est de marquer chaque sommet comme visité tout en évitant les cycles.

L'algorithme fonctionne comme suit:

Commencez par placer l'un des sommets du graphe au fond d'une file d'attente.
Prenez le premier élément de la file d'attente et ajoutez-le à la liste visitée.
Créez une liste des nœuds adjacents de ce sommet. Ajoutez ceux qui ne sont pas dans la liste visitée à l'arrière de la file d'attente.
Répétez les étapes 2 et 3 jusqu'à ce que la file d'attente soit vide.

Le graphique peut avoir deux parties déconnectées différentes, donc pour nous assurer que nous couvrons chaque sommet, nous pouvons également exécuter l'algorithme BFS sur chaque nœud

Exemple BFS

Voyons comment fonctionne l'algorithme Breadth First Search avec un exemple. Nous utilisons un graphe non orienté avec 5 sommets.

Graphique non orienté avec 5 sommets

Nous partons du sommet 0, l'algorithme BFS commence par le mettre dans la liste Visited et mettre tous ses sommets adjacents dans la pile.

Visitez le sommet de départ et ajoutez ses sommets adjacents à la file d'attente

Ensuite, nous visitons l'élément à l'avant de la file d'attente, c'est-à-dire 1 et allons vers ses nœuds adjacents. Puisque 0 a déjà été visité, nous en visitons 2 à la place.

Visitez le premier voisin du nœud de départ 0, qui est 1

Le sommet 2 a un sommet adjacent non visité dans 4, nous l'ajoutons donc à l'arrière de la file d'attente et visitons 3, qui se trouve au début de la file d'attente.

Visite 2 qui a été ajoutée à la file d'attente plus tôt pour ajouter ses voisins

4 reste dans la file d'attente

Il ne reste plus que 4 dans la file d'attente puisque le seul nœud adjacent de 3 c'est-à-dire 0 est déjà visité. Nous le visitons.

Visitez le dernier élément restant dans la pile pour vérifier s'il a des voisins non visités

Puisque la file d'attente est vide, nous avons terminé la traversée en largeur en premier du graphe.

Pseudocode BFS

 créer une file d'attente Q marquer v comme visité et mettre v dans Q alors que Q n'est pas vide supprimer la tête u de la marque Q et mettre en file d'attente tous les voisins (non visités) de u

Exemples Python, Java et C / C ++

Le code de l'algorithme de recherche en largeur d'abord avec un exemple est illustré ci-dessous. Le code a été simplifié afin que nous puissions nous concentrer sur l'algorithme plutôt que sur d'autres détails.

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