title

G-5. Breadth-First Search (BFS) | C++ and Java | Traversal Technique in Graphs

description

GfG-Problem Link: https://bit.ly/3bn84K8
C++/Java/Codes and Notes Link: https://takeuforward.org/graph/breadth-first-search-bfs-level-order-traversal/
DP Series: https://www.youtube.com/watch?v=FfXoiwwnxFw&list=PLgUwDviBIf0qUlt5H_kiKYaNSqJ81PMMY
SDE Sheet: https://takeuforward.org/interviews/strivers-sde-sheet-top-coding-interview-problems/
Check out our Website for curated resources: https://www.takeuforward.org/
Our Second Channel: https://www.youtube.com/channel/UCvEKHATlVq84hm1jduTYm8g
In case you are thinking to buy courses, please check below:
Code "takeuforward" for 15% off at GFG: https://practice.geeksforgeeks.org/courses
Code "takeuforward" for 20% off on sys-design: https://get.interviewready.io?_aff=takeuforward
Crypto, I use the Wazirx app: https://wazirx.com/invite/xexnpc4u
Take 750 rs free Amazon Stock from me: https://indmoney.onelink.me/RmHC/idjex744
Earn 100 rs by making a Grow Account for investing: https://app.groww.in/v3cO/8hu879t0
Linkedin/Instagram/Telegram: https://linktr.ee/takeUforward
---------------------------------------------------------------------------------------------------------------------------

detail

{'title': 'G-5. Breadth-First Search (BFS) | C++ and Java | Traversal Technique in Graphs', 'heatmap': [{'end': 1042.064, 'start': 1007.918, 'weight': 1}], 'summary': 'Covers the importance and process of breadth-first search (bfs) technique in graph traversal, including its application, initial configuration steps, creating adjacency list, and time complexity of o(v+e).', 'chapters': [{'end': 63.272, 'segs': [{'end': 23.613, 'src': 'embed', 'start': 0.149, 'weight': 0, 'content': [{'end': 7.678, 'text': 'so, in order to solve any graph problems, we have to know traversal techniques, and the first traversal technique that we are going to learn is bfs,', 'start': 0.149, 'duration': 7.529}, {'end': 8.479, 'text': 'traversal technique.', 'start': 7.678, 'duration': 0.801}, {'end': 9.801, 'text': 'now, what is bfs?', 'start': 8.479, 'duration': 1.322}, {'end': 14.767, 'text': 'it is nothing but the breadth first search technique.', 'start': 9.801, 'duration': 4.966}, {'end': 17.95, 'text': 'okay, you must have heard about this if you have read trees.', 'start': 14.767, 'duration': 3.183}, {'end': 23.613, 'text': 'so this is the first technique that we are going to learn, and in the next video we will be learning something else dfs.', 'start': 17.95, 'duration': 5.663}], 'summary': 'To solve graph problems, learning traversal techniques like bfs is essential.', 'duration': 23.464, 'max_score': 0.149, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-tgVpUgsQ5k/pics/-tgVpUgsQ5k149.jpg'}, {'end': 68.736, 'src': 'embed', 'start': 41.395, 'weight': 2, 'content': [{'end': 44.457, 'text': 'now, usually graphs are of two kinds.', 'start': 41.395, 'duration': 3.062}, {'end': 48.02, 'text': 'one can be the one based indexing graph, which is this one.', 'start': 44.457, 'duration': 3.563}, {'end': 54.445, 'text': 'if you carefully see, n is eight over here and the graph numbering starts like the node numbering starts from one.', 'start': 48.02, 'duration': 6.425}, {'end': 59.309, 'text': 'or it can be zero based indexing, where the graph numbering starts from zero.', 'start': 54.445, 'duration': 4.864}, {'end': 60.189, 'text': 'that is okay.', 'start': 59.309, 'duration': 0.88}, {'end': 63.272, 'text': 'you just need to make sure you write the code according to that.', 'start': 60.189, 'duration': 3.083}, {'end': 65.153, 'text': 'but the logic remains same.', 'start': 63.272, 'duration': 1.881}, {'end': 67.555, 'text': "so let's come back to bfs.", 'start': 65.153, 'duration': 2.402}, {'end': 68.736, 'text': 'so what is breadth?', 'start': 67.555, 'duration': 1.181}], 'summary': 'Graphs can be one-based or zero-based indexing, with n=8, and the logic remains the same.', 'duration': 27.341, 'max_score': 41.395, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-tgVpUgsQ5k/pics/-tgVpUgsQ5k41395.jpg'}], 'start': 0.149, 'title': 'Graph traversal techniques: bfs', 'summary': 'Covers the importance of breadth first search (bfs) technique in problem-solving, with a brief mention of the upcoming dfs technique and the distinction between one-based and zero-based indexing graphs.', 'chapters': [{'end': 63.272, 'start': 0.149, 'title': 'Graph traversal techniques: bfs', 'summary': 'Covers the breadth first search (bfs) technique for graph traversal, emphasizing its importance and relevance in problem-solving, with a brief mention of the upcoming dfs technique and the distinction between one-based and zero-based indexing graphs.', 'duration': 63.123, 'highlights': ['BFS is the first traversal technique discussed, emphasizing its crucial role in solving graph problems.', 'The chapter introduces the concept of breadth first search (BFS) as a fundamental traversal technique for graphs.', 'The distinction between one-based and zero-based indexing graphs is briefly explained, highlighting the importance of adapting code to the specific indexing method.']}], 'duration': 63.123, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-tgVpUgsQ5k/pics/-tgVpUgsQ5k149.jpg', 'highlights': ['BFS is the first traversal technique discussed, emphasizing its crucial role in solving graph problems.', 'The chapter introduces the concept of breadth first search (BFS) as a fundamental traversal technique for graphs.', 'The distinction between one-based and zero-based indexing graphs is briefly explained, highlighting the importance of adapting code to the specific indexing method.']}, {'end': 505.284, 'segs': [{'end': 95.167, 'src': 'embed', 'start': 63.272, 'weight': 0, 'content': [{'end': 65.153, 'text': 'but the logic remains same.', 'start': 63.272, 'duration': 1.881}, {'end': 67.555, 'text': "so let's come back to bfs.", 'start': 65.153, 'duration': 2.402}, {'end': 68.736, 'text': 'so what is breadth?', 'start': 67.555, 'duration': 1.181}, {'end': 70.957, 'text': 'breadth first search.', 'start': 69.656, 'duration': 1.301}, {'end': 73.537, 'text': 'so this term is very important.', 'start': 70.957, 'duration': 2.58}, {'end': 78.979, 'text': 'breadth. it kind of signifies level wise traversal as well.', 'start': 73.537, 'duration': 5.442}, {'end': 81.46, 'text': 'this is also called as level wise traversal.', 'start': 78.979, 'duration': 2.481}, {'end': 84.301, 'text': 'but yeah, generally the generic term is breadth first.', 'start': 81.46, 'duration': 2.841}, {'end': 85.561, 'text': "so let's understand.", 'start': 84.301, 'duration': 1.26}, {'end': 95.167, 'text': 'so usually they will be telling you a starting node, okay, so assume i see you over here the starting node is one.', 'start': 85.561, 'duration': 9.606}], 'summary': 'Bfs (breadth first search) signifies level-wise traversal. starting node is one.', 'duration': 31.895, 'max_score': 63.272, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-tgVpUgsQ5k/pics/-tgVpUgsQ5k63272.jpg'}, {'end': 236.54, 'src': 'embed', 'start': 212.725, 'weight': 1, 'content': [{'end': 220.05, 'text': 'but if the starting node is one very, very important, if the starting node is one, what if i change the starting node?', 'start': 212.725, 'duration': 7.325}, {'end': 224.753, 'text': "so let's quickly change the starting node and understand bfs in depth.", 'start': 220.05, 'duration': 4.703}, {'end': 230.216, 'text': 'so assume, i tell you that the starting node as of now is six, okay.', 'start': 224.753, 'duration': 5.463}, {'end': 232.017, 'text': "so i've changed the starting node.", 'start': 230.216, 'duration': 1.801}, {'end': 236.54, 'text': 'remember this this is the starting node and this is at level zero.', 'start': 232.017, 'duration': 4.523}], 'summary': 'Changing the starting node to six for a deeper understanding of bfs.', 'duration': 23.815, 'max_score': 212.725, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-tgVpUgsQ5k/pics/-tgVpUgsQ5k212725.jpg'}, {'end': 505.284, 'src': 'embed', 'start': 433.02, 'weight': 2, 'content': [{'end': 438.881, 'text': 'this will be the initial configuration initially a queue which contains a starting node.', 'start': 433.02, 'duration': 5.861}, {'end': 444.763, 'text': 'initially a visited array which will be of size depending on its one based or zero based.', 'start': 438.881, 'duration': 5.882}, {'end': 450.726, 'text': 'you can decide, and the starting node will be traversed, so thereby it will be marked as one.', 'start': 444.763, 'duration': 5.963}, {'end': 455.59, 'text': 'this is going to be the initial or the starting configuration in a bfs traversal.', 'start': 450.726, 'duration': 4.864}, {'end': 457.871, 'text': 'what is the next step that you will do?', 'start': 455.59, 'duration': 2.281}, {'end': 460.953, 'text': 'whatever is in the queue, you will start taking it out.', 'start': 457.871, 'duration': 3.082}, {'end': 461.954, 'text': 'start taking it out.', 'start': 460.953, 'duration': 1.001}, {'end': 465.197, 'text': 'start taking it out till the queue is not empty.', 'start': 461.954, 'duration': 3.243}, {'end': 469.08, 'text': 'remember this keep taking out, keep taking out till the queue is not empty.', 'start': 465.197, 'duration': 3.883}, {'end': 475.498, 'text': "okay. so whatever is the uh q data structure, i take it out and you'll print it.", 'start': 469.08, 'duration': 6.418}, {'end': 476.84, 'text': 'so assume i print this.', 'start': 475.498, 'duration': 1.342}, {'end': 478.242, 'text': 'so this is printed.', 'start': 476.84, 'duration': 1.402}, {'end': 480.725, 'text': 'right. this is printed as a bfs travesty.', 'start': 478.242, 'duration': 2.483}, {'end': 486.353, 'text': 'now, very important whatever you take out of the queue, one you took out of the queue.', 'start': 480.725, 'duration': 5.628}, {'end': 491.794, 'text': 'so if you remember this graph, You would have stored this in some data structure.', 'start': 486.353, 'duration': 5.441}, {'end': 496.798, 'text': 'And which data structure was that? That data structure was adjacency list.', 'start': 492.294, 'duration': 4.504}, {'end': 498.119, 'text': 'Do you remember? Yes.', 'start': 496.978, 'duration': 1.141}, {'end': 501.541, 'text': 'So what will be the adjacency list for this particular graph??', 'start': 498.539, 'duration': 3.002}, {'end': 505.284, 'text': 'Can I say for 0, it will be an empty data structure?', 'start': 502.002, 'duration': 3.282}], 'summary': 'Initial configuration with a queue and traversal in bfs algorithm.', 'duration': 72.264, 'max_score': 433.02, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-tgVpUgsQ5k/pics/-tgVpUgsQ5k433020.jpg'}], 'start': 63.272, 'title': 'Bfs traversal in graphs', 'summary': 'Explains the initial configuration and steps for breadth-first search (bfs) traversal in a graph, including creating a queue and a visited array, and the process of taking out nodes from the queue and printing them.', 'chapters': [{'end': 336.702, 'start': 63.272, 'title': 'Bfs traversal explained', 'summary': 'Explains the breadth first search (bfs) traversal, emphasizing level-wise traversal and the impact of changing the starting node on the traversal path and levels.', 'duration': 273.43, 'highlights': ['The BFS traversal emphasizes level-wise traversal, where nodes are categorized into different levels based on their distance from the starting node, with the starting node being at level zero.', 'Changing the starting node in BFS traversal impacts the level categorization of nodes and the traversal path, as nodes are categorized based on their distance from the new starting node.']}, {'end': 505.284, 'start': 337.143, 'title': 'Bfs traversal in graphs', 'summary': 'Explains the initial configuration and steps for breadth-first search (bfs) traversal in a graph, including creating a queue and a visited array, and the process of taking out nodes from the queue and printing them.', 'duration': 168.141, 'highlights': ['The initial configuration for BFS traversal involves creating a queue data structure containing the starting node and a visited array of size 10 for a graph with nodes numbered till nine, marking the starting node as one and others as zero. The initial configuration for BFS traversal includes creating a queue with the starting node and a visited array of size 10 for a graph with nodes numbered till nine. The starting node is marked as one, while others are marked as zero.', 'The next step in BFS traversal involves taking out nodes from the queue until it is empty and printing them, following the First In First Out (FIFO) principle. The next step in BFS traversal is to take out nodes from the queue until it is empty and print them, following the First In First Out (FIFO) principle.', 'The adjacency list is a crucial data structure used to store the nodes and their connections in a graph for BFS traversal. The adjacency list is a crucial data structure used to store the nodes and their connections in a graph for BFS traversal.']}], 'duration': 442.012, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-tgVpUgsQ5k/pics/-tgVpUgsQ5k63272.jpg', 'highlights': ['The BFS traversal emphasizes level-wise traversal, categorizing nodes based on their distance from the starting node.', 'Changing the starting node in BFS traversal impacts the level categorization of nodes and the traversal path.', 'The initial configuration for BFS traversal involves creating a queue and a visited array of size 10 for a graph with nodes numbered till nine.', 'The next step in BFS traversal involves taking out nodes from the queue until it is empty and printing them, following the First In First Out (FIFO) principle.', 'The adjacency list is a crucial data structure used to store the nodes and their connections in a graph for BFS traversal.']}, {'end': 1169.91, 'segs': [{'end': 601.415, 'src': 'embed', 'start': 534.34, 'weight': 2, 'content': [{'end': 538.743, 'text': "so let's, uh, store two in it next will be four.", 'start': 534.34, 'duration': 4.403}, {'end': 541.325, 'text': 'for four, it is having five and two.', 'start': 538.743, 'duration': 2.582}, {'end': 549.776, 'text': 'so for four it will be two and five, for 5, for 6, for 7, for 8..', 'start': 541.325, 'duration': 8.451}, {'end': 558.328, 'text': 'Similarly, create the entire adjacency list that I have already taught you in the second video.', 'start': 549.776, 'duration': 8.552}, {'end': 562.033, 'text': 'So, kindly create this and after that we can start off with the BFS traversal.', 'start': 558.608, 'duration': 3.425}, {'end': 601.415, 'text': 'so. so this is how the entire adjacency list will look like now.', 'start': 596.03, 'duration': 5.385}], 'summary': 'Creating an adjacency list with specific values for bfs traversal.', 'duration': 67.075, 'max_score': 534.34, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-tgVpUgsQ5k/pics/-tgVpUgsQ5k534340.jpg'}, {'end': 1042.064, 'src': 'heatmap', 'start': 1007.918, 'weight': 1, 'content': [{'end': 1015.184, 'text': 'very simple and let me put them into the queue as well so that in the next step they can be taken into the pfs.', 'start': 1007.918, 'duration': 7.266}, {'end': 1018.626, 'text': 'once this is done, you can say this is my answer.', 'start': 1015.184, 'duration': 3.442}, {'end': 1027.118, 'text': "once this is done, you can always say this is my answer okay, now let's quickly compile this and check if you see, uh, the compilation is successful,", 'start': 1018.626, 'duration': 8.492}, {'end': 1030.079, 'text': "and let's quickly now submit the code and check if it's working fine.", 'start': 1027.118, 'duration': 2.961}, {'end': 1035.281, 'text': "and so it's time to understand the space complexity and the time complexity.", 'start': 1030.079, 'duration': 5.202}, {'end': 1042.064, 'text': 'space complexity is very simple a queue, a visited node and a bfs uh list.', 'start': 1035.281, 'duration': 6.783}], 'summary': 'Using simple queue and bfs list for time and space complexity.', 'duration': 34.146, 'max_score': 1007.918, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-tgVpUgsQ5k/pics/-tgVpUgsQ5k1007918.jpg'}, {'end': 1156.341, 'src': 'embed', 'start': 1130.06, 'weight': 0, 'content': [{'end': 1135.504, 'text': 'and if you remember the total degrees, we have already concluded as twice of edges.', 'start': 1130.06, 'duration': 5.444}, {'end': 1142.63, 'text': 'this was done in the first lecture, the total degrees, because for every node we traverse all the neighboring nodes.', 'start': 1135.504, 'duration': 7.126}, {'end': 1147.054, 'text': 'so this will be the time complexity for this particular guy.', 'start': 1142.63, 'duration': 4.424}, {'end': 1150.356, 'text': 'so, guys, i hope you have understood the entire bfs algorithm.', 'start': 1147.054, 'duration': 3.302}, {'end': 1156.341, 'text': "just in case you did, please, please, please make sure you like this video and if you're new to our channel, What are you waiting for?", 'start': 1150.356, 'duration': 5.985}], 'summary': "Bfs algorithm's time complexity is twice the total edges. understand bfs algorithm.", 'duration': 26.281, 'max_score': 1130.06, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-tgVpUgsQ5k/pics/-tgVpUgsQ5k1130060.jpg'}], 'start': 506.305, 'title': 'Bfs traversal in graphs', 'summary': 'Covers creating an adjacency list for bfs traversal and explains the breadth-first search (bfs) algorithm with a time complexity of o(v+e) and code structure explanation.', 'chapters': [{'end': 601.415, 'start': 506.305, 'title': 'Creating adjacency list for bfs traversal', 'summary': 'Covers the process of creating an adjacency list for bfs traversal, involving storing various elements and forming connections, followed by a plan to initiate bfs traversal.', 'duration': 95.11, 'highlights': ['Creating an adjacency list involves storing elements and their connections, such as 1 storing 2 and 6, 3 storing 2, and 2 storing 1, 3, and 4.', 'The next step after creating the adjacency list is to initiate BFS traversal.', 'The process of creating the adjacency list was detailed in the second video.']}, {'end': 1169.91, 'start': 601.415, 'title': 'Bfs traversal of a graph', 'summary': 'Explains the breadth-first search (bfs) algorithm for traversing a graph, demonstrating the process and providing a time complexity analysis of o(v+e), with a clear explanation of the code structure.', 'duration': 568.495, 'highlights': ['The chapter explains the BFS algorithm for traversing a graph, providing a detailed step-by-step explanation of the process, including marking nodes as visited, adding neighbors to a queue, and time complexity analysis.', 'The time complexity of the BFS algorithm is analyzed, with a detailed explanation of how the algorithm runs for each node and its degrees, resulting in a time complexity of O(V+E).', 'The explanation includes a demonstration of the code structure for implementing the BFS algorithm, emphasizing the use of a visited array, a queue, and an adjacency list provided for the graph.']}], 'duration': 663.605, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-tgVpUgsQ5k/pics/-tgVpUgsQ5k506305.jpg', 'highlights': ['The time complexity of the BFS algorithm is analyzed, with a detailed explanation of how the algorithm runs for each node and its degrees, resulting in a time complexity of O(V+E).', 'The chapter explains the BFS algorithm for traversing a graph, providing a detailed step-by-step explanation of the process, including marking nodes as visited, adding neighbors to a queue, and time complexity analysis.', 'Creating an adjacency list involves storing elements and their connections, such as 1 storing 2 and 6, 3 storing 2, and 2 storing 1, 3, and 4.', 'The next step after creating the adjacency list is to initiate BFS traversal.']}], 'highlights': ['The time complexity of the BFS algorithm is analyzed, with a detailed explanation of how the algorithm runs for each node and its degrees, resulting in a time complexity of O(V+E).', 'The chapter explains the BFS algorithm for traversing a graph, providing a detailed step-by-step explanation of the process, including marking nodes as visited, adding neighbors to a queue, and time complexity analysis.', 'The adjacency list is a crucial data structure used to store the nodes and their connections in a graph for BFS traversal.', 'The next step after creating the adjacency list is to initiate BFS traversal.', 'The initial configuration for BFS traversal involves creating a queue and a visited array of size 10 for a graph with nodes numbered till nine.', 'The next step in BFS traversal involves taking out nodes from the queue until it is empty and printing them, following the First In First Out (FIFO) principle.', 'Creating an adjacency list involves storing elements and their connections, such as 1 storing 2 and 6, 3 storing 2, and 2 storing 1, 3, and 4.', 'The BFS traversal emphasizes level-wise traversal, categorizing nodes based on their distance from the starting node.', 'Changing the starting node in BFS traversal impacts the level categorization of nodes and the traversal path.', 'The distinction between one-based and zero-based indexing graphs is briefly explained, highlighting the importance of adapting code to the specific indexing method.', 'BFS is the first traversal technique discussed, emphasizing its crucial role in solving graph problems.', 'The chapter introduces the concept of breadth first search (BFS) as a fundamental traversal technique for graphs.']}