BFS algoritam grafikona (s kodom na C, C ++, Java i Python)

Sadržaj

BFS algoritam
BFS primjer
BFS pseudokod
Primjeri Pythona, Java i C / C ++
Složenost algoritma BFS
Primjene BFS algoritma

U ovom vodiču naučit ćete o algoritmu pretraživanja po širini. Također ćete naći radne primjere bfs algoritma na C, C ++, Java i Python.

Prelazak znači posjećivanje svih čvorova grafa. Prijelaz u širinu ili Prvo pretraživanje u širini rekurzivni je algoritam za pretraživanje svih vrhova strukture podataka grafa ili stabla.

BFS algoritam

Standardna implementacija BFS-a stavlja svaki vrh grafa u jednu od dvije kategorije:

Posjećeno
Nije posjećeno

Svrha algoritma je označiti svaki vrh kao posjećen uz izbjegavanje ciklusa.

Algoritam radi na sljedeći način:

Započnite stavljanjem bilo kojeg od vrhova grafa na stražnju stranu reda.
Uzmite prednju stavku u redu i dodajte je na posjećeni popis.
Stvorite popis susjednih čvorova tog vrha. Dodajte one koji nisu na posjećenom popisu na stražnji dio reda.
Ponavljajte korake 2 i 3 dok se red ne isprazni.

Graf može imati dva različita odvojena dijela, tako da bismo bili sigurni da pokrivamo svaki vrh, također možemo pokrenuti BFS algoritam na svakom čvoru

BFS primjer

Pogledajmo kako na primjeru radi algoritam za prvo pretraživanje. Koristimo neusmjereni graf s 5 vrhova.

Neusmjereni graf s 5 vrhova

Polazimo od vrha 0, BFS algoritam započinje stavljanjem na popis Posjećeno i stavljanjem svih susjednih vrhova u stog.

Posjetite početni vrh i dodajte njegove susjedne vrhove u red čekanja

Dalje, posjetimo element na čekanju reda tj. 1 i idemo do njegovih susjednih čvorova. Budući da je 0 već posjećeno, umjesto njih posjetimo 2.

Posjetite prvog susjeda početnog čvora 0, koji je 1

Vrh 2 ima ne posjećeni susjedni vrh u 4, pa to dodamo stražnjem dijelu reda i posjetimo 3, koji se nalazi ispred čekanog reda.

Posjet 2 koji je ranije dodan u red za dodavanje susjeda

4 ostaje u redu

Samo 4 ostaje u redu jer je jedini susjedni čvor od 3, tj. 0 već posjećen. Posjećujemo ga.

Posjetite posljednju preostalu stavku u hrpi kako biste provjerili ima li neposjećenih susjeda

Budući da je red prazan, dovršili smo prvo prelaženje širine grafikona.

BFS pseudokod

 stvorite red Q oznake v po posjećenosti i stavite v Q dok Q nije prazan uklonite glavu u oznake Q i stavite u red sve (neposjećene) susjede u

Primjeri Pythona, Java i C / C ++

Kôd algoritma za prvo pretraživanje širine s primjerom prikazan je u nastavku. Kôd je pojednostavljen tako da se možemo usredotočiti na algoritam, a ne na druge pojedinosti.

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