Lesson 5 - Graph Algorithms (BFS, DFS & Shortest Paths)

Data Structures and Algorithms in Python Lesson 5 - Graph Algorithms
#1

Please visit the Lesson Page for more detailed info :point_up:

:play_or_pause_button: Live Session Links:
English: https://youtu.be/SmOrBW22R2k
Hindi: https://youtu.be/avSKR73MqBE

Lecture Date and Time:
English: Add to Calendar (Google)
Hindi: Add to Calendar (Google)

:zap: In this lesson, we look at the graph data structure and implement common graph algorithms like breadth-fist search, depth-first search, and shortest paths.

Notebooks used in this lesson:

:question: Asking/Answering Questions :
Reply to this thread to ask questions during and after the lecture. Before asking, scroll through the thread and check if your question (or a similar one) is already present. If yes, just like it. During the lecture, we’ll answer 8-10 questions with the most likes. The rest will be answered on the forum. If you see a question you know the answer to, please post your answer as a reply to that question. Let’s help each other learn!

#2
#3

Hi, the notebook is not updated with the lecture material. Seems Aakash forgot to commit the notebook. Can we have the codes recreated in the notebook, please?

3 Likes
#4

Hello, The notebook linked from the lesson page contains all the code, please go through it.

1 Like
#5

Has anybody done the DFS Exercises? I’m trying to get the parent of DFS nodes! not sure if it’s correct! I write code parent=current aftet popping it!

current=stack.pop()
parent=current

so it gives me this! is it right!??
should i write…
parent.append(current) after popping!!(then it gives long list!)

parent in dfs wrong or right!!
parent in dfs wrong or right!!864×407 18.1 KB

1 Like
#6

image

I have done it like this and it gives correct result…
image

Hope it helps…

1 Like
#7

Has anyone implemented this…
image

If so please help me i don’t have a clue for this…

My only breakthrough is that if len(edges) > num_nodes then graph must contain a cycle

1 Like
#8

I am also stuck at he time complexities of DFS and BFS and Dijkstra’s algorithm
Pls can someone explain them ???

1 Like
#9

Thanks for the reply. Yes I figured it out too and sure it helps.

1 Like
#10

I practiced it from This: https://www.geeksforgeeks.org/detect-cycle-undirected-graph/
and from some you tube channel(better to search). it took good amount of time to get the hang of it. but the explanation is good. there’s another way of graph coloring!! i have to check it too.
Oh and yes try to break it the whole code first to understand properly then practice together!

1 Like
#11

Check this out: https://youtu.be/XB4MIexjvY0 for Djikstra’s algiorithm.

time_complexity_Djikstra_alg
time_complexity_Djikstra_alg1148×326 24 KB

1 Like
#12

Thank You very much…I would be checking and learning all of these in a couple of days…
I might become a champion in Graphs becuase of You…Thank You once again Mariha…

1 Like