G-21. Topological Sort Algorithm | DFS
Вставка
- Опубліковано 6 лип 2024
- GfG-Problem Link: bit.ly/3PvBfsm
C++/Java/Codes and Notes Link: takeuforward.org/data-structu...
DP Series: • Striver's Dynamic Prog...
SDE Sheet: takeuforward.org/interviews/s...
Check out our Website for curated resources:
Our Second Channel: / @striver_79
In case you are thinking to buy courses, please check below:
Code "takeuforward" for 15% off at GFG: practice.geeksforgeeks.org/co...
Code "takeuforward" for 20% off on sys-design: get.interviewready.io?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/invite/xexnpc4u
Take 750 rs free Amazon Stock from me: indmoney.onelink.me/RmHC/idje...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v3cO/8hu879t0
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
---------------------------------------------------------------------------------------------------------------------------
Let's continue the habit of commenting “understood” if you got the entire video. Please give it a like too, you don't 😞
Do follow me on Instagram: striver_79
Understood
@pulkitjain5159
0 seconds ago
LET ME GIVE WHAT I UNDERSTOOD AS AN INTUTION
Agar isko Task Completion ke perspective se dekhe such that if A -> B is like ki A wala task complete karne ke liye B wala task complete hona jaroori hai.
toh hum dfs ke through bas yeh keh rahe hai ki
dfs(task , completedTasks){
visited[task] = true; // mene yeh task karna start kardiya hai
// par mujhe pata laga yeh task toh bakiyo pe dependent hai , toh phele mein unko khatam karke ata hu
// let task on which my current task is dependend on be "dep".
for( int dep : adj[ task ] ){
if(!visited[dep]){
// agae yeh dep abhi tak khatam nahi hua hai
dfs(dep , completedTasks); // phele m isko complete kar leta hu
}
}
// ab jab saare tasks jinpe mein depend karta hu khatam hogaye toh
completedTask.push(task);
}
Why can't we add codes in comments?
Many coder who know all this things but cannot explain well, but u r the different beast who can do both single handedly !!!!
The problem with this solution is that if you are given a directed graph that contains a cycle in the solution. The algorithm wont be able to detect, it will spill out an ordering which is wrong. But when using khans algorithm, you will be able to detect whether top. sort was possible or not.
+1
glad i looked up this cooment, was doing course schedule using dfs topo and getting wrong answer
Yeah but he already mentioned it is for Directed Acyclic Graph so it won't work in Graphs containing cycles.
But you can check the size of your topological sort array and if it is equal to number if vertices it is a valid one otherwise not.
C ho tum
Revising through this playlist before an interview is a bliss.
INTUITION : incase you faced some trouble , taking in consideration the graph 1->2->3->4
we start with the dfs(1) we keep calling it for the adjacent nodes and at the very end we reach dfs(4) WHICH DOES NOT HAS ANY ADJ NODE, thus we put it in the stack stating that there is no node it needs to point after completion we push 3 in the stack stating that all the nodes pointed by 3 must already be the stack, same way we go up and at the end we push 1 in the stack stating that all the nodes pointed by 1 are already in the stack in a linear order.
Linear order if a node v points to u then v comes first then u.
And if it is reverse of topological ordering? Use Queue :P
@@sayandey2492 by playing with where you place stack during recursion you can use stack only.
@pulkitjain5159
0 seconds ago
LET ME GIVE WHAT I UNDERSTOOD AS AN INTUTION
Agar isko Task Completion ke perspective se dekhe such that if A -> B is like ki A wala task complete karne ke liye B wala task complete hona jaroori hai.
toh hum dfs ke through bas yeh keh rahe hai ki
dfs(task , completedTasks){
visited[task] = true; // mene yeh task karna start kardiya hai
// par mujhe pata laga yeh task toh bakiyo pe dependent hai , toh phele mein unko khatam karke ata hu
// let task on which my current task is dependend on be "dep".
for( int dep : adj[ task ] ){
if(!visited[dep]){
// agae yeh dep abhi tak khatam nahi hua hai
dfs(dep , completedTasks); // phele m isko complete kar leta hu
}
}
// ab jab saare tasks jinpe mein depend karta hu khatam hogaye toh
completedTask.push(task);
}
@@varunaggarwal7126 exactly what i was thinking , the moment you insert the ele should be made at the start and not end , regular dfs is rev topo i guess ?
great comments , it's okk for understanding, actually great but code is actually working in backtracking way, so not exactly fitting......
mtlb ki phle hum uss element ko khoj rhe hain jo sbpe dependent hain (dfs(1) agar dfs(2) ko call kr rha hain mtlb 1->2 ja skte hain mtlb ki 2 ko krne ke liye 1 ka hona jruri hain, lekin yha hum sbse phle 2 ko stack mein dalenge then 1 ko so that 2 sbse niche chala jaye,) isse jo kaam sbse phle krna hain, jo kisi pe dependent nhi hain wo top pe aajayega@@pulkitjain5159 this is from my understanding, please correct if i am wrong.🙏
Great Work Striver. Thanks for always helping us !!
Understood! Super amazing explanation as always, thank you very much!!
Can't express it in words, your content is out of the world, really amazing bro❤❤
we can use bool array instead of int array to mark visited....it will take less memory.
understood, was able to code up using the logic after your explanation, thanks!
Hey Striver, Thank you for the amazing content. But I request if you could add some problems on Union Find as well. Thanks in advance!!!
Thank you striver for providing such nice content
Quick Tip : If you are thinking, why don't we put into list when you start dfs, this way we don't have to use stack or reverse order. Consider a case 6->0->1->2->3->4->5, we start from 0 and put into list, so ordering comes out to be, 0,1,2,3,4,5 and then we check for 6, so 6 at last, but this is wrong. Hence we cannot put into list when starting the dfs, because we dont' know if 0 was coming from somewhere else. Hence we put into list at last and then reverse(or use stack and pop). So ordering becomes 5->4->3->2->1->0 and then we check for 6, so 5->4->3->2->1->0->6 and reversing this is correct topo.
Thanks bro !!
Why 6 cannot be in last?
@@crosswalker45 Because 6 is at starting of topo sort and not last. It is even before 0, since we started from 0 doesn't mean our topo start from 0.
Thanks
whenever your heart is broken , don't ever forget you are golden..
explained in quite easy manner ..thanks habibi
Thank you, STRIVER 🙂
understood,great explanation
got it!! thanks for this series
Understood. Fantastic explanation❤
loved the intuition and explanation striverr bhaii
Thank you very much. You are a genius.
Thank You So Much for this wonderful video.................🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Amazingly explained :)
Understood! Thank you sir
Awesome work
Thank You sooo much SIR
🙏
Understood, Thank you so much
understood bhaiya..
LET ME GIVE WHAT I UNDERSTOOD AS AN INTUTION
Agar isko Task Completion ke perspective se dekhe such that if A -> B is like ki A wala task complete karne ke liye B wala task complete hona jaroori hai.
toh hum dfs ke through bas yeh keh rahe hai ki
dfs(task , completedTasks){
visited[task] = true; // mene yeh task karna start kardiya hai
// par mujhe pata laga yeh task toh bakiyo pe dependent hai , toh phele mein unko khatam karke ata hu
// let task on which my current task is dependend on be "dep".
for( int dep : adj[ task ] ){
if(!visited[dep]){
// agae yeh dep abhi tak khatam nahi hua hai
dfs(dep , completedTasks); // phele m isko complete kar leta hu
}
}
// ab jab saare tasks jinpe mein depend karta hu khatam hogaye toh
completedTask.push(task);
}
nice explanation
ek dum sexy explanation bhai!
Very clearly explained @pulkitjain5159,
@striver this is what you call intuition
Thank you sir 😊
Its awesome bro
Thank you sir iski bahut need thi. Haal hi mai ek question aaya tha aur woh mai nhi kar paya tha
THANK YOUUU STRIVERRR!!
UNDERSTOOOOOD😊
Understood !
GOD level explanation
understood ❤️
Understood 😊
Thank you bhaiya
Understood bhaiya
understood the assignment :)
UNDERSTOOD!!!!!!!
understoooddddd
Why aren't we using the path[] here? Is it because its acyclic graph?
understood!!! JOD
understood!
Understood❤
understoood
UNDERSTOOD.
everything is nyc except one thing sir if suppose i/p is loop(1,2,3) then s.size==n fails only bfs accepts am i correct i chckd for conditions
Understood.
Understood !!
can we pushback the node in ans in the postorder of the dfs function i.e., after the for-loop?
then you have to reverse the stack.
ua-cam.com/video/6Vi5Td_a8B8/v-deo.html&ab_channel=Pepcoding watch this for your doubt clarification
Awesome! Us
Understood:)
Understood
Awesome
awesome
maza aa gya
What I understood from this problem is that "GIve a BFS path using DFS". Is it?
hey striver I want to code like you!!
understood
Cool understood
understood.
can we use queue in this question at last we will reverse the queue
UNDERSTOOD
understood!!!!!!!!!!!!!!!!!!!!
Can someone help me understand how he determines if we are given an adj matrix or an adj list?
If given
vectoradj; that mean we have an adj matrix
If given
vectoradj[ ] this mean we have an adj list
@boomsi69 tompr ko mera pranam 🙏🙏
yes
Even without taking a stack we can do, it is by taking a vector and storing all the node values after completion of that node's dfs, and finally reverse that vector...
Why to go all the way to reverse a vector rather than storing it in the reverse order during the dfs. Just create a vector with size of total number of nodes and using a index variable move from the back of vector to the front during dfs. Here's how its done:
class Solution
{
private:
void dfs(int start,int vis[],vector adj[],vector& ans,int& index){
vis[start]=1;
for(auto it: adj[start]){
if(!vis[it]){
dfs(it,vis,adj,ans,index);
}
}
ans[index--]=start; // Its decrement
}
public:
//Function to return list containing vertices in Topological order.
vector topoSort(int V, vector adj[])
{
// code here
int vis[V]={0};
vector ans(V);
int index=V-1;
for(int i=0;i
is it ok to use queue rather than using a stack ?
Yes but at last when you pop out nodes, you will have to reverse the resultant list.
@@Shivanai_h thank you 😊
@Ayush Negi simply use vector, and reverse it. No need to store again to vector from deque while returning.
Hey Striver ( @takUforward ) is topological sort used by dependency management tools like Maven or Gradle to manage project dependencies??
Yes
understand bhaiya❤🙏🏻\
Understood..
@take U forward before applying this method we should ensure that no cycle is present ??
Input is always DAG, so it's not checked. But if input can be cyclic graph, you need to add cycle checks
@@VIRAJBHOSLE Yeah, thanks!!!
understood but striver I forgot those code and have to remember everytime . How should I keep remember the code?
Don't memorise the code. Instead, try to understand the logic and then write code. Converting logic into code requires practice.
Memorize the logic. If DFS, and topological sort, use a stack. BFS, use Queue. Both use visited array
I believe we need to assume that the given directed graph does not contain any cycle, only then this algorithm using DFS will work.
grt vdo
understood :D
#Striver rocks 🤟👍
link is not found for -C++/Java/Codes and Notes Link
Please check.
what if i run this algo on a directed graph with cycle
Topological Sorting - DFS algorithm will print wrong linear ordering if input is a directed cyclic graph.
Why can we not use simple array instead of stack. I am not able to understand of specific stack in this case. Can any body clear this?
Yes we can push into vector.....
Than at the end we can reverse it
how do we know that stack will be used
Because we need to get in reverse order
@@narendrarokkam5367 we can store it in a vector then simply reverse it, space saved right?
@@soumyamondal but time inc
4:05 - 7:50
Understood but what the intuition ?
only had to watch half of the video and did the coding part all by myself
🐐
5:30
how cycle is handled in this code?
topo sort is only done for DAGs
4:08
6:20
"UNDERSTOOD"
We should apply the DFS way of Topological Sorting only if the ordering of the resulting sort is checked otherwise should always prefer BFS way of Topological Sorting. WHY?
Because if the cycle exists DFS would return all the vertices with wrong ordering but in case of BFS, it wouldn't return all the vertices if cycle exists. So even if we don't go for ordering detection, number of vertices itself would clear whether sorting is possible or not.
This is the reason why BFS (Kahn's Algorithm) is preferred.
"understood"
457310 aa sakta hai final output?
Understood Striver bhai. Aapne samjhaya hai toh samjh to aayega.
Also bhai aapki tabayt kharab lag rahi thi . Pls take care bhai.
Understood Striver
UnderStood
US, 900th like
is Indegree logic wrong in dfs? umm why?>
vectorans;
void dfs(int src, vectorgraph[] , vector&inDeg , vector&vis){
vis[src]=1;
ans.push_back(src);
for(auto nbr: graph[src]){
inDeg[nbr]--;
if(inDeg[nbr] == 0 && vis[nbr]==0){
dfs(nbr,graph,inDeg,vis);
}
}
}
vector topoSort(int n, vector graph[])
{
vectorinDeg(n,0);
for(int i=0;i