BFS-diagramalgoritm (med kod i C, C ++, Java och Python)

Innehållsförteckning

BFS-algoritm
BFS-exempel
BFS-pseudokod
Python, Java och C / C ++ exempel
BFS-algoritmkomplexitet
BFS-algoritmapplikationer

I den här handledningen lär du dig om bredden första sökalgoritmen. Du hittar också arbetsexempel på bfs-algoritm i C, C ++, Java och Python.

Traversal betyder att besöka alla noder i ett diagram. Breadth First Traversal eller Breadth First Search är en rekursiv algoritm för att söka i alla hörn i en graf eller träddatastruktur.

BFS-algoritm

En standard BFS-implementering placerar varje toppunkt i diagrammet i en av två kategorier:

Besökta
Inte besökt

Syftet med algoritmen är att markera varje toppunkt som besökt medan man undviker cykler.

Algoritmen fungerar enligt följande:

Börja med att placera någon av grafens hörn på baksidan av en kö.
Ta det främsta objektet i kön och lägg till det i den besökta listan.
Skapa en lista med toppunktens intilliggande noder. Lägg till de som inte finns i den besökta listan längst bak i kön.
Fortsätt upprepa steg 2 och 3 tills kön är tom.

Grafen kan ha två olika frånkopplade delar så för att se till att vi täcker varje toppunkt kan vi också köra BFS-algoritmen på varje nod

BFS-exempel

Låt oss se hur Breadth First Search-algoritmen fungerar med ett exempel. Vi använder en oriktad graf med 5 hörn.

Oriktad graf med 5 hörn

Vi börjar från vertex 0, BFS-algoritmen börjar med att placera den i listan Besökta och lägga alla dess intilliggande hörn i stacken.

Besök startpunkten och lägg till dess intilliggande hörn i kö

Därefter besöker vi elementet framför kön, dvs. 1 och går till dess intilliggande noder. Eftersom 0 redan har besökts besöker vi 2 istället.

Besök den första grannen till startnod 0, som är 1

Vertex 2 har ett obesökt intilliggande toppunkt i 4, så vi lägger till det på baksidan av kön och besök 3, som ligger längst fram i kön.

Besök 2 som lades till i kön tidigare för att lägga till sina grannar

4 förblir i kön

Endast 4 finns kvar i kön eftersom den enda intilliggande noden på 3, dvs 0, redan är besökt. Vi besöker den.

Besök sista återstående föremålet i stacken för att kontrollera om det har obesökta grannar

Eftersom kön är tom har vi slutfört Breadth First Traversal i diagrammet.

BFS-pseudokod

 skapa en kö Q-markering v som besökt och placera v i Q medan Q är icke-tom ta bort huvudet på Q-markeringen och inkapsla alla (obesökta) grannar till u

Python, Java och C / C ++ exempel

Koden för algoritmen för Breadth First Search med ett exempel visas nedan. Koden har förenklats så att vi kan fokusera på algoritmen snarare än andra 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; )