BFS Graph Algorithm (met code in C, C ++, Java en Python)

Inhoudsopgave

BFS-algoritme
BFS voorbeeld
BFS-pseudocode
Python, Java en C / C ++ voorbeelden
Complexiteit van het BFS-algoritme
BFS-algoritme-toepassingen

In deze zelfstudie leert u over het zoekalgoritme voor breedte eerst. Ook vindt u werkende voorbeelden van bfs-algoritme in C, C ++, Java en Python.

Traversal betekent het bezoeken van alle knooppunten van een grafiek. Breadth First Traversal of Breadth First Search is een recursief algoritme voor het doorzoeken van alle hoekpunten van een grafiek of boomgegevensstructuur.

BFS-algoritme

Een standaard BFS-implementatie plaatst elk hoekpunt van de grafiek in een van de twee categorieën:

Bezocht
Niet bezocht

Het doel van het algoritme is om elk hoekpunt te markeren als bezocht terwijl cycli worden vermeden.

Het algoritme werkt als volgt:

Begin door een van de hoekpunten van de grafiek achter in een wachtrij te plaatsen.
Neem het voorste item van de wachtrij en voeg het toe aan de bezochte lijst.
Maak een lijst met de aangrenzende knooppunten van dat hoekpunt. Voeg degenen die niet in de bezochte lijst staan toe aan de achterkant van de wachtrij.
Blijf stap 2 en 3 herhalen totdat de wachtrij leeg is.

De grafiek kan twee verschillende losgekoppelde delen hebben, dus om ervoor te zorgen dat we elk hoekpunt bedekken, kunnen we ook het BFS-algoritme op elk knooppunt uitvoeren

BFS voorbeeld

Laten we eens kijken hoe het Breadth First Search-algoritme werkt met een voorbeeld. We gebruiken een ongerichte graaf met 5 hoekpunten.

Ongerichte graaf met 5 hoekpunten

We beginnen bij hoekpunt 0, het BFS-algoritme begint door het in de lijst Bezocht te plaatsen en alle aangrenzende hoekpunten in de stapel te plaatsen.

Bezoek het startpunt en voeg de aangrenzende hoekpunten toe aan de wachtrij

Vervolgens bezoeken we het element vooraan in de wachtrij, dwz 1, en gaan naar de aangrenzende knooppunten. Aangezien 0 al is bezocht, bezoeken we er 2.

Bezoek de eerste buur van startknooppunt 0, dat is 1

Vertex 2 heeft een niet-bezocht aangrenzend hoekpunt in 4, dus we voegen dat toe aan de achterkant van de wachtrij en bezoek 3, dat vooraan in de wachtrij staat.

Bezoek 2 dat eerder aan de wachtrij is toegevoegd om zijn buren toe te voegen

4 blijft in de wachtrij staan

Slechts 4 blijft in de wachtrij staan aangezien het enige aangrenzende knooppunt van 3 dwz 0 al bezocht is. We bezoeken het.

Bezoek het laatst overgebleven item in de stapel om te controleren of het onbezochte buren heeft

Omdat de wachtrij leeg is, hebben we de breedte eerste doorgang van de grafiek voltooid.

BFS-pseudocode

 maak een wachtrij Q markeer v als bezocht en plaats v in Q terwijl Q niet leeg is verwijder de kop u van Q markeer en zet alle (onbezochte) buren van u in de wachtrij

Python, Java en C / C ++ voorbeelden

De code voor het Breadth First Search-algoritme met een voorbeeld wordt hieronder weergegeven. De code is vereenvoudigd, zodat we ons op het algoritme kunnen concentreren in plaats van op andere details.

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