Great Explanation. Sorry I don't have time to write a better review, my exams are tomorrow 😅, but seriously, this guy is an amazing teacher. Keep it up Anuj!
C++ code for the same approach int spanningTree(int V, vector adj[]) { // we are creating the minheap such that the first element is the code and the second element is the edge vector vis(V,0); int ans = 0; priority_queue pq; pq.push({0,0}); // push the initial node and weight while(!pq.empty()){ pair temp = pq.top(); // get the next edge with min cost int w = temp.first; int u = temp.second; pq.pop(); if(!vis[u]){ ans += w; vis[u] = 1; for(auto it:adj[u]){ int v = it[0]; int cost = it[1]; if(!vis[v]){ pq.push({cost,v}); } } } } return ans; } };
For me the quality of videos is decreasing as I am reaching the end. The code writing and explaining becoming faster. The starting videos of this playlist are sooo good. Now coding part becoming clumsy and errors in some codes also
Bhaiya gfg version of this question is updated. Now they are taking adjacency matrix as input and they want O(E log V) time complexity. Also, their adjacency matrix is completely different to what you taught. Please do this question again bhaiya, it'll help us a lot! If anyone is able to solve 'Minimum spanning tree' in gfg (current version) using Prim's algorithm, Please help me!
Java complete solution import java.util.*; public class primsAlgo { // gives minimum spanning tree of a graph // min spanning tree is connecting all vertices with min edge weight // follows greedy algo static class Pair implements Comparable { int v, wt; public Pair(int v, int wt) { this.v = v; this.wt = wt; } public int compareTo(Pair that) { return this.wt-that.wt; } } // undirected graph so assigning source, destination and weight static void addAdjEdge(ArrayList a, int s, int d, int wt) { ArrayList neigh = a.get(s); ArrayList list = new ArrayList(); list.add(0,d); list.add(1,wt); neigh.add(list); addAdjEdgeR(a, d, s, wt); } static void addAdjEdgeR(ArrayList a, int s, int d, int wt) { ArrayList neigh = a.get(s); ArrayList list = new ArrayList(); list.add(0,d); list.add(1,wt); neigh.add(list); } static int primsAlg(ArrayList adj, int v, int src) { PriorityQueue pq = new PriorityQueue(); boolean visited[] = new boolean[v]; pq.add(new Pair(src,0)); int ans = 0; while(!pq.isEmpty()) { Pair cur = pq.remove(); int u = cur.v; if(visited[u]) continue; ans+= cur.wt; visited[u] = true; ArrayList neigh = adj.get(u); for(ArrayList list: neigh) { int vertex = list.get(0); int wt = list.get(1); if(!visited[vertex]) { pq.add(new Pair(vertex, wt)); } } } return ans; } public static void main(String[] args) { int v = 5, src = 1; ArrayList adj= new ArrayList(); for (int i = 0; i < v; i++) { adj.add(new ArrayList()); }
C++ class Solution { public: //Function to find sum of weights of edges of the Minimum Spanning Tree. struct CustomComparator { bool operator()(const pair& p1, const pair& p2) const { return p1.second > p2.second; // Change > to < for ascending order } };
int spanningTree(int V, vector adj[]) { priority_queue pq; vector visited(V, false); pq.push({0, 0}); // Start with vertex 0 and weight 0 int ans = 0; while (!pq.empty()) { pair curr = pq.top(); pq.pop(); int vertex = curr.first; int wt = curr.second; if (visited[vertex]) continue;
visited[vertex] = true; ans += wt; for (auto& edge : adj[vertex]) { int nextVertex = edge[0]; int weight = edge[1]; if (!visited[nextVertex]) { pq.push({nextVertex, weight}); // Pushing vertex and its weight } } } return ans;
you are the only person i find on youtube who explains concepts very clearly
i usually code in C++, but if i have any doubt i see your videos because of your great explaination of dry run
please provide this code in c++
Great Explanation. Sorry I don't have time to write a better review, my exams are tomorrow 😅, but seriously, this guy is an amazing teacher. Keep it up Anuj!
Well explained...also plz try to provide the code in the description...would be more helpful
Bhaiii aag lgaa diii i will also crack Amazon interview one day ❤️❤️🎉
and that day is day 1😃
Think again.
Have you cracked any company yet?
OP tha bhai kya samjhaye🤩
Bhai jaldi jaldi video upload Kiya Karo or iske badd compitative coding ka course nikalo please
Really Helpful🙏
Very helpful and simple to understand
Bhaiya bahut best video hai made more videos
great explanation👍✌️✌️
It would be really helpful if you could share the code for using Priority queue and hashmap together😊
Extremally Helpful !
All other youtubers rush up in the explanation process, but anuj bhayia make it easy
acha moazam bhai
Anuj Bhai mujhe sirf adha samajh mein aaya
Super bhaiyya
Thank you bhaiya 🔥🔥💯💯
really helpful
Well explained!
Thanks bhaiya
Nice Bhaiya
yes it was helpfulll
mst explanation
How many more upcoming videos are in this series?
Can any one please share the practice link for this problem(which has 3-D ArrayList as adjacency matrix as parameter)
Absolutely
C++ code for the same approach
int spanningTree(int V, vector adj[])
{
// we are creating the minheap such that the first element is the code and the second element is the edge
vector vis(V,0);
int ans = 0;
priority_queue pq;
pq.push({0,0}); // push the initial node and weight
while(!pq.empty()){
pair temp = pq.top(); // get the next edge with min cost
int w = temp.first;
int u = temp.second;
pq.pop();
if(!vis[u]){
ans += w;
vis[u] = 1;
for(auto it:adj[u]){
int v = it[0];
int cost = it[1];
if(!vis[v]){
pq.push({cost,v});
}
}
}
}
return ans;
}
};
Wil you do any spring boot series in future please
Hi Gaurav, I'll be doing a Web Development Series next. Will try to make Spring boot series in the future though. Stay tuned
@@AnujBhaiya thanks bhaiya
@@AnujBhaiya Hello Bhaiya really curious Web dev kabse start krne ka soche hai
@@AnujBhaiya bhaiya, please provide this code in c++ as well
what is the font style of the code ??
Helpful
For me the quality of videos is decreasing as I am reaching the end. The code writing and explaining becoming faster. The starting videos of this playlist are sooo good. Now coding part becoming clumsy and errors in some codes also
true
iska source code kaha milega
What is that.wt concept
Sir, pls give code links as well
Sir me b.a. ka student hu to kya me coding field me career bna skta hu skills ke bass par
Bhaiya gfg version of this question is updated. Now they are taking adjacency matrix as input and they want O(E log V) time complexity. Also, their adjacency matrix is completely different to what you taught. Please do this question again bhaiya, it'll help us a lot!
If anyone is able to solve 'Minimum spanning tree' in gfg (current version) using Prim's algorithm, Please help me!
can you add with python?
Noo
bhaiya, please provide this code in c++ as well
But it is helpful
Directed graph mein karte
bhaiya i haven't learned maths in 11 th and 12th can I still become a coder
yes
no
sir i would really helpful if u provide code
noice
everything was going great until you started coding in JAVA .....was expecting C++ solution
stop talking so fast
Playback speed low kar lo
M to jb bhi 1.5× m dhekra 😂
Better u stop watching
@@ArtisticGodbetter u stop commenting
@@rifahtasnimtandra6771 better u stop reacting..
yar thoda or improve kro smjhane mae, if you know it does not mean everyone knows
Java complete solution
import java.util.*;
public class primsAlgo
{
// gives minimum spanning tree of a graph
// min spanning tree is connecting all vertices with min edge weight
// follows greedy algo
static class Pair implements Comparable
{
int v, wt;
public Pair(int v, int wt)
{
this.v = v;
this.wt = wt;
}
public int compareTo(Pair that)
{
return this.wt-that.wt;
}
}
// undirected graph so assigning source, destination and weight
static void addAdjEdge(ArrayList a, int s, int d, int wt)
{
ArrayList neigh = a.get(s);
ArrayList list = new ArrayList();
list.add(0,d);
list.add(1,wt);
neigh.add(list);
addAdjEdgeR(a, d, s, wt);
}
static void addAdjEdgeR(ArrayList a, int s, int d, int wt)
{
ArrayList neigh = a.get(s);
ArrayList list = new ArrayList();
list.add(0,d);
list.add(1,wt);
neigh.add(list);
}
static int primsAlg(ArrayList adj, int v, int src)
{
PriorityQueue pq = new PriorityQueue();
boolean visited[] = new boolean[v];
pq.add(new Pair(src,0));
int ans = 0;
while(!pq.isEmpty())
{
Pair cur = pq.remove();
int u = cur.v;
if(visited[u])
continue;
ans+= cur.wt;
visited[u] = true;
ArrayList neigh = adj.get(u);
for(ArrayList list: neigh)
{
int vertex = list.get(0);
int wt = list.get(1);
if(!visited[vertex])
{
pq.add(new Pair(vertex, wt));
}
}
}
return ans;
}
public static void main(String[] args)
{
int v = 5, src = 1;
ArrayList adj= new ArrayList();
for (int i = 0; i < v; i++)
{
adj.add(new ArrayList());
}
addAdjEdge(adj,0,1,2);
addAdjEdge(adj,0,3,7);
addAdjEdge(adj,0,4,6);
addAdjEdge(adj,1,2,1);
addAdjEdge(adj,1,4,4);
addAdjEdge(adj,2,3,3);
addAdjEdge(adj,2,4,2);
addAdjEdge(adj,3,4,5);
System.out.println(primsAlg(adj, v, src));
}
}
C++
class Solution
{
public:
//Function to find sum of weights of edges of the Minimum Spanning Tree.
struct CustomComparator {
bool operator()(const pair& p1, const pair& p2) const {
return p1.second > p2.second; // Change > to < for ascending order
}
};
int spanningTree(int V, vector adj[]) {
priority_queue pq;
vector visited(V, false);
pq.push({0, 0}); // Start with vertex 0 and weight 0
int ans = 0;
while (!pq.empty()) {
pair curr = pq.top();
pq.pop();
int vertex = curr.first;
int wt = curr.second;
if (visited[vertex]) continue;
visited[vertex] = true;
ans += wt;
for (auto& edge : adj[vertex]) {
int nextVertex = edge[0];
int weight = edge[1];
if (!visited[nextVertex]) {
pq.push({nextVertex, weight}); // Pushing vertex and its weight
}
}
}
return ans;
}
};