No video :(

Kahn's algorithm | Topological sort | Course schedule 2 | Leetcode

Подписаться 172 тыс.

Просмотров 31 тыс.

50% 1

This video explains an important programming interview problem which is to find the topological sort of a given graph.In this video,i have explained how to find topological sort using Kahn's algorithm.This algorithm is based on BFS (Breadth first search) and makes use of QUEUE and an Indegree ARRAY.Topological sort can also be found recursively using DFS (Depth first search) and a STACK which i have explained in my previous video.I have shown all the steps of this algorithm clearly using proper examples and have also shown the solution for a practice problem from leetcode number 210 which is course schedule 2.I have dry run the algorithm and have also explained the code walk through at the end of the video.CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
========================================================================
INSTAGRAM : / surya.pratap.k
SUPPORT OUR WORK: / techdose
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
TELEGRAM Channel LINK: t.me/codewithT...
TELEGRAM Group LINK: t.me/joinchat/...
=======================================================================
CODE LINK: gist.github.co...
USEFUL VIDEOS:-
BFS: • Breadth first search |...
Topological sort | Course schedule 2: • Topological sort | Cou...

Опубликовано:

8 июл 2020

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 89

@sainathreddy2632 3 года назад

Indirectly it can be used to find cycle in directed graph using the count variable

@techdose4u 3 года назад

Yes

@bestsaurabh 3 года назад

Instead of count variable, we can use "ans.size() != no of vertices"

@ashishg656 4 года назад

Perfectly explained. Thanks a lot :)

@techdose4u 4 года назад

Welcome :)

@willturner3440 3 года назад

I code it without seeing solution bcoz of your great explanation 🥰

@Amansinghal321 4 года назад

Great explanation sir, please keep making videos on the graph. This is the best resource I have seen so far.

@sulekhakumari-hs4gy 4 года назад

this dose is really making my coding healthy.

@umapathybabu8397 4 года назад

Excellent lectures, continue doing this helps a lot

@ApoorvaRajBhadani 4 года назад

Subscribed after watching your first video(this one). You are amazing.

@techdose4u 4 года назад

Thanks :)

@adwaitkulkarni 3 года назад

great explanation!

@techdose4u 3 года назад

Thanks :)

@mohitshoww 4 года назад

@TechDose Jaisa Koi Explain nhi kar sakta bhai ... Thanks Sir For your Awesome Explanation 😍😍😍

@minguero 2 года назад

what a great explanation

@techdose4u 2 года назад

Thanks 😊

@gauthamalva8701 3 года назад

Made my day. Thankyou brother :)

@techdose4u 3 года назад

Welcome

@fadiahetrakeshkumar9454 3 года назад

Wonderful expalination bro

@spetsnaz_2 4 года назад

😍Very well explained🍁

@techdose4u 4 года назад

Thanks

@RishabhVerma 3 года назад

Awesome Explanation !! Thanks for your efforts :)

@techdose4u 3 года назад

Welcome bro

@PUNEETRAIPURIA 4 года назад

awesome explanation 🤩

@techdose4u 4 года назад

Thanks :)

@Official-tk3nc 4 года назад

COMMENT YOUR COLLEGE NAME HERE:

@Official-tk3nc 4 года назад

nit JALANDHAR

@spetsnaz_2 4 года назад

@@Official-tk3nc Jadavpur University

@WowPlusWow 3 года назад

ABC Mouse

@HimanshuSingh-ob9qo 4 года назад

Always best explaination

@akashjain2541 4 года назад

hey bro. thank you so much for owsm explanation.

@gontlakowshik2345 4 года назад

Nice explanation sir it is very much help full 🤝

@bilbo_baggins_ 4 года назад

good explanation....thank u sir

@techdose4u 4 года назад

Thanks :)

@nayanjain5761 3 года назад

Sir, you are awesome, please keep on making such amazing videos.

@jiosim1377 2 года назад

Great explaination but i didnt get the intuition behind the algorithm. Can someone explain?

@satrap299792458 4 года назад

Can you please explain Djikstra's algorithm with code link?

@sainikhil956 3 года назад

Sir,what if there is multiple components and why we did not use visited array? is it because while we are traversing in indegree itself we will get all possible components ryt?

@mks7846 4 года назад

Please do a video on inverse and determinant of a matrix

@techdose4u 4 года назад

👍

@priyanshijajoo6006 3 года назад

Perfect! Thanks.

@techdose4u 3 года назад

Welcome

@siddharthsen4475 4 года назад

Great explanation 👌

@fadiahetrakeshkumar9454 3 года назад

Subscribed!!!

@Mandeepsingh-jo5cf 3 года назад

Thank you sir.

@techdose4u 3 года назад

Welcome :)

@aviligondagowtham1153 4 года назад

Sir do more nd more dynamic programming questions

@naman_goyal 4 года назад

Nice explanation

@Amitkumar-sh1xl 4 года назад

Nice explanation Sir 🔥

@tanujkalra7334 3 года назад

Excellent Explanation ! Thanks :)

@techdose4u 3 года назад

Welcome :)

@rajatnagpure7445 4 года назад

The code for Kahn's aglorothm isnt there at link u gave.

@rajatnagpure7445 4 года назад

and my code doesnt seem to work! can u plz help me why? class Solution { public: vector findOrder(int numCourses, vector& prerequisites) { vector adj(numCourses); vector ind(numCourses,0); for(int i=0;i

@techdose4u 4 года назад

It is for course schedule 2 using Kahn's Algorithm. Please check it. If there is any issue then let me know.

@sarwadnyanivruttimutkule4898 3 года назад

Will the code work if our graph has disconnected components?? because even then the count variable won't be equal to the number of nodes when it comes out of the BFS run.

@ChandraSekhar-tr7sf 2 года назад

even though graph is disconnected it has at least one node which has indegree zero and outdegree zero

@dharanit3918 3 года назад

Awesome explanation bro 💯💯❤ Which is preferred dfs+stack or khan's algo bfs+ queue ?? Thanks in advance :)

@techdose4u 3 года назад

Anything is fine. I prefer BFS.

@dharanit3918 3 года назад

@@techdose4u Thanks bro ❤

@WilliamDunn1 3 года назад

If you are also confident in your cycle detection algorithm (such as the simple "graph coloring" method) the DFS version is probably easiest to implement during job interviews- it's identical to the standard post-order DFS, you first need to check there are no cycles, but then you can implement the simple recursive version of DFS and append to the stack as the post-order step then reverse the stack when done. It's almost impossible to make a mistake with such a simple and common algorithm that you use for many problems. Though as with all recursive algorithms you will need to first confirm with the interviewer that the longest path is shorter than your language's max recursive call stack

@dharanit3918 3 года назад

@@WilliamDunn1 thanks

@NaveenKumar3992 2 года назад

Iterative code (BFS + queue ) is always preferred over recursive one ( DFS + stack ) because iterative solutions are faster than recursive since it doesn't have to deal with recursive call stack frame . Also iterative solutions avoid the problem of stack overflow associated with recursive solutions

@modetechno7728 10 месяцев назад

what is indegree and outdegree?

@fadiahetrakeshkumar9454 3 года назад

can i simply say that count=answer.size(); where answer is the vector(n+1,0);

@ayushmehra5059 4 года назад

Awesome

@vikaschauhan2630 4 года назад

Thanks ..🙂

@akashtyagi7182 4 года назад

I have a virtual interview coming up in few days. Can you please share your drawing instrument and technique ? As currently i don't have any such gadget and I am worried how to explain to interviewer

@rashmikiranpandit8962 4 года назад

Even me too...

@techdose4u 4 года назад

You can take any pen tablet according to your budget and you can get free drawing softwares on internet.

@anantpawar782 2 года назад

On which software do you work?

@adityamaurya8092 4 года назад

Make a vedio on find the target sum in array without using recursion

@techdose4u 4 года назад

Is it target subset sum problem?

@adityamaurya8092 4 года назад

@@techdose4u yes ,but without using recursion because using dynamic problem and recursion it's solution is already ,I don't find solution without using recursion on internet