In diesem Tutorial lernen Sie den Algorithmus für die Breitensuche kennen. Außerdem finden Sie Arbeitsbeispiele für den bfs-Algorithmus in C, C ++, Java und Python.
Durchqueren bedeutet, alle Knoten eines Graphen zu besuchen. Breadth First Traversal oder Breadth First Search ist ein rekursiver Algorithmus zum Durchsuchen aller Scheitelpunkte eines Diagramms oder einer Baumdatenstruktur.
BFS-Algorithmus
Bei einer Standard-BFS-Implementierung wird jeder Scheitelpunkt des Diagramms in eine von zwei Kategorien eingeteilt:
- hat besucht
- Nicht besucht
Der Zweck des Algorithmus besteht darin, jeden Scheitelpunkt als besucht zu markieren und dabei Zyklen zu vermeiden.
Der Algorithmus funktioniert wie folgt:
- Beginnen Sie, indem Sie einen der Scheitelpunkte des Diagramms am Ende einer Warteschlange platzieren.
- Nehmen Sie das vordere Element der Warteschlange und fügen Sie es der besuchten Liste hinzu.
- Erstellen Sie eine Liste der benachbarten Knoten dieses Scheitelpunkts. Fügen Sie diejenigen, die nicht in der besuchten Liste enthalten sind, am Ende der Warteschlange hinzu.
- Wiederholen Sie die Schritte 2 und 3 so lange, bis die Warteschlange leer ist.
Das Diagramm kann zwei verschiedene getrennte Teile enthalten. Um sicherzustellen, dass wir jeden Scheitelpunkt abdecken, können wir den BFS-Algorithmus auch auf jedem Knoten ausführen
BFS-Beispiel
Lassen Sie uns anhand eines Beispiels sehen, wie der Algorithmus für die Breitensuche funktioniert. Wir verwenden einen ungerichteten Graphen mit 5 Eckpunkten.
Ungerichteter Graph mit 5 Eckpunkten
Wir beginnen mit Scheitelpunkt 0, der BFS-Algorithmus beginnt damit, ihn in die Liste "Besucht" aufzunehmen und alle benachbarten Scheitelpunkte in den Stapel zu legen.
Besuchen Sie den Startscheitelpunkt und fügen Sie die benachbarten Scheitelpunkte zur Warteschlange hinzu
Als nächstes besuchen wir das Element an der Vorderseite der Warteschlange, dh 1, und gehen zu den benachbarten Knoten. Da 0 bereits besucht wurde, besuchen wir stattdessen 2.
Besuchen Sie den ersten Nachbarn des Startknotens 0, der 1 ist
Scheitelpunkt 2 hat einen nicht besuchten benachbarten Scheitelpunkt in 4, daher fügen wir diesen hinten in der Warteschlange hinzu und besuchen 3, der sich vorne in der Warteschlange befindet.
Besuch 2, der früher zur Warteschlange hinzugefügt wurde, um seine Nachbarn 
4 hinzuzufügen, bleibt in der Warteschlange
Es verbleiben nur 4 in der Warteschlange, da der einzige benachbarte Knoten von 3, dh 0, bereits besucht ist. Wir besuchen es.
Besuchen Sie das letzte verbleibende Element im Stapel, um zu überprüfen, ob es nicht besuchte Nachbarn hat
Da die Warteschlange leer ist, haben wir die Breite der ersten Durchquerung des Diagramms abgeschlossen.
BFS-Pseudocode
Erstellen Sie eine Warteschlange Q-Markierung v als besucht und setzen Sie v in Q, während Q nicht leer ist. Entfernen Sie den Kopf u der Q-Markierung und stellen Sie alle (nicht besuchten) Nachbarn von u in die Warteschlange
Beispiele für Python, Java und C / C ++
Der Code für den Breadth First Search-Algorithmus mit einem Beispiel ist unten dargestellt. Der Code wurde vereinfacht, damit wir uns eher auf den Algorithmus als auf andere Details konzentrieren können.
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; )
Komplexität des BFS-Algorithmus
Die zeitliche Komplexität des BFS-Algorithmus wird in Form von dargestellt O(V + E), wobei V die Anzahl der Knoten und E die Anzahl der Kanten ist.
Die räumliche Komplexität des Algorithmus ist O(V).
BFS-Algorithmus-Anwendungen
- Index nach Suchindex erstellen
- Für die GPS-Navigation
- Pfadfindungsalgorithmen
- Im Ford-Fulkerson-Algorithmus, um den maximalen Fluss in einem Netzwerk zu finden
- Zykluserkennung in einem ungerichteten Diagramm
- Im minimalen Spannbaum
