Please visit the Lesson Page for more detailed info
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:
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!
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?
Hello, The notebook linked from the lesson page contains all the code, please go through it.
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!
so it gives me this! is it right!??
should i write…
parent.append(current) after popping!!(then it gives long list!)
I have done it like this and it gives correct result…
Hope it helps…
Has anyone implemented this…
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
I am also stuck at he time complexities of DFS and BFS and Dijkstra’s algorithm
Pls can someone explain them ???
Thanks for the reply. Yes I figured it out too and sure it helps.
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!
Check this out: https://youtu.be/XB4MIexjvY0 for Djikstra’s algiorithm.
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…
my repr function for Adjacency Matrix isnt working correctly
i have tried it in two following ways
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
for i in range(self.num_nodes):
and this is returning
[0, 1, 0, 0, 1]
link to my notebook
hi i came up with this shortest path algo on my own before watching the video
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
this is the link to my notebook
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
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.