[7.3] Breadth First Search(BFS) in Python | Graph Theory | Data Structures in Python
In this tutorial we will implement BFS algorithm in Python.
Breadth-first search is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root, and explores all of the neighbor nodes at the present level before moving on to the nodes at the next level.
🔗Important Links:
Data Structures in Python: www.thinkxacademy.com/Data%20...
🌐Join our community:
Android App(Notes+Videos): play.google.com/store/apps/de... Facebook: / thinkxacademy Twitter: / thinkxacademy Instagram: / thinkxacademy
#graphtheory #bfs #python #datastructures #algorithms
Пікірлер: 56
Use this dictionary: graph = {0: [1, 2], 1: [2,3,0], 2: [3,1,0], 3: [1, 2]}
@shabareesharyan
Жыл бұрын
Hey, i just wanted to clarify one thing that is use a list instead of set. Because set treats each element as a unique object instead of a sequence. I tried sets and it prints the visited nodes in random fashion everytime. Using list solves that problem
@amanlall8496
3 ай бұрын
In your graph, 2nd vertex should be 2:[0,1,4] and not 2:[0,1] but it worked anyway
Thank you very much, I've watched many BFS tutorial videos and this is the best I've seen. Your explanations are clear and precise and your scripting is easy to follow along with.
@ThinkXAcademy
2 жыл бұрын
Thanks😀This really motivates me to create these videos😄
Thanks, simple and understandable explanation!
Thanks ❣❣
It is so well explained please make a video on dFS, DLS, uniform cost search, and greedy best-first search implementation in python
Thanks bro, much helpful !!!
@ThinkXAcademy
2 жыл бұрын
Thanks bro😄Share my videos to help my channel grow💯
Write a function called searchBFS which given the tree or graph as defined below returns every number smaller than 4 in the order it was found using the breadth first technique.
@ThinkXAcademy
2 жыл бұрын
can you show graph of this question?
Thank you !!!
good explanation loved it !!
@ThinkXAcademy
2 жыл бұрын
Thanks☺️Make sure to share our videos to help this channel growth💯
Thank you so much for this video.
@ThinkXAcademy
2 жыл бұрын
Please share our videos to help this channel grow😊
@Abhishekkumar-jl2dr
2 жыл бұрын
@@ThinkXAcademy please give me some ideas or approach to solve this question "Knight and Bishop meeting point on a 8*8 chess board and few blocks are blocked" Please give me some ideas
Thanks
Nice explanation!
@ThinkXAcademy
3 жыл бұрын
Thank you🙂 Share our content to support👍🏻
in your graph dictionary 2 has a connection with 0,1 and 4. In the grap dictionary,which you defined, "2" has only two connections 1 and 0, should that list include 4 also?
@ThinkXAcademy
2 жыл бұрын
you can add 4 in that list but i have added node 2 in the list of nodes of 4 so that's fine but do not add it in both that will give unexpected output
@titasarirahmawati1587
2 жыл бұрын
@@ThinkXAcademy so in dictionary 1 only connected with 2
@titasarirahmawati1587
2 жыл бұрын
1:0,2.. must 1:2
@ThinkXAcademy
2 жыл бұрын
in the dictionary you can see 1:[0,2] so 1 is connected with 0 and 2.
what is the link for video you mentioned about cycles in undirected graph
@ThinkXAcademy
Жыл бұрын
Video and Code is available on this website just go to the course and find the video: www.thinkxacademy.com
nice vid but pls explain why we add firstly to queue if we could just add straight to visited array???
@tusharvyavahare9229
Жыл бұрын
first element in the queue tells the program, where you are in the graph at the moment, so at first you're at root, hence root should be in the queue at start [if queue is empty, the while loop won't start]. You're adding a node to visited set, when you're going to leave the node for further travelling. Also set in python is unordered(mostly doesn't store elements in the insertion order), so you should not use set.
@ThinkXAcademy
Жыл бұрын
Great explanation @Tushar
why did we use visited= set() ? As we are defining a condition which will not repeat the visited nodes
@SJ-kp2hq
5 ай бұрын
Nice observation 😅
set function cannot be taken as it sorts the data in it. try it by changing the root node.
@ThinkXAcademy
2 жыл бұрын
in visited array order does not matter even if it sorted the algorithm will work. Change graph dictionary to this and it will work with any root node: graph = {0: [1, 2], 1: [2,3,0], 2: [3,1,0], 3: [1, 2]}
@aneeshgarray5569
2 жыл бұрын
@@ThinkXAcademy u r printing the visited array as final result So order matters
@ThinkXAcademy
2 жыл бұрын
i ran the program and the result i am getting is not sorted, tried with node 2: output was 2,3,1,0 which is not sorted
@akanshgoswami4899
2 жыл бұрын
@@ThinkXAcademy i am getting the sort output, tried with node 2 : output was {0, 1, 2, 3}.
@sakethdamam3280
2 жыл бұрын
@@ThinkXAcademy when we run set() returns new output everytime
thnaqu so much man
@ThinkXAcademy
2 жыл бұрын
Please share my videos with other students to help this channel grow🌟🧑🏻💻
How can we upload text file into dictionary
Can you please make a video on recursion how to master it from zero level questions to advance means from basic to advance.. Please can you?
@ThinkXAcademy
2 жыл бұрын
kzread.info/dash/bejne/YnaWm5KEqbDSoNo.html
@ThinkXAcademy
2 жыл бұрын
This will give you good idea about recursion👍🏻
@056_anmolkumarojha2
2 жыл бұрын
Thank you , also if possible please provide your viewers a path how to master important topics like recursion, trees, graph, greedy DP will be very helpful 😊
@ThinkXAcademy
2 жыл бұрын
sure i will
Waiting for DFS
@ThinkXAcademy
3 жыл бұрын
Coming tomorrow ✅
Plz complete course bro
@ThinkXAcademy
3 жыл бұрын
Working on it..
@black_eye7105
3 жыл бұрын
Yes bro complicate all the topic.
@md_arfin_cse
3 жыл бұрын
@@black_eye7105 ty bro
bro we RE FIND TO SHORTEST PATH FROM INITIAL TO GOAL, so 0,1,2,4 is answer why you are printed 0,1,2,3,4 in this case 3 is not connected to 4 .
@ThinkXAcademy
Жыл бұрын
This is breadth first search technique, it does not aim at finding shortest path. It is a graph traversal algorithm which visits every node in the graph
H'atr hetyet hìerël hâyarŕ nös?!