title
6.2 BFS and DFS Graph Traversals| Breadth First Search and Depth First Search | Data structures

description
In this video, I have explained BFS and DFS Graph Traversal | BFS (Breadth First Search) DFS (Depth First Search), BFS with help of Queue data structure and DFS with the help of Stack data structure. DSA Full Course: https: https://www.youtube.com/playlist?list=PLdo5W4Nhv31bbKJzrsKfMpo_grxuLl8LU ****************************************** More Playlists: C Programming Course: https://www.youtube.com/playlist?list=PLdo5W4Nhv31a8UcMN9-35ghv8qyFWD9_S C++ Programming: https://www.youtube.com/playlist?list=PLdo5W4Nhv31YU5Wx1dopka58teWP9aCee Python Full Course: https://www.youtube.com/playlist?list=PLdo5W4Nhv31bZSiqiOL5ta39vSnBxpOPT Printing Pattern in C: https://www.youtube.com/playlist?list=PLdo5W4Nhv31Yu1igxTE2x0aeShbKtVcCy DAA Course: https://www.youtube.com/playlist?list=PLdo5W4Nhv31ZTn2P9vF02bkb3SC8uiUUn Placement Series: https://www.youtube.com/playlist?list=PLdo5W4Nhv31YvlDpJhvOYbM9Ap8UypgEy Dynamic Programming: https://www.youtube.com/playlist?list=PLdo5W4Nhv31aBrJE1WS4MR9LRfbmZrAQu Operating Systems: //www.youtube.com/playlist?list=PLdo5W4Nhv31a5ucW_S1K3-x6ztBRD-PNa DBMS: https://www.youtube.com/playlist?list=PLdo5W4Nhv31b33kF46f9aFjoJPOkdlsRc ******************************************* Connect & Contact Me: Facebook: https://www.facebook.com/Jennys-Lectures-CSIT-Netjrf-316814368950701/ Quora: https://www.quora.com/profile/Jayanti-Khatri-Lamba Instagram: https://www.instagram.com/jayantikhatrilamba/ #bfs #dfs #datastructures #jennyslectures

detail
{'title': '6.2 BFS and DFS Graph Traversals| Breadth First Search and Depth First Search | Data structures', 'heatmap': [{'end': 66.367, 'start': 32.381, 'weight': 0.821}, {'end': 125.043, 'start': 110.07, 'weight': 0.738}, {'end': 197.786, 'start': 152.658, 'weight': 0.746}, {'end': 265.202, 'start': 225.943, 'weight': 0.928}, {'end': 540.968, 'start': 500.805, 'weight': 1}, {'end': 627.08, 'start': 551.355, 'weight': 0.701}, {'end': 740.573, 'start': 726.994, 'weight': 0.701}, {'end': 947.753, 'start': 919.288, 'weight': 0.835}, {'end': 1034.574, 'start': 1005.412, 'weight': 0.744}], 'summary': 'Covers bfs and dfs graph traversal techniques, explaining the use of queue for bfs and stack for dfs, emphasizing the process of visiting adjacent vertices, insertion and backtracking, and highlighting multiple valid traversals for both techniques.', 'chapters': [{'end': 322.179, 'segs': [{'end': 66.367, 'src': 'heatmap', 'start': 0.549, 'weight': 0, 'content': [{'end': 5.174, 'text': 'hi guys, in this video I am going to discuss with you graph traversal techniques.', 'start': 0.549, 'duration': 4.625}, {'end': 10.459, 'text': 'two types of graph traversal techniques are there BFS and DFS.', 'start': 5.174, 'duration': 5.285}, {'end': 24.199, 'text': 'bfs means breadth first search, or sometimes it is also known as level order traversal, and dfs is depth first search fine.', 'start': 11.795, 'duration': 12.404}, {'end': 32.381, 'text': 'so we will take this example and with the help of this example i am going to discuss with you the bfs traversal fine.', 'start': 24.199, 'duration': 8.182}, {'end': 37.504, 'text': 'in bfs traversal, when you will start, then you can take any node as a root node.', 'start': 32.381, 'duration': 5.123}, {'end': 40.885, 'text': 'you can start traversing this graph from any node.', 'start': 37.504, 'duration': 3.381}, {'end': 47.911, 'text': 'Suppose we can take 0, you can take 1, you can take 6 as a root node and you can start your traversal.', 'start': 41.545, 'duration': 6.366}, {'end': 57.239, 'text': 'But sometimes in question if it is given that BFS traversal find out of this graph and considering 2 as a root node.', 'start': 48.511, 'duration': 8.728}, {'end': 61.063, 'text': 'Then what you have to do is you are supposed to start from this 2.', 'start': 57.62, 'duration': 3.443}, {'end': 66.367, 'text': 'You will consider 2 as a root node and you will start traversing this graph from this node only.', 'start': 61.063, 'duration': 5.304}], 'summary': 'Video discussing graph traversal techniques: bfs and dfs', 'duration': 56.69, 'max_score': 0.549, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/vf-cxgUXcMk/pics/vf-cxgUXcMk549.jpg'}, {'end': 151.578, 'src': 'heatmap', 'start': 110.07, 'weight': 2, 'content': [{'end': 117.919, 'text': 'Okay All the adjacent vertices of this 0 will be traversed first.', 'start': 110.07, 'duration': 7.849}, {'end': 125.043, 'text': 'Means try to traverse all the vertices as close as possible to the root vertex.', 'start': 118.059, 'duration': 6.984}, {'end': 129.806, 'text': 'See, its adjacent vertices are 1 and 3.', 'start': 125.644, 'duration': 4.162}, {'end': 135.871, 'text': 'So, 0 will visit after that 1 or 3 or either 3 or 1 in any fashion.', 'start': 129.806, 'duration': 6.065}, {'end': 137.612, 'text': 'After that you would move forward.', 'start': 135.951, 'duration': 1.661}, {'end': 143.115, 'text': 'It will not happen that after 0 you visit 1 and then you would visit 5.', 'start': 137.852, 'duration': 5.263}, {'end': 151.578, 'text': 'First of all, all the vertices as close as possible to this 0, those vertices would be visited.', 'start': 143.115, 'duration': 8.463}], 'summary': 'Traverse adjacent vertices of 0 before moving forward, visiting 1 and 3 first.', 'duration': 67.554, 'max_score': 110.07, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/vf-cxgUXcMk/pics/vf-cxgUXcMk110070.jpg'}, {'end': 197.786, 'src': 'heatmap', 'start': 152.658, 'weight': 0.746, 'content': [{'end': 160.721, 'text': 'Now see, suppose we have taken 0 as a root node, so 0 would be inserted in this Q.', 'start': 152.658, 'duration': 8.063}, {'end': 173.046, 'text': 'fine, okay, now, in the result we have, suppose we have deleted this zero and we have printed this zero in the result.', 'start': 162.116, 'duration': 10.93}, {'end': 179.673, 'text': 'fine, now, as soon as the zero is printed means zero has been visited.', 'start': 173.046, 'duration': 6.627}, {'end': 183.015, 'text': 'fine now, next thing, what you have to do is zero.', 'start': 179.673, 'duration': 3.342}, {'end': 184.977, 'text': 'ko jaise yahan se delete hoga.', 'start': 183.015, 'duration': 1.962}, {'end': 190.821, 'text': 'uske jitne bhi adjacent vertices hongi zero ke that would be inserted in this queue.', 'start': 184.977, 'duration': 5.844}, {'end': 194.623, 'text': 'now, adjacent vertices of this zero is one and three.', 'start': 190.821, 'duration': 3.802}, {'end': 197.786, 'text': 'fine, now one and three would be inserted in this queue.', 'start': 194.623, 'duration': 3.163}], 'summary': 'Traversal of vertices from 0, inserting 1 and 3 into the queue.', 'duration': 45.128, 'max_score': 152.658, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/vf-cxgUXcMk/pics/vf-cxgUXcMk152658.jpg'}, {'end': 293.361, 'src': 'heatmap', 'start': 225.943, 'weight': 5, 'content': [{'end': 242.487, 'text': 'means 1 has already been visited now next thing what you have to do is all the adjacent vertices of 1 adjacent vertices plus unvisited vertices Fine.', 'start': 225.943, 'duration': 16.544}, {'end': 250.432, 'text': 'Adjacent unvisited vertices of 1 would be inserted in this Q.', 'start': 244.188, 'duration': 6.244}, {'end': 254.575, 'text': 'See, how many adjacent vertices of 1 are there? 0, 3, 2, 5 and 6.', 'start': 250.432, 'duration': 4.143}, {'end': 256.815, 'text': 'I will write 0, 3, 2, 5 and 6.', 'start': 254.575, 'duration': 2.24}, {'end': 265.202, 'text': 'But you have to insert only the unvisited vertices.', 'start': 256.815, 'duration': 8.387}, {'end': 266.062, 'text': '0 has already been visited.', 'start': 265.222, 'duration': 0.84}, {'end': 277.533, 'text': 'Fine 0 has already been visited, so you will not insert 0 in it.', 'start': 272.731, 'duration': 4.802}, {'end': 280.495, 'text': 'And 3, 3 has already been inserted.', 'start': 278.294, 'duration': 2.201}, {'end': 284.357, 'text': "Fine So, you also don't have to insert this in it.", 'start': 281.855, 'duration': 2.502}, {'end': 290.82, 'text': 'Which will be inserted in it? 2, 5 and 6.', 'start': 285.817, 'duration': 5.003}, {'end': 293.361, 'text': '2, 5 and 6.', 'start': 290.82, 'duration': 2.541}], 'summary': 'Insert unvisited adjacent vertices 2, 5, and 6 of vertex 1 into the queue.', 'duration': 42.929, 'max_score': 225.943, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/vf-cxgUXcMk/pics/vf-cxgUXcMk225943.jpg'}], 'start': 0.549, 'title': 'Graph traversal techniques', 'summary': 'Discusses bfs and dfs graph traversal techniques, including their definitions and the use of a queue data structure for bfs traversal, emphasizing the fifo nature of the queue. it also explains a vertex traversal algorithm with an example of inserting and visiting vertices using a queue, emphasizing the order of visiting adjacent vertices and the insertion of unvisited vertices. additionally, it discusses how to identify and insert unvisited adjacent vertices of a given vertex in a graph, demonstrating the process with specific examples and emphasizing the importance of considering only unvisited vertices for insertion.', 'chapters': [{'end': 117.919, 'start': 0.549, 'title': 'Graph traversal techniques', 'summary': 'Discusses bfs and dfs graph traversal techniques, including their definitions and the use of a queue data structure for bfs traversal, emphasizing the fifo (first in first out) nature of the queue.', 'duration': 117.37, 'highlights': ['BFS and DFS are the two types of graph traversal techniques, with BFS also known as level order traversal and DFS as depth first search.', 'In BFS traversal, any node can be taken as the root node, and a queue data structure is used for traversing the graph in a FIFO manner.', 'The Q data structure is used for BFS traversal, working in a FIFO (First In First Out) fashion.']}, {'end': 250.432, 'start': 118.059, 'title': 'Traversing vertices algorithm', 'summary': 'Explains a vertex traversal algorithm with an example of inserting and visiting vertices using a queue, emphasizing the order of visiting adjacent vertices and the insertion of unvisited vertices.', 'duration': 132.373, 'highlights': ['The algorithm emphasizes visiting adjacent vertices as close as possible to the root vertex, ensuring that all such vertices are visited first.', 'The process involves inserting the root vertex into a queue, deleting it from the queue after visiting, and then inserting its adjacent unvisited vertices into the queue.', 'The example demonstrates the insertion of adjacent vertices in any order, emphasizing the flexibility of the algorithm for inserting unvisited vertices.']}, {'end': 322.179, 'start': 250.432, 'title': 'Graph adjacent vertices', 'summary': 'Discusses how to identify and insert unvisited adjacent vertices of a given vertex in a graph, demonstrating the process with specific examples and emphasizing the importance of considering only unvisited vertices for insertion.', 'duration': 71.747, 'highlights': ['The chapter emphasizes the importance of inserting only unvisited adjacent vertices, demonstrating this by identifying and inserting unvisited vertices 2, 5, and 6, while omitting the previously visited vertices 0 and 3.', 'The speaker highlights the flexibility in the order of insertion, emphasizing that the sequence of insertion for unvisited adjacent vertices, such as 2, 5, and 6, can vary, providing examples like 5, 2, 6 or 6, 5, 2.', 'The chapter discusses the process of identifying the adjacent vertices of a given vertex, exemplifying with the identification of adjacent vertices of the vertex 3 and subsequent actions.']}], 'duration': 321.63, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/vf-cxgUXcMk/pics/vf-cxgUXcMk549.jpg', 'highlights': ['BFS and DFS are the two types of graph traversal techniques, with BFS also known as level order traversal and DFS as depth first search.', 'In BFS traversal, any node can be taken as the root node, and a queue data structure is used for traversing the graph in a FIFO manner.', 'The Q data structure is used for BFS traversal, working in a FIFO (First In First Out) fashion.', 'The algorithm emphasizes visiting adjacent vertices as close as possible to the root vertex, ensuring that all such vertices are visited first.', 'The process involves inserting the root vertex into a queue, deleting it from the queue after visiting, and then inserting its adjacent unvisited vertices into the queue.', 'The chapter emphasizes the importance of inserting only unvisited adjacent vertices, demonstrating this by identifying and inserting unvisited vertices 2, 5, and 6, while omitting the previously visited vertices 0 and 3.']}, {'end': 608.249, 'segs': [{'end': 346.679, 'src': 'embed', 'start': 322.179, 'weight': 0, 'content': [{'end': 328.64, 'text': 'see this what we are finding out all the adjacent vertices of any node.', 'start': 322.179, 'duration': 6.461}, {'end': 330.528, 'text': 'it is called exploration of that node.', 'start': 328.64, 'duration': 1.888}, {'end': 332.335, 'text': 'You are going to explore that node.', 'start': 330.668, 'duration': 1.667}, {'end': 337.935, 'text': 'Fine Now find out the adjacent vertices of this 3.', 'start': 332.998, 'duration': 4.937}, {'end': 345.998, 'text': 'Adjacent vertices of this 3 are, see we have printed 3 means that has already been printed or you can say that has already been visited.', 'start': 337.935, 'duration': 8.063}, {'end': 346.679, 'text': 'This is fine.', 'start': 346.018, 'duration': 0.661}], 'summary': 'Exploring adjacent vertices of node 3, already visited.', 'duration': 24.5, 'max_score': 322.179, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/vf-cxgUXcMk/pics/vf-cxgUXcMk322179.jpg'}, {'end': 608.249, 'src': 'heatmap', 'start': 500.805, 'weight': 3, 'content': [{'end': 509.011, 'text': 'method. fine, now we will discuss the dfs traversal of this graph.', 'start': 500.805, 'duration': 8.206}, {'end': 512.673, 'text': 'now we would find out the dfs traversal of this graph.', 'start': 509.011, 'duration': 3.662}, {'end': 514.275, 'text': 'dfs means depth.', 'start': 512.673, 'duration': 1.602}, {'end': 517.577, 'text': 'first search traversal of this graph.', 'start': 514.275, 'duration': 3.302}, {'end': 523.501, 'text': 'okay, in bfs queue data structure is used and, as in dfs, what data structure will be used.', 'start': 517.577, 'duration': 5.924}, {'end': 528.785, 'text': 'that is stack and it works in leaf form and it lasts in first out.', 'start': 523.501, 'duration': 5.284}, {'end': 533.265, 'text': 'okay, so we will have one stack.', 'start': 529.284, 'duration': 3.981}, {'end': 540.968, 'text': 'fine, and here we will write down the result of this traversal.', 'start': 533.265, 'duration': 7.703}, {'end': 544.829, 'text': 'same, in that bfs we have taken any node as root node.', 'start': 540.968, 'duration': 3.861}, {'end': 549.711, 'text': 'so in dfs also, you can take any node as root node and you can start traversing from that node.', 'start': 544.829, 'duration': 4.882}, {'end': 554.916, 'text': 'in case, if it is given, that consider 1 as a root node.', 'start': 551.355, 'duration': 3.561}, {'end': 557.477, 'text': 'in that case you have to take 1 as root node.', 'start': 554.916, 'duration': 2.561}, {'end': 560.477, 'text': 'but if it is not given, then you can take any node as root node.', 'start': 557.477, 'duration': 3}, {'end': 563.898, 'text': 'suppose we are taking 0 as root node.', 'start': 560.477, 'duration': 3.421}, {'end': 573.721, 'text': 'okay, now see, 0 would be inserted in this stack, fine, and 0 would be printed.', 'start': 563.898, 'duration': 9.823}, {'end': 578.522, 'text': 'okay, now check how many adjacent vertices of 0 are there?', 'start': 573.721, 'duration': 4.801}, {'end': 582.659, 'text': '1 and So what we did in DFS?', 'start': 578.522, 'duration': 4.137}, {'end': 593.623, 'text': 'all the adjacent vertices of that note which we have deleted from Q and which we have printed, all its adjacent vertices, we have inserted into Q.', 'start': 582.659, 'duration': 10.964}, {'end': 595.964, 'text': 'But what will happen in DFS?', 'start': 593.623, 'duration': 2.341}, {'end': 597.385, 'text': 'only one.', 'start': 595.964, 'duration': 1.421}, {'end': 604.966, 'text': 'any one of that node would be inserted into stack.', 'start': 597.385, 'duration': 7.581}, {'end': 608.249, 'text': 'depth first, search.', 'start': 604.966, 'duration': 3.283}], 'summary': 'The discussion focuses on dfs traversal of a graph, using a stack data structure for traversal, and choosing a root node for the traversal.', 'duration': 126.308, 'max_score': 500.805, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/vf-cxgUXcMk/pics/vf-cxgUXcMk500805.jpg'}], 'start': 322.179, 'title': 'Graph traversal algorithms', 'summary': 'Explains the process of exploring adjacent vertices and using bfs and dfs traversal techniques in graph theory. it covers identification of adjacent vertices, insertion and printing of visited vertices, bfs traversal, multiple valid traversals, dfs traversal, and the usage of stack data structure.', 'chapters': [{'end': 451.865, 'start': 322.179, 'title': 'Exploration of adjacent vertices', 'summary': 'Explains the process of exploring adjacent vertices of nodes in a graph, highlighting the concept of exploration, identification of adjacent vertices, and the process of inserting and printing visited vertices in a queue.', 'duration': 129.686, 'highlights': ['The process involves identifying and exploring the adjacent vertices of a node in a graph, ensuring that only unvisited vertices are inserted in the queue. (Relevance: 5)', 'The method includes the identification and exclusion of already visited vertices, ensuring that only unvisited vertices are inserted in the queue for exploration. (Relevance: 4)', 'The exploration process involves deleting and printing visited vertices, along with the identification of their adjacent vertices for further exploration. (Relevance: 3)', 'The concept emphasizes the avoidance of inserting already visited vertices in the exploration queue, ensuring that only unvisited vertices are processed. (Relevance: 2)']}, {'end': 517.577, 'start': 451.865, 'title': 'Bfs and dfs traversal explanation', 'summary': 'Discusses the bfs traversal of a graph, highlighting the concept of multiple valid traversals based on the order of insertion, and then transitions to discussing the dfs traversal of the graph.', 'duration': 65.712, 'highlights': ['The concept of multiple valid BFS traversals of the graph based on the order of insertion is explained, emphasizing the flexibility in finding numerous valid BFS traversals.', 'Transition to discussing the DFS traversal of the graph is mentioned, indicating a shift in focus from BFS to DFS traversal.']}, {'end': 608.249, 'start': 517.577, 'title': 'Dfs data structure and traversal', 'summary': 'Discusses the usage of stack data structure in depth-first search (dfs) traversal, highlighting the process of selecting a root node and traversing adjacent vertices in a depth-first manner.', 'duration': 90.672, 'highlights': ['DFS uses a stack data structure for traversal, following the Last In First Out (LIFO) principle, and the process involves selecting a root node and traversing from that node.', 'In DFS, the selection of a root node is flexible, allowing any node to be chosen unless specified, and the traversal involves inserting the adjacent vertices of the selected node into the stack in a depth-first manner.', 'The process of DFS involves inserting the root node into the stack, printing it, and then traversing its adjacent vertices in a depth-first manner, inserting one adjacent vertex into the stack at a time.']}], 'duration': 286.07, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/vf-cxgUXcMk/pics/vf-cxgUXcMk322179.jpg', 'highlights': ['The process involves identifying and exploring the adjacent vertices of a node in a graph, ensuring that only unvisited vertices are inserted in the queue.', 'The method includes the identification and exclusion of already visited vertices, ensuring that only unvisited vertices are inserted in the queue for exploration.', 'The exploration process involves deleting and printing visited vertices, along with the identification of their adjacent vertices for further exploration.', 'The concept of multiple valid BFS traversals of the graph based on the order of insertion is explained, emphasizing the flexibility in finding numerous valid BFS traversals.', 'DFS uses a stack data structure for traversal, following the Last In First Out (LIFO) principle, and the process involves selecting a root node and traversing from that node.', 'In DFS, the selection of a root node is flexible, allowing any node to be chosen unless specified, and the traversal involves inserting the adjacent vertices of the selected node into the stack in a depth-first manner.', 'The process of DFS involves inserting the root node into the stack, printing it, and then traversing its adjacent vertices in a depth-first manner, inserting one adjacent vertex into the stack at a time.', 'The concept emphasizes the avoidance of inserting already visited vertices in the exploration queue, ensuring that only unvisited vertices are processed.']}, {'end': 931.759, 'segs': [{'end': 740.573, 'src': 'heatmap', 'start': 640.523, 'weight': 0, 'content': [{'end': 644.284, 'text': "in case you don't get anything, then you will backtrack.", 'start': 640.523, 'duration': 3.761}, {'end': 653.011, 'text': 'fine. but depth first search means you will go deeper and deeper until a dead end.', 'start': 644.284, 'duration': 8.727}, {'end': 656.935, 'text': 'dead end means its adjacent, unvisited adjacent.', 'start': 653.011, 'duration': 3.924}, {'end': 659.517, 'text': 'nothing will happen and you have to backtrack.', 'start': 656.935, 'duration': 2.582}, {'end': 664.923, 'text': 'fine. so any one of this vertex zero is printed.', 'start': 659.517, 'duration': 5.406}, {'end': 670.314, 'text': 'so any one of this zero Would be taken.', 'start': 664.923, 'duration': 5.391}, {'end': 673.256, 'text': 'Any one adjacent vertices of this 0 would be taken.', 'start': 670.595, 'duration': 2.661}, {'end': 674.977, 'text': 'And pushed into this stack.', 'start': 673.336, 'duration': 1.641}, {'end': 677.939, 'text': 'Suppose we have 1 and 3.', 'start': 675.017, 'duration': 2.922}, {'end': 679.72, 'text': 'Two adjacent vertices of 0 we have.', 'start': 677.939, 'duration': 1.781}, {'end': 683.382, 'text': 'So you can take either 1 or you can take 3.', 'start': 680.04, 'duration': 3.342}, {'end': 687.305, 'text': 'Suppose we are taking 1.', 'start': 683.382, 'duration': 3.923}, {'end': 688.125, 'text': '1 would be printed.', 'start': 687.305, 'duration': 0.82}, {'end': 692.088, 'text': 'And 1 would be pushed into the stack.', 'start': 688.666, 'duration': 3.422}, {'end': 694.309, 'text': 'After 0 where have we gone? 1.', 'start': 693.148, 'duration': 1.161}, {'end': 694.709, 'text': 'After that.', 'start': 694.309, 'duration': 0.4}, {'end': 729.237, 'text': "like BFS, you don't have to insert all four.", 'start': 726.994, 'duration': 2.243}, {'end': 735.025, 'text': 'you take any one of these four, three, two, five, four, six.', 'start': 729.237, 'duration': 5.788}, {'end': 740.573, 'text': 'suppose we have taken this three, fine three.', 'start': 735.025, 'duration': 5.548}], 'summary': 'Depth-first search explores vertices until a dead end, backtracking as needed.', 'duration': 94.502, 'max_score': 640.523, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/vf-cxgUXcMk/pics/vf-cxgUXcMk640523.jpg'}, {'end': 837.599, 'src': 'embed', 'start': 770.254, 'weight': 2, 'content': [{'end': 776.238, 'text': 'Which is the unvisited vertex? 2 and this 4.', 'start': 770.254, 'duration': 5.984}, {'end': 786.605, 'text': 'So you would take any one of these adjacent unvisited vertices and you would push that vertex into this stack.', 'start': 776.238, 'duration': 10.367}, {'end': 788.426, 'text': 'You can take 2 or 4.', 'start': 786.665, 'duration': 1.761}, {'end': 789.367, 'text': 'Suppose you have taken 2.', 'start': 788.426, 'duration': 0.941}, {'end': 796.672, 'text': 'You printed 2 and pushed 2 into this stack.', 'start': 789.367, 'duration': 7.305}, {'end': 801.328, 'text': 'Where did you go after 3? 2.', 'start': 796.852, 'duration': 4.476}, {'end': 803.951, 'text': 'Fine Now you are at this 2.', 'start': 801.328, 'duration': 2.623}, {'end': 807.354, 'text': 'Now find out adjacent vertices of this 2.', 'start': 803.951, 'duration': 3.403}, {'end': 810.497, 'text': 'Fine Which are its adjacent vertices? 1.', 'start': 807.354, 'duration': 3.143}, {'end': 814.461, 'text': 'But you cannot push 1 at this one because 1 is already visited.', 'start': 810.497, 'duration': 3.964}, {'end': 815.482, 'text': 'You cannot push 3.', 'start': 814.541, 'duration': 0.941}, {'end': 816.583, 'text': '3 is already visited.', 'start': 815.482, 'duration': 1.101}, {'end': 819.626, 'text': 'Now you still have adjacent vertices 5.', 'start': 817.344, 'duration': 2.282}, {'end': 821.568, 'text': 'You can push 5 in this.', 'start': 819.626, 'duration': 1.942}, {'end': 825.427, 'text': 'Fine And 1 is this 4.', 'start': 821.608, 'duration': 3.819}, {'end': 826.208, 'text': 'Adjacent vertex.', 'start': 825.427, 'duration': 0.781}, {'end': 829.651, 'text': 'Fine This 5 and 4.', 'start': 826.748, 'duration': 2.903}, {'end': 831.673, 'text': 'So you can take either 5 or either 4.', 'start': 829.651, 'duration': 2.022}, {'end': 832.053, 'text': 'Any one.', 'start': 831.673, 'duration': 0.38}, {'end': 834.696, 'text': "Okay You don't have to take all of them.", 'start': 832.074, 'duration': 2.622}, {'end': 836.218, 'text': 'I am focusing on this again and again.', 'start': 834.716, 'duration': 1.502}, {'end': 837.599, 'text': 'You have to choose any one.', 'start': 836.278, 'duration': 1.321}], 'summary': 'Traversing vertices, pushing into stack, and choosing adjacent unvisited vertices.', 'duration': 67.345, 'max_score': 770.254, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/vf-cxgUXcMk/pics/vf-cxgUXcMk770254.jpg'}, {'end': 931.759, 'src': 'embed', 'start': 904.47, 'weight': 5, 'content': [{'end': 913.321, 'text': "you know, further from the 6 deep you can't go after 6 because you do not have any unvisited adjacent vertices of 6 where you can go.", 'start': 904.47, 'duration': 8.851}, {'end': 915.744, 'text': 'so what will happen here?', 'start': 913.321, 'duration': 2.423}, {'end': 916.625, 'text': 'backtracking now.', 'start': 915.744, 'duration': 0.881}, {'end': 917.526, 'text': 'how will backtracking happen?', 'start': 916.625, 'duration': 0.901}, {'end': 919.288, 'text': 'where to go in backtracking?', 'start': 917.526, 'duration': 1.762}, {'end': 926.815, 'text': 'how will you know from this step, If such a situation comes, what happens there?', 'start': 919.288, 'duration': 7.527}, {'end': 928.477, 'text': 'That strap is there.', 'start': 927.176, 'duration': 1.301}, {'end': 931.759, 'text': 'The topmost element is deleted, popped out.', 'start': 929.057, 'duration': 2.702}], 'summary': 'Backtracking occurs when no unvisited adjacent vertices are available, leading to the deletion of the topmost element.', 'duration': 27.289, 'max_score': 904.47, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/vf-cxgUXcMk/pics/vf-cxgUXcMk904470.jpg'}], 'start': 608.249, 'title': 'Graph traversal and backtracking', 'summary': 'Covers the depth first search algorithm, emphasizing the process of visiting unvisited vertices and backtracking until a dead end, and the selection and pushing of adjacent vertices into the stack for further exploration. it also explains the process of graph traversal and backtracking, emphasizing the selection of unvisited adjacent vertices and the concept of backtracking when no further unvisited adjacent vertices are available.', 'chapters': [{'end': 810.497, 'start': 608.249, 'title': 'Depth first search algorithm', 'summary': 'Explains the depth first search algorithm, emphasizing the process of visiting unvisited vertices and backtracking until a dead end, and the selection and pushing of adjacent vertices into the stack for further exploration.', 'duration': 202.248, 'highlights': ['The process involves visiting unvisited vertices and backtracking until a dead end is reached. The algorithm emphasizes going deeper and deeper until a dead end is encountered, where the adjacent unvisited vertices are explored.', 'Selection and pushing of adjacent vertices into the stack for further exploration is a crucial step in the algorithm. Adjacent unvisited vertices are selected and pushed into the stack for further exploration, facilitating the traversal process.', 'The algorithm involves the selection of any one adjacent unvisited vertex for exploration and pushing it into the stack. When encountering adjacent unvisited vertices, the algorithm involves the selection of any one of them for exploration and then pushing it into the stack for further traversal.']}, {'end': 931.759, 'start': 810.497, 'title': 'Graph traversal and backtracking', 'summary': 'Explains the process of graph traversal and backtracking, emphasizing the selection of unvisited adjacent vertices and the concept of backtracking when no further unvisited adjacent vertices are available.', 'duration': 121.262, 'highlights': ['The importance of selecting unvisited adjacent vertices is emphasized, with the instruction to choose any one unvisited adjacent vertex, such as 4 or 5, in the graph traversal process.', 'The concept of backtracking is explained, illustrating the scenario where no unvisited adjacent vertices are available for further traversal, leading to the necessity of backtracking in the graph traversal process.', 'The process of backtracking is detailed, describing the deletion or popping out of the topmost element when backtracking is required in the graph traversal process.']}], 'duration': 323.51, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/vf-cxgUXcMk/pics/vf-cxgUXcMk608249.jpg', 'highlights': ['The process involves visiting unvisited vertices and backtracking until a dead end is reached.', 'Selection and pushing of adjacent vertices into the stack for further exploration is a crucial step in the algorithm.', 'The algorithm involves the selection of any one adjacent unvisited vertex for exploration and pushing it into the stack.', 'The importance of selecting unvisited adjacent vertices is emphasized, with the instruction to choose any one unvisited adjacent vertex.', 'The concept of backtracking is explained, illustrating the scenario where no unvisited adjacent vertices are available for further traversal.', 'The process of backtracking is detailed, describing the deletion or popping out of the topmost element when backtracking is required.']}, {'end': 1224.963, 'segs': [{'end': 1034.574, 'src': 'heatmap', 'start': 968.011, 'weight': 0, 'content': [{'end': 972.673, 'text': 'then 4 would be popped out from the stack.', 'start': 968.011, 'duration': 4.662}, {'end': 974.254, 'text': 'next element is 2.', 'start': 972.673, 'duration': 1.581}, {'end': 977.206, 'text': 'now we would go to two.', 'start': 974.254, 'duration': 2.952}, {'end': 978.987, 'text': 'backtrack to two.', 'start': 977.206, 'duration': 1.781}, {'end': 980.108, 'text': 'now find out.', 'start': 978.987, 'duration': 1.121}, {'end': 984.971, 'text': 'is there any adjacent vertices of two that is still unvisited?', 'start': 980.108, 'duration': 4.863}, {'end': 986.572, 'text': 'yes, we have.', 'start': 984.971, 'duration': 1.601}, {'end': 987.633, 'text': 'what is that this?', 'start': 986.572, 'duration': 1.061}, {'end': 993.216, 'text': 'five. this five is still unvisited and it is adjacent of this two.', 'start': 987.633, 'duration': 5.583}, {'end': 995.558, 'text': 'so you would go to this five.', 'start': 993.216, 'duration': 2.342}, {'end': 1001.942, 'text': 'five would be printed and five would be pushed into the stack.', 'start': 995.558, 'duration': 6.384}, {'end': 1005.412, 'text': 'fine, now check five.', 'start': 1001.942, 'duration': 3.47}, {'end': 1009.533, 'text': 'is there any adjacent vertices of five which is still unvisited?', 'start': 1005.412, 'duration': 4.121}, {'end': 1012.074, 'text': 'no one already visited.', 'start': 1009.533, 'duration': 2.541}, {'end': 1013.715, 'text': 'two already visited.', 'start': 1012.074, 'duration': 1.641}, {'end': 1015.856, 'text': 'what the next step is?', 'start': 1013.715, 'duration': 2.141}, {'end': 1017.837, 'text': 'we cannot go further from five.', 'start': 1015.856, 'duration': 1.981}, {'end': 1020.558, 'text': 'so backtrack.', 'start': 1017.837, 'duration': 2.721}, {'end': 1024.98, 'text': 'first step is five would be popped out from the stack.', 'start': 1020.558, 'duration': 4.422}, {'end': 1027.141, 'text': 'okay, the top element would be popped out.', 'start': 1024.98, 'duration': 2.161}, {'end': 1030.122, 'text': 'now check the next top element, that is two.', 'start': 1027.141, 'duration': 2.981}, {'end': 1034.574, 'text': 'then five, say, backtrack to the 2.', 'start': 1030.122, 'duration': 4.452}], 'summary': 'Traversing a graph using depth-first search, popping 4 and 5 from the stack.', 'duration': 66.563, 'max_score': 968.011, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/vf-cxgUXcMk/pics/vf-cxgUXcMk968011.jpg'}, {'end': 1189.498, 'src': 'embed', 'start': 1129.157, 'weight': 2, 'content': [{'end': 1135.438, 'text': 'first to one, but from zero you can go to this vertex.', 'start': 1129.157, 'duration': 6.281}, {'end': 1141.62, 'text': 'three also, okay, after that, if you visit, then this would be another dfs traversal.', 'start': 1135.438, 'duration': 6.182}, {'end': 1147.093, 'text': 'fine, so there can be many DFS traversals in this.', 'start': 1142.81, 'duration': 4.283}, {'end': 1149.814, 'text': 'so I have told you what will happen in BFS.', 'start': 1147.093, 'duration': 2.721}, {'end': 1161.121, 'text': 'I will try to explore all the nodes as close as possible to the root node means level order.', 'start': 1149.814, 'duration': 11.307}, {'end': 1164.583, 'text': 'all the adjacent nodes will be explored first.', 'start': 1161.121, 'duration': 3.462}, {'end': 1167.966, 'text': 'after that you will go further.', 'start': 1164.583, 'duration': 3.383}, {'end': 1169.727, 'text': 'fine, but what will happen in DFS?', 'start': 1167.966, 'duration': 1.761}, {'end': 1180.715, 'text': 'any one node would be visited from that root node and after that you will visit further from that node and after that further, further and further,', 'start': 1171.272, 'duration': 9.443}, {'end': 1189.498, 'text': "you will go deeper and when you will reach that dead end from where you don't have any unvisited adjacent vertices.", 'start': 1180.715, 'duration': 8.783}], 'summary': 'Dfs explores all nodes from root and goes deeper until dead end.', 'duration': 60.341, 'max_score': 1129.157, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/vf-cxgUXcMk/pics/vf-cxgUXcMk1129157.jpg'}], 'start': 931.84, 'title': 'Depth first search algorithm and traversal', 'summary': 'Explains the process of depth first search algorithm with a stack, visiting and pushing unvisited vertices, and backtracking to previously visited vertices. it also elaborates on the dfs traversal of a graph, highlighting the use of stack data structure, multiple valid dfs traversals, and the backtracking process when reaching a dead end.', 'chapters': [{'end': 1099.736, 'start': 931.84, 'title': 'Depth first search', 'summary': 'Explains the process of depth first search algorithm with a stack, visiting and pushing unvisited vertices, and backtracking to previously visited vertices.', 'duration': 167.896, 'highlights': ['The algorithm involves visiting vertices and pushing unvisited vertices into a stack, as shown with examples like pushing 6 and 5 into the stack.', 'Backtracking to previously visited vertices is essential, as illustrated by the process of backtracking from 5 to 2 and from 3 to 1.', 'The process also includes popping out vertices from the stack when there are no unvisited adjacent vertices, such as popping out 4, 2, and 3 from the stack.']}, {'end': 1224.963, 'start': 1099.736, 'title': 'Dfs traversal and stack data structure', 'summary': 'Explains the dfs traversal of a graph, highlighting that multiple valid dfs traversals exist, and the difference between dfs and bfs lies in the use of stack and queue data structures. it also emphasizes the backtracking process when reaching a dead end.', 'duration': 125.227, 'highlights': ['The DFS traversal of a graph can have multiple valid DFS traversals, as it depends on the order of visiting the vertices.', 'In BFS, all the adjacent nodes are explored first in a level order manner, while in DFS, the traversal goes deeper until reaching a dead end.', 'The backtracking process in DFS involves popping the top of the stack when reaching a dead end and then backtracking from the next top of the stack.']}], 'duration': 293.123, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/vf-cxgUXcMk/pics/vf-cxgUXcMk931840.jpg', 'highlights': ['The algorithm involves visiting and pushing unvisited vertices into a stack, e.g., pushing 6 and 5 into the stack.', 'Backtracking to previously visited vertices is essential, demonstrated by backtracking from 5 to 2 and from 3 to 1.', 'DFS traversal of a graph can have multiple valid traversals, depending on the order of visiting vertices.', 'In DFS, the traversal goes deeper until reaching a dead end, then backtracks from the next top of the stack.']}], 'highlights': ['The process involves visiting adjacent vertices as close as possible to the root vertex, ensuring that all such vertices are visited first.', 'The concept of multiple valid BFS traversals of the graph based on the order of insertion is explained, emphasizing the flexibility in finding numerous valid BFS traversals.', 'The process of DFS involves inserting the root node into the stack, printing it, and then traversing its adjacent vertices in a depth-first manner, inserting one adjacent vertex into the stack at a time.', 'The process involves visiting unvisited vertices and backtracking until a dead end is reached.', 'DFS traversal of a graph can have multiple valid traversals, depending on the order of visiting vertices.']}