Topological Sort Algorithm with DFS | Course Schedule in JAVA | Code and Implementation
Вставка
- Опубліковано 25 сер 2024
- Please consume this content on nados.pepcoding.com for a richer experience. It is necessary to solve the questions while watching videos, nados.pepcoding.com enables that.
NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. This video explains the Topological Sort algorithm for acyclic directed graphs with weights. Topological Sort algorithm is a permutation of vertices for a directed acyclic graph if for all directed edges uv, u appears before v in the graph. We then code and implement the job sequencing problem where:
1. You are given a directed acyclic graph. The vertices represent tasks and edges represent dependencies between tasks.
2. You are required to find and print the order in which tasks could be done. The task that should be done at last should be printed first and the task which should be done first should be printed last. This is called topological sort.
Check out the video for details.
For a better experience and more exercises, VISIT: www.pepcoding....
#graphs #topologicalsort #algorithms
Have a look at our result: www.pepcoding....
Follow us on our FB page: / pepcoding
Follow us on Instagram: / pepcoding
Follow us on LinkedIn: / pepcoding-education
Join us on Telegram: t.me/joinchat/...
![АЛАУДИНОВ у Скабеевой: эти их ВСУ нас НЕ ДОГОНЯТ 😁 [Пародия]](http://i.ytimg.com/vi/an0anqU4WGQ/mqdefault.jpg)
Sir u spent 40 minutes explained so nice 4-5 times , and at last still said agar samaj nahi aaya toh dubara banaunga. you won my heart
so true.. sir aap ne bhot achha samjhaya.. thank you soooooo much sirr.....
Thank you sir for the clear explanation of Topological Sort! No additional explanation is required.
I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem.
If you like our efforts, we request a review
g.page/Pepcoding/review?rc
You can subscribe to our channel here
ua-cam.com/users/Pepcodingabout?view_as=subscriber
Bhai cyclic ke liye kaam ni kr rha ye algo?
Topological sort ki requirement h directed acyclic graph
Generally I don't comment on videos, but this is really brilliant... all the questions and doubts, which were there in my mind were covered in this video. For ex: i knew preOrder will not work, but an accurate explaination was not clear to me. This gave me the explaination. Also i have seen many pepcoding videos, these are alway best
I don't think there's a better explanation of this out there 💯
I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem.
If you like our efforts, we request a review
g.page/Pepcoding/review?rc
You can subscribe to our channel here
ua-cam.com/users/Pepcodingabout?view_as=subscriber
truuuuee........
Mujhe lagta tha topological sort bahut jyada hard hoga but aapke explain krne ke baad mai kisi ko bhi topological sort padha sakta hu 🔥🔥
Sir matlab alag hi dedication hai aapka humaare lie.. pata hi ni chalta aapke saath padke time ho gaya . Btw great explanation sir
thank you. :-)
Most underrated channel on youtube. Awesome videos.
Glad you liked it.
Keep learning and growing.
And for better experience and well organised content explore nados.pepcoding.com
amazing lecture....at 15:25 to explain why preorder will not work, not only independent component but in single component also preorder will not work e.g. the component with nodes 4, 5 and 6...if traversal was considering the node 6 first from 4 then preorder will give 4, 6, 5 as output but there is edge 5, 6 in the component. I hope it helps.
understood in first 7 minutes...mazaa aane laga hai ab
Best tutorial for graph, I've ever seen. I will surely recommend this to my friends
I dnot know how to describe my feelings . itna acha explanation maine baar sunna . Hats Off to you Sumeet sir !! 🫡
Sir this is the best explanation ever..... thanks a million times.... 🤗😊
Amazing sir.. bahut ache se samajh aaya. don't worry about it
Chalo cool hai. Mujhe lga repeat karna padega.
I had seen many tutorial on youtube but your level of explaining is top notch please made more video
nados.io pe jaie aur content dekhie. wahan humari 10K videos hain, youtube pe sirf 3K. wo bhi free he hai.
kya video thi ye waali :), iteratiev dfs bhi bahut badiya thi :)
Thank you
Respect and Love... Always ⭐
Best explanation ever! Hats off to Sumeet Malik
Glad to know that you liked the content and thank you for appreciating.
The love and respect which I get from you people keep me highly motivated and the same I am able to forward It to you people through my videos.
So, keep motivating, keep learning and keep loving Pepcoding😊
haaa sr baat smjh me aagyi kaafi efforts daale hai aapne
OP Explanation🔥🔥
boht acche se smj aaya sir
best video ...!!! here and sir what an explanation loved itt........!!!
Thanks a ton. keep motivating, keep learning and keep loving Pepcoding😊
Very much excited for level up
does sir post level up videos also on youtube?
@@kampatiraviteja7398 yes
I pray to god that I atleast do 10 questions per day.
@@Pepcoding if pray to god to give me such a dedication u had ...respect !!
Great content!
Thank you sir..
Thankyou beta!
Thanks a lot for the free content :)
Glad to know. If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )
One small request...if you could please upload one video...vertical order traversal where overlapping nodes need sorting...I know Rajneesh Sir has already uploaded it but need to understand it even better...Thank you
Amazing sir ....🙏🙏🙏🙏🙏🙏
Thankyou beta!
I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem.
If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Excellent explanation 👍
Glad, it was helpful. For complete content, check out nados.pepcoding.com
What if there is a cycle in the graph , then topological sort is not possible and Ans should rather be -1.
Thank you so much.
Always welcome. For better experience and precisely arranged content visit on nados.io, even you can post your doubts on nados.io
Imandari ki misaal ho sir aap
Superb explaination🎉🎉
Sir bhut ache se clear, thanku
Keep learning and keep loving Pepcoding
Great pleasure for us sir
Great Explaination !!!
Very well explained sir
Thanks and welcome
Sumeet Malik the OG!
excellent
Thank you! Cheers! For better experience and well organised content sign up on nados.io
sir please try to cover LinkedList , Stack&Queue first in the levelup course. These topics are small and not linked with other topics like recursion or /tree.
bet stack and queues foundation mei he kaafi sahi ki hai. levelup ka order hoga
backtracking -> bits -> dynamic programming -> trees -> hashmap and heaps -> graphs
Stack and Queues and Linked Lists last mei karenge
Sir crystal clear .
😍🥰❤️🙏🏼
Sir i just finished basic ds algo concepts....now i want to start practicing question should i directly start with your list or first practice from somewhere else?
Pls tell...
You can do this
docs.google.com/spreadsheets/u/1/d/1XdXJbn9NC7fx1CeavItkxR0Yos8rQAC9xXjnH4-f6Eg/edit#gid=0
Or I will start levelup 2mrw. 10 questions everyday. You could also do that.
Will it handle back edges of if the graph is cyclic? , I am getting some errors. There are no conditions to check if the graph is cyclic.
Thankyou for sharing!
My pleasure!
Sir, what to do if the graph has a cycle ?
Sir faang list k solutions ki Bh vedios banadijeye plss...!!! It will be soo helpful .
sir please made more videos on this graph
thank you
You're welcome
Osm sir ji
Waiting for this .
A very important question here is
1. Did you watch it complete?
2. Did you get the "Whys" that I tried to explain?
I am not satisfied with this video. Are you?
@@Pepcoding 1) i watched it 4 times sir .❤️
2) i have doubts but parallel to this i take reference from gfg Because i code in c++. And as far as the satisfaction level concerned For me it is 4/5 . I am satisfied.
I will redo it. Mza nahi aya
@Pepcoding Sir can you please put this Java code here , I have a bit confusion while writing the code 🙏
Sir plz continue with graph lectures...
hanji jaroor
@@Pepcoding kab tak aa Jayega sir?
Sir levelup ke roadmap ki ek video daal dijiye, ki hum kis order mein konse konse topics padenge
here it is
1. Backtracking
2. Bit Manipulation
3. Dynamic Programming
4. Trees
5. Hashmap and Heaps
6. Graphs
Iske baad dekhenge
Sir I think there is some mistake because you said order of compilation is reverse of topological sort but in the end you did not reverse it. Popping elements from the stack will actually give the topological sort. Thank you
that is asked in the question, it is just sir wanted us to know order of work is reverse of topo sort
Great content 👍
Glad you think so! and If you like the content could you post something on LinkedIn about us? This will help us in reaching out to more people and help a lot of other students as well
Something like this
Sumeet Malik from Pepcoding is making all his content freely available to the community
You can check it out here - www.pepcoding.com/resources
/
Also, this is the youtube channel - ua-cam.com/users/Pepcodingplaylists?view_as=subscriber
@@Pepcoding sure sir , will share it with friends
indegree lekar bi to kar sakte hai na ? sare nodes with indegree equals zero queue mein jayege.. Then bfs as usual
Sir, sari videos hai but bridges in graph ki video nahi mili
hanji, level2 mei dalunga. wo bhi aur union-find bhi
Sir, I am new here please guide me.From where I have to start?
How much time I have to give?
What should be done first?...
Please sir help me..
ua-cam.com/video/2IdlrHxdla4/v-deo.html
refer this video
@@Pepcoding That was epic!
Thank you so much sir,
One more query sir,
Sir the 300 questions that you said in the video about 'concepts' are present in your foundation course or not? Have a nice day sir..
You are awesome.
adj list use karna thi rehta h ya adj matrix?
Bhai 1st video dekhle playlist ki sab clear hojayega.
adj list use krna jayda thik rehta hai bca adj matrix m kafi space waste hota hai
bcz*
Sir the mock interview which you will conduct on 20th webinar , will be open ended like you will ask questions to students on youtube or you will conduct it with some person on zoom.
beta, ek favourite student hai jisne bhot struggles ki aur apne bal boote tier 3 college se microsoft, amazon aur traveloka crack kia. He has been a part of my teaching journey. We as a teacher-student pair failed and succeeded together. Use bhot insight hai, in saari struggles ki. Referrals wagaerah ki bhi. Uska mock interview mai lunga aur last mei usse advise lenge.
@@Pepcoding representing GTBIT tier 3 //belongs to the sardars but claimed by JEE dropouts :P
Sirji levelup ? checking channel every 5 mins :)
beta jo aj bnaunga use kal padhna. 6 bje he shuru karta hun. 12 bje tak bnaunga. 10 ban jaengi. tum mujhse ek din peeche chalo. mai aj 10 bnaunga, aap kal 10 padho.
@@Pepcoding Ok Sir thank you
sir post order me hmesha children pe pehle kaam hoga uske parent se ?
Yes. kyunki children ka post order parent se pehle aata hai
Can there be multiple toplogical sort of a graph...??
Yes
Sir,.
Like push_front in vectors.. Is there any function in arraylist?
If it is so. , then we can use arraylist instead of stack
for that in java we use queue , and if you need both the functionalities of a stack adding at last and adding in front like a queue , in java there is a different datastructure for that know as deque, and if you only want to use the array list and push in front then you can do arr.add(index , element ) this will push the element in the specific index but the time complexity will become O(n) as all the elements will be needed to shift one place
Need help in leetcode 207 question.
For solving all your doubts visit on community tab on nados.io
Can you explain some examples?
you missed the edge case when there is input forms cycle
topological sort works only for acyclic graphs (when there is a cycle, topological sort is not possible)
Sir bs ek request thi , arrays and strings ke bhi daal do
hanji. Kar rhe hain beta.
Hello sir.
Sir apne ek comment main kaha tha ki 16 August se levelup ke question Aa jayega
So jo question ayenge wo foundation main he add ho jayenge ki levelup ka ek agal se Playlist rahega.
Or ip ka bhi?
Alag playlist bnega beta aur, site pe yahan milega
www.pepcoding.com/resources/data-structures-and-algorithms-in-java-levelup
IP ka bhi alag playlist and alag course
@@Pepcoding but sir link open ho raha hai but ek bhi question nahi hai
Means topic hai but question nahi hai usame..
@@Pepcoding thank you sir.
For always replying 😇
What if the topological sort is not possible? for example: [[0->1],[1->0]]
You can check first with dfs.
Sir level up ki video kb upload kroge app?
beta subh se kuch kuch nipta rha tha. abhi shuru karunga. raat tak 10 daal ke he sounga. aap mujhse ek din peeche chalein (time waste nahi hoga). Mai roj 10 daalunga (aap next day 10 kar dein)
First viewer me.
A very important question here is
1. Did you watch it complete?
2. Did you get the "Whys" that I tried to explain?
I am not satisfied with this video. Are you?
@@Pepcoding yes I watched completely, understood Whys as well. you are trying to tell if an edge running from U to V, u must be completed before V. and using stack to
keep dependency vertices first
I guess with queues also we can do it but completely different approaches.
anyways thank you Sumeet sir for the detailed explanation.
@@CodeCraftWithVinayak should I redo this one?
Not required. Thanks for reply.
sir agar main directed cyclic graph de doon tbb bhi yeh code chal rha hai. tbb toh nhi chalna chaiye tha. aisa kyu
kyuki vo visited mark kar deta hai. isliye ruk jaata hai cyclic ghumne se
fir us component se stack me daal ke next component pe chale jaate hai
hume saara tam jhaam karne se pehle ye check karna cahiye ke cyclic hai to return -1