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

Indholdsfortegnelse

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

I denne vejledning lærer du om bredden første søgealgoritme. Du finder også arbejdseksempler på bfs-algoritme i C, C ++, Java og Python.

Traversal betyder at besøge alle noder i en graf. Breadth First Traversal eller Breadth First Search er en rekursiv algoritme til søgning i alle hjørnerne i en graf eller træstatastruktur.

BFS-algoritme

En standard BFS-implementering sætter hvert toppunkt i grafen i en af to kategorier:

Besøgt
Ikke besøgt

Formålet med algoritmen er at markere hvert toppunkt som besøgt, mens man undgår cyklusser.

Algoritmen fungerer som følger:

Start med at placere en af grafens hjørner bagest i en kø.
Tag det forreste element i køen, og føj det til den besøgte liste.
Opret en liste over toppunktets tilstødende noder. Føj dem, der ikke er på den besøgte liste, bagest i køen.
Gentag trin 2 og 3, indtil køen er tom.

Grafen kan have to forskellige frakoblede dele, så for at sikre, at vi dækker hvert toppunkt, kan vi også køre BFS-algoritmen på hver node

BFS eksempel

Lad os se, hvordan Breadth First Search-algoritmen fungerer med et eksempel. Vi bruger en ikke-rettet graf med 5 hjørner.

Ustyret graf med 5 hjørner

Vi starter fra toppunkt 0, BFS-algoritmen starter med at placere den i listen Besøgte og placere alle de tilstødende hjørner i stakken.

Besøg startpunktet, og tilføj dets tilstødende hjørner til køen

Dernæst besøger vi elementet forrest i køen, dvs. 1 og går til dets tilstødende noder. Da 0 allerede er besøgt, besøger vi 2 i stedet.

Besøg den første nabo til startknude 0, som er 1

Vertex 2 har et ubesøgt tilstødende toppunkt i 4, så vi tilføjer det på bagsiden af køen og besøger 3, som er forrest i køen.

Besøg 2, som blev føjet til køen tidligere for at tilføje sine naboer

4 forbliver i køen

Kun 4 forbliver i køen, da den eneste tilstødende node på 3, dvs. 0, allerede er besøgt. Vi besøger det.

Besøg den sidste resterende vare i stakken for at kontrollere, om den har ubesøgte naboer

Da køen er tom, har vi gennemført grafens bredeste første gennemgang.

BFS pseudokode

 Opret en kø Q-mark v som besøgt og sæt v i Q, mens Q ikke er tom fjern hovedet u af Q-mærket og indkapsl alle (ubesøgte) naboer til u

Python, Java og C / C ++ eksempler

Koden til algoritmen for bredden første søgning med et eksempel er vist nedenfor. Koden er blevet forenklet, så vi kan fokusere på algoritmen snarere end 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; )