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: Session Recordings:
English: https://youtu.be/SmOrBW22R2k
Hindi: https://youtu.be/avSKR73MqBE

: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. Before asking, scroll through the thread and check if your question (or a similar one) is already present. If yes, just like it. We will give priority to the questions with the most likes. The rest will be answered by our mentors or the community. 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
#13

my repr function for Adjacency Matrix isnt working correctly
i have tried it in two following ways
first

 def __repr__(self):
        return str([print(self.data[i]) for i in range(self.num_nodes)])

this is giving

[0, 1, 0, 0, 1]
[1, 0, 1, 1, 1]
[0, 1, 0, 1, 0]
[0, 1, 1, 0, 1]
[1, 1, 0, 1, 0]

[None, None, None, None, None]

i want to remove none list
and second

def __repr__(self):
        for i in range(self.num_nodes):
            return str(self.data[i])

and this is returning

[0, 1, 0, 0, 1]

link to my notebook

#14

hi i came up with this shortest path algo on my own before watching the video

image
image1253×634 20.7 KB

i know this is a stupid question but is this same as Dijkstra’s algorithm. i came up with this after reading the explaination that was given in the jovian notebook.
it is also giving the correct answer so i thought i should confirm with some expert

in the below photo i compared the the time of mine and the given algo in notbook and my algo is certainly faster. so please someone confirm this

image
image992×387 11.1 KB

this is the link to my notebook

#15

nevermind, i understood what i am missing. correct me if i am wrong but the algo i have written doesn’t give shortest path but follows the path which seems shortest from current node

#16

Hi everyone, I have a question regarding the video of Lesson 5.

At 1:52:47 of the lesson video, I wonder why the algorithm on graph2 returns 15:

shortest_path(graph2, 2, 8)

While graph2 is defined as a undirected graph, the shortest path from 2 to 8 should be 12 (going through 2 → 3 → 0 → 8), instead of 15 (going through 2 → 3 → 4 → 8).

It is also strange that shortest_path(graph2, 1, 2) returns infinity, while shortest_path(graph2, 2, 1) returns 6. For undirected graph it should be the same.

Have anyone checked it out and had an idea of it? Am I understanding it correctly? Thank you for any of your advise.