


Implementing BFS using vectors and queues, following the implementation of the CLRS algorithm in a C program
In the CLRS book, the BFS algorithm is described using vectors and queues. We have to use C STL to implement this algorithm. First let's look at the algorithm.
Algorithm
BFS(G, s) −
begin for each vertex u in G.V - {s}, do u.color := white u.d := infinity u.p := NIL done s.color := green s.d := 0 s.p := NIL Q := NULL insert s into Q while Q is not null, do u = delete from Q for each v in adjacent to u, do if v.color = white v.color := green v.d := u.d + 1 v.p := u insert v into Q end if done u.color = dark_green done end
Example
’s Chinese translation is:Example
#include<iostream> #include<vector> #include<queue> using namespace std; vector<string> colour; vector<int> dist; vector<int> par; void addEdge(vector <int> g[], int u, int v) { //add edge to form the graph g[u].push_back(v); g[v].push_back(u); } void BFS(vector <int> g[], int s) { queue<int> q; q.push(s); //insert source dist[s] = 0; colour[s] = "gray"; while (!q.empty()) { int u = q.front(); //top element from queue, then delete it q.pop(); cout << u << " "; for (auto i = g[u].begin(); i != g[u].end(); i++) { if (colour[*i] == "white") { //white is unvisited node colour[*i] = "gray"; //gray is visited but not completed dist[*i] = dist[u] + 1; par[*i] = u; q.push(*i); } } colour[u] = "black"; //black is completed node } } void BFSAlgo(vector <int> g[], int n) { colour.assign(n, "white"); //put as unvisited dist.assign(n, 0); par.assign(n, -1); for (int i = 0; i < n; i++) if (colour[i] == "white") BFS(g, i); } int main() { int n = 7; vector <int> g[n]; addEdge(g, 0, 1); addEdge(g, 0, 2); addEdge(g, 1, 3); addEdge(g, 1, 4); addEdge(g, 2, 5); addEdge(g, 2, 6); BFSAlgo(g, n); }
Output
0 1 2 3 4 5 6
The above is the detailed content of Implementing BFS using vectors and queues, following the implementation of the CLRS algorithm in a C program. For more information, please follow other related articles on the PHP Chinese website!

Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

AI Hentai Generator
Generate AI Hentai for free.

Hot Article

Hot Tools

Notepad++7.3.1
Easy-to-use and free code editor

SublimeText3 Chinese version
Chinese version, very easy to use

Zend Studio 13.0.1
Powerful PHP integrated development environment

Dreamweaver CS6
Visual web development tools

SublimeText3 Mac version
God-level code editing software (SublimeText3)

Hot Topics

Laravel is a very popular PHP development framework. It provides rich functions and convenient development methods, which can help developers quickly build stable and reliable web applications. During the development process of Laravel, it is very important to use cache and queue properly. This article will introduce some precautions to help developers make better use of cache and queue. 1. Reasonable use of cache The definition and function of cache Cache is a technology that temporarily stores frequently used data in memory, which can greatly improve the response speed of the system.

Introduction to application scenarios of dead letter queues and delay queues in PHP and MySQL As Internet applications become more and more complex, the need to process a large number of messages and tasks is growing day by day. As a solution, queues can effectively implement asynchronous processing of tasks and improve the scalability and stability of the system. In queue applications, two common concepts are dead letter queues and delay queues. This article will introduce the application scenarios of these two concepts in PHP and MySQL, and provide specific code examples. The application scenarios of the dead letter queue are:

In the CLRS book, the BFS algorithm is described using vectors and queues. We have to use C++STL to implement this algorithm. First let's look at the algorithm. Algorithm BFS(G,s)−begin foreachvertexuinG.V-{s},do u.color:=white u.d:=infinity u.p:=NI

Queue's implementation of message filtering and message routing in PHP and MySQL With the rapid development of the Internet, message queue (MessageQueue), as an important communication mechanism, plays a crucial role in Web development. Message queues can be used to implement functions such as decoupling, peak shaving, and asynchronous processing. This article will introduce how to implement message filtering and message routing in PHP and MySQL, and provide specific code examples. Message queue Message queue is a typical "producer-consumer" model

Application scenarios of queue message persistence and message deduplication in PHP and MySQL Queue is a common data structure and is widely used in asynchronous message processing, task scheduling, log collection and other scenarios in software development. Among them, message persistence and message deduplication are two important features of the queue, which can ensure message reliability and data consistency. In PHP and MySQL, queue applications can use Redis as the message middleware and MySQL to store and manage queue metadata. Specific examples are as follows. first

A stack is a subclass of the Vector class and represents a last-in-first-out (LIFO) stack of objects. The last element added to the top of the stack (In) can be the first element removed from the stack (Out). The Queue class extends the Collection interface and supports insertion and deletion operations using first-in-first-out (FIFO). We can also use queues to implement stacks in the following program. Example importjava.util.*;publicclassStackFromQueueTest{ Queuequeue=newLinkedList();

Introduction to stacks and queues in C++ Stacks and queues are commonly used data structures in C++, and they are widely used in programs. This article will introduce the concepts, usage and application scenarios of stacks and queues in detail. 1. The concept of stack Stack (Stack) is a linear data structure, which has the characteristics of "first in, last out". In the stack, the data pushed into the stack is closer to the bottom of the stack; the data pushed into the stack later is closer to the top of the stack. The main operations of the stack are push and pop. Pushing is to add data to the stack, and popping

How to handle message accumulation and congestion control in queues in PHP and MySQL. With the rapid development of the Internet, the number of users of various websites and applications continues to increase, which puts higher requirements on the load capacity of the server. In this context, message queues have become a commonly used solution to solve the problem of message accumulation and congestion under high concurrent access. This article will introduce how to handle message accumulation and congestion control of queues in PHP and MySQL, and give specific code examples. In PHP we can use Re
