Algoritmus grafu BFS (s kódom v jazykoch C, C ++, Java a Python)

Obsah

Algoritmus BFS
Príklad BFS
BFS pseudokód
Príklady jazyka Python, Java a C / C ++
Zložitosť algoritmu BFS
Aplikácie algoritmu BFS

V tomto výučbe sa dozviete o algoritme vyhľadávania prvého šírky. Nájdete tiež pracovné príklady algoritmu bfs v jazykoch C, C ++, Java a Python.

Traverz znamená návštevu všetkých uzlov grafu. Breadth First Traversal alebo Breadth First Search je rekurzívny algoritmus na prehľadávanie všetkých vrcholov grafu alebo stromovej dátovej štruktúry.

Algoritmus BFS

Štandardná implementácia BFS stavia každý vrchol grafu do jednej z dvoch kategórií:

Navštívené
Nenavštívené

Účelom algoritmu je označiť každý vrchol ako navštívený, pričom sa treba vyhnúť cyklom.

Algoritmus funguje nasledovne:

Začnite umiestnením ktoréhokoľvek z vrcholov grafu na koniec poradia.
Vezmite prednú položku vo fronte a pridajte ju do zoznamu navštívených.
Vytvorte zoznam susedných uzlov tohto vrcholu. Do zadnej časti frontu pridajte tie, ktoré nie sú v zozname navštívených.
Opakujte kroky 2 a 3, až kým nebude rad prázdny.

Graf môže mať dve rôzne odpojené časti, aby sme zaistili, že pokryjeme každý vrchol, môžeme tiež spustiť algoritmus BFS na každom uzle

Príklad BFS

Pozrime sa, ako algoritmus Breadth First Search funguje na príklade. Používame neorientovaný graf s 5 vrcholmi.

Neusmernený graf s 5 vrcholmi

Začíname od vrcholu 0, algoritmus BFS začína vložením do zoznamu Navštívené a vložením všetkých jeho susedných vrcholov do zásobníka.

Navštívte začiatočný vrchol a pridajte jeho susedné vrcholy do poradia

Ďalej navštívime prvok v prednej časti fronty, tj. 1, a prejdeme k jeho susedným uzlom. Pretože 0 už bola navštívená, navštívime radšej 2.

Navštívte prvého suseda štartovacieho uzla 0, ktorý je 1

Vrchol 2 má nenavštívený susedný vrchol v 4, takže ho pridáme do zadnej časti frontu a navštívime 3, ktorá je v prednej časti frontu.

Navštívte 2, ktorá bola pridaná do poradia skôr, aby ste pridali svojich susedov

4, zostáva vo fronte

Vo fronte zostávajú iba 4, pretože jediný susedný uzol 3, tj. 0, je už navštívený. My to navštevujeme.

Navštívte poslednú zvyšnú položku v zásobníku a skontrolujte, či nemá nenavštívených susedov

Pretože je fronta prázdna, dokončili sme šírku prvého prechodu grafu.

BFS pseudokód

 vytvorte frontu Q značka v ako navštívená a vložte v do Q, zatiaľ čo Q nie je prázdna, odstráňte hlavu u značky Q a zaradte všetkých (nenavštívených) susedov u

Príklady jazyka Python, Java a C / C ++

Kód pre algoritmus vyhľadávania prvého šírky s príkladom je uvedený nižšie. Kód bol zjednodušený, aby sme sa mohli sústrediť na algoritmus a nie na ďalšie podrobnosti.

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