Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
STL (Standard Template Library)
2.1.
C++ STL Overview
3.
Competitive programming (CP) 
4.
BFS implementation in STL using a queue and a vector
5.
Implementation
6.
Complexity
6.1.
Time complexity
6.2.
Space Complexity
7.
Frequently Asked Questions
7.1.
Why do we use BFS to find the shortest path? 
7.2.
What is the Graph's shortest path? 
7.3.
Can STL be used for programming competitions? 
7.4.
Why do we use STL?
7.5.
Does Depth-First Search identify the shortest route? 
8.
Conclusion
Last Updated: Mar 27, 2024
Medium

STL-based BFS for competitive coding

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Hello Ninja, Welcome back. We are aware of the fact importance of competitive coding in today's world. In this post, we'll learn STL-based BFS for competitive coding and Simple BFS implementation based on STL utilizing queue and vector. Vectors of vectors serve as the representative for the adjacency list. Now we focus on STL-based Breadth-First Search for competitive coding

Introduction

STL (Standard Template Library)

Competitive coding typically includes time restrictions. You must complete the issues within the allotted time to receive credit.

Standard Template Library is referred to as STL. It helps in STL-based BFS for competitive coding. Programmers use this library because it contains so many built-in methods like sort() and rotate() as well as built-in algorithms like binary search() and pre-defined data structures, including stacks, queues, linked lists, and forward lists. Now we focus on STL-based BFS for competitive coding.

C++ STL Overview

There are five different types of iterators:
 

  • Iterators for input,
     
  • Iterators for output, 
     
  • Iterators for forwarding motion, 
     
  • Iterators for bi-directional motion, and 
     
  • Iterators for random access.
     

Now we focus on STL-based BFS for competitive coding.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Competitive programming (CP) 

Competitive Programming is self-explanatory based on its name. It is just programming, as the name implies, but in a hostile environment. Programmers from varied backgrounds compete in a problem-solving competition.

People now pursue CP as a career and instruct others in it. There are several venues for CP, like Coding Ninja Competitive Programing (where the best programmers train). Many folks only received their desired job as a result of CP. Now we focus on STL based BFS for competitive coding.

BFS implementation in STL using a queue and a vector

Simple BFS implementation based on STL utilizing queue and vector. Vectors of vectors serve as the representative for the adjacency list.

We begin with a node in BFS.
 

  • Enqueue a source into a queue that you have created.
     
  • Acknowledge the source as visited.
     
  • Dequeue a vertex from the queue when the queue is not empty. This should be x.
     
  • Print x
     
  • All nearby areas that haven't been visited should be queued and marked as visited.
     

Here is an illustration of BFS beginning at source vertex 1. Note that a graph may have many BFSs (even from a particular vertex).

STL using a queue and a vector

BFS uses STL to code competitively.

Refer to this page for further information about BFS.

Now we implement STL-based BFS for competitive coding.

Implementation

Here, the code has been made simple enough to be applied to programming competitions.

// Now we focus on STL based BFS for competitive coding.
#include <bits/stdc++.h>
using namespace std;
void addEdge(vector<int> adj[], int u, int v)  {
      adj[u].push_back(v);
     
}
  void BFS(int V, int s, vector<int> adj[]) {
    bool *visited = new bool[V];
    memset(visited, false, sizeof(visited));
    queue<int> q;
    q.push(s);
    vector<int>::iterator i;

    while (!q.empty()) {
        int s = q.front();
        q.pop();
        visited[s] = true;
        cout << s << " ";
          for (i = adj[s].begin(); i != adj[s].end(); i++) if (!visited[*i]) q.push(*i);
    }
}

int main() {
      int V = 6;
      vector<int> adj[V];
      addEdge(adj, 0, 1);
      addEdge(adj, 0, 2);
      addEdge(adj, 1, 3);
      addEdge(adj, 3, 4);
    addEdge(adj, 4, 5);
      BFS(V, 0, adj);
    return 0;
}

Complexity

Time complexity

O(V+E): The complexity of DFS Algorithm is O(V+E), where V is the number of vertexes and E is the number of edges.

Reason: As we are traversing all the nodes of the Graph for finding the Breadth-First Search of a graph once.

Space Complexity

O(V): The Space complexity is O(V), where V is the number of vertexes.

Reason: Extra space for storing nodes in a queue as well as the visited array of O(V) size is being used.

Check out this problem - Queue Implementation

Frequently Asked Questions

Why do we use BFS to find the shortest path? 

If we wish to locate the shortest path in an undirected, unweighted graph, we claim that BFS is the algorithm to employ. According to BFS, the shortest path would be shown the first time a node is found during the traversal because of its proximity to the source. A weighted graph cannot be compared in the same way.

What is the Graph's shortest path? 

Finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its edges is reduced is known as the "shortest path problem" in graph theory.

Can STL be used for programming competitions? 

Yes, STL is permitted in programming competitions and is also recommended. Speed is crucial in competitive programming, and STL allows programmers the chance to create quickly and concentrate more on the logic than the actual code.

Why do we use STL?

The STL is a good example of generic programming as opposed to object-oriented programming and gets its strength and flexibility from using templates rather than polymorphism and inheritance. Additionally, it does away with new and deletes when managing memory in favor of allocators for deallocating and allocating storage. 

Does Depth-First Search identify the shortest route? 

A data structure known as a graph may be defined as one that has information that is stored among several groups of connected edges (paths) and vertices (nodes). A collection of Nodes and Edges make up the graph data structure (N, E). Vertices and nodes must both be finite.

Conclusion

In this article, we learned STL-based Breadth-First Search for competitive coding and Simple BFS implementation based on STL utilizing queue and vector. IF If you want to practice the same kind of questions, click here.

The Coding Ninjas Software development career is for you if you're looking for a more in-depth study that goes beyond Data Structure and covers the most in-demand programming languages and skills today. 

Do you have any queries about the Depth-First Search algorithm covered in this tutorial? If so, do post them in part below this page that is designated for comments.

You can also consider our competitive programming course to give your career an edge over others!

Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Ninja, have a great time learning.

Previous article
Jumping Numbers Smaller Than or Equal to a Given Value
Next article
Shortest distance between two nodes in a Graph by reducing the weight of an edge by half
Live masterclass