Table of Contents
Algorithm
Example
Output
Home Backend Development C++ Implementing BFS using vectors and queues, following the implementation of the CLRS algorithm in a C program

Implementing BFS using vectors and queues, following the implementation of the CLRS algorithm in a C program

Sep 06, 2023 pm 04:37 PM
queue vector bfs (breadth-first search)

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
Copy after login

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);
}
Copy after login

Output

0 1 2 3 4 5 6
Copy after login

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!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
4 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
4 weeks ago By 尊渡假赌尊渡假赌尊渡假赌

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Laravel development notes: Proper use of cache and queue Laravel development notes: Proper use of cache and queue Nov 22, 2023 am 11:46 AM

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.

Application scenarios of dead letter queue and delay queue in PHP and MySQL Application scenarios of dead letter queue and delay queue in PHP and MySQL Oct 15, 2023 am 11:46 AM

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:

Implementing BFS using vectors and queues, following the implementation of the CLRS algorithm in a C program Implementing BFS using vectors and queues, following the implementation of the CLRS algorithm in a C program Sep 06, 2023 pm 04:37 PM

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

How to implement queue message filtering and message routing in PHP and MySQL How to implement queue message filtering and message routing in PHP and MySQL Oct 15, 2023 pm 04:55 PM

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 Application scenarios of queue message persistence and message deduplication in PHP and MySQL Oct 15, 2023 pm 01:42 PM

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

How can we implement stack using queue in Java? How can we implement stack using queue in Java? Aug 25, 2023 pm 05:05 PM

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

Stack and Queue in C++ Stack and Queue in C++ Aug 22, 2023 am 11:00 AM

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 queue message accumulation and congestion control in PHP and MySQL How to handle queue message accumulation and congestion control in PHP and MySQL Oct 15, 2023 am 09:24 AM

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

See all articles