BFS-grafalgoritme (med kode i C, C ++, Java og Python)

Innholdsfortegnelse

BFS-algoritme
BFS eksempel
BFS pseudokode
Python, Java og C / C ++ eksempler
BFS algoritmekompleksitet
BFS algoritmeapplikasjoner

I denne veiledningen lærer du om bredden første søkealgoritme. Du finner også eksempler på bfs-algoritme i C, C ++, Java og Python.

Traversal betyr å besøke alle nodene i en graf. Breadth First Traversal eller Breadth First Search er en rekursiv algoritme for å søke i alle toppunktene i en graf eller tredatastruktur.

BFS-algoritme

En standard BFS-implementering setter hvert toppunkt i grafen i en av to kategorier:

Besøkt
Ikke besøkt

Formålet med algoritmen er å merke hvert toppunkt som besøkt mens man unngår sykluser.

Algoritmen fungerer som følger:

Start med å sette en av grafens hjørner bak i køen.
Ta det fremre elementet i køen og legg det til den besøkte listen.
Lag en liste over toppunktets tilstøtende noder. Legg til de som ikke er i den besøkte listen på baksiden av køen.
Gjenta trinn 2 og 3 til køen er tom.

Grafen kan ha to forskjellige frakoblede deler, så for å sikre at vi dekker hvert toppunkt, kan vi også kjøre BFS-algoritmen på hver node

BFS eksempel

La oss se hvordan Breadth First Search-algoritmen fungerer med et eksempel. Vi bruker en ikke-rettet graf med 5 hjørner.

Udirigert graf med 5 hjørner

Vi starter fra toppunkt 0, BFS-algoritmen starter med å sette den i Besøkt-listen og sette alle de tilstøtende toppunktene i stabelen.

Besøk startpunktet og legg de tilstøtende toppunktene til køen

Deretter besøker vi elementet foran køen, dvs. 1 og går til de tilstøtende nodene. Siden 0 allerede er besøkt, besøker vi 2 i stedet.

Besøk den første naboen til startnode 0, som er 1

Vertex 2 har et ubesøkt tilstøtende toppunkt i 4, så vi legger til det på baksiden av køen og besøk 3, som er foran i køen.

Besøk 2 som ble lagt til i køen tidligere for å legge til naboene

4 forblir i køen

Bare 4 gjenstår i køen siden den eneste tilstøtende noden på 3, dvs. 0, allerede er besøkt. Vi besøker den.

Besøk den gjenværende gjenstanden i bunken for å sjekke om den har ubesøkte naboer

Siden køen er tom, har vi fullført Breadth First Traversal i grafen.

BFS pseudokode

 opprett en kø Q-mark v som besøkt og legg v inn i Q mens Q ikke er tom fjern hodet u av Q-merket og innkjør alle (ubesøkte) naboer til u

Python, Java og C / C ++ eksempler

Koden for Breadth First Search Algorithm med et eksempel er vist nedenfor. Koden er forenklet slik at vi kan fokusere på algoritmen i stedet for andre detaljer.

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