Algoritm grafic BFS (Cu cod în C, C ++, Java și Python)

Cuprins

Algoritm BFS
Exemplu BFS
Pseudocod BFS
Exemple Python, Java și C / C ++
Complexitatea algoritmului BFS
Aplicații de algoritm BFS

În acest tutorial, veți afla despre algoritmul de căutare a lățimii întâi. De asemenea, veți găsi exemple de lucru ale algoritmului bfs în C, C ++, Java și Python.

Traversal înseamnă a vizita toate nodurile unui grafic. Breadth First Traversal sau Breadth First Search este un algoritm recursiv pentru căutarea tuturor vârfurilor unui grafic sau a unei structuri de date arborescente.

Algoritm BFS

O implementare standard BFS pune fiecare vârf al graficului în una din cele două categorii:

Vizitat
Nu a fost vizitat

Scopul algoritmului este de a marca fiecare vârf ca fiind vizitat evitând ciclurile.

Algoritmul funcționează după cum urmează:

Începeți prin a pune oricare dintre vârfurile graficului în spatele unei cozi.
Luați elementul din față al cozii și adăugați-l la lista vizitată.
Creați o listă a nodurilor adiacente ale vârfului respectiv. Adăugați pe cele care nu sunt în lista vizitată în spatele cozii.
Repetați pașii 2 și 3 până când coada este goală.

Graficul ar putea avea două părți diferite deconectate, astfel încât să ne asigurăm că acoperim fiecare vârf, putem rula și algoritmul BFS pe fiecare nod

Exemplu BFS

Să vedem cum funcționează algoritmul Breadth First Search cu un exemplu. Folosim un grafic neorientat cu 5 vârfuri.

Grafic nedirectat cu 5 vârfuri

Începem de la vârful 0, algoritmul BFS începe prin a-l pune în lista Vizitat și a pune toate vârfurile adiacente în stivă.

Accesați vârful de pornire și adăugați vârfurile adiacente la coadă

Apoi, vizităm elementul din partea din față a cozii, adică 1 și mergem la nodurile sale adiacente. Deoarece 0 a fost deja vizitat, vizităm în schimb 2.

Vizitați primul vecin al nodului de pornire 0, care este 1

Vertex 2 are un vârf adiacent nevizitat în 4, așa că îl adăugăm în partea din spate a cozii și vizităm 3, care se află în partea din față a cozii.

Vizita 2 care a fost adăugată la coadă mai devreme pentru a adăuga vecinii săi

4 rămâne în coadă

Doar 4 rămâne în coadă, deoarece singurul nod adiacent de 3 adică 0 este deja vizitat. O vizităm.

Vizitați ultimul articol rămas în stivă pentru a verifica dacă are vecini nevizitați

Deoarece coada este goală, am finalizat Breadth First Traversal al graficului.

Pseudocod BFS

 creați o coadă Q marca v așa cum a fost vizitată și puneți v în Q în timp ce Q este ne-gol eliminați capul u al marcii Q și puneți în coadă toți vecinii (nevizitați)

Exemple Python, Java și C / C ++

Codul pentru algoritmul Breadth First Search cu un exemplu este prezentat mai jos. Codul a fost simplificat astfel încât să ne putem concentra asupra algoritmului mai degrabă decât asupra altor detalii.

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