title

6.3 Types of Edges in DFS | Edge Classification | Data Structures and Algorithms

description

In this video, I have explained the Classification of Edges (Tree edge, Forward Edge, Back Edge, Cross edge) in Depth-First Search Traversal in a Directed Graph.
Depth First Search Traversal:
https://www.youtube.com/watch?v=vf-cxgUXcMk
DSA Full Course: https: https://www.youtube.com/playlist?list=PLdo5W4Nhv31bbKJzrsKfMpo_grxuLl8LU
******************************************
See Complete 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/

detail

{'title': '6.3 Types of Edges in DFS | Edge Classification | Data Structures and Algorithms', 'heatmap': [{'end': 159.653, 'start': 137.58, 'weight': 1}, {'end': 964.065, 'start': 947.234, 'weight': 0.758}, {'end': 1077.555, 'start': 1038.935, 'weight': 0.702}, {'end': 1149.705, 'start': 1133.277, 'weight': 0.739}], 'summary': 'Covers dfs traversal process, time stamp, and the four types of edges including tree edge, forward edge, back edge, and cross edge, as well as their characteristics and an example. it also details the traversal and exploration of a graph with 13 nodes and 12 edges, tracking starting and finishing times of each node, and the backtracking process. additionally, it discusses traversal path, starting times of nodes in a network, available traversal choices, dfs traversal of a graph with 12 tree edges, and the classification of different types of edges including forward, back, and cross edges. furthermore, it explains the classification of edges in a graph based on direction and starting time of vertices, emphasizing back edges and cross edges with examples demonstrating the conditions for each type of edge, and delves into classifying graph edges as tree edges, forward edges, back edges, and cross edges, with specific examples and conditions for each type, including the union of all edges in the graph.', 'chapters': [{'end': 249.986, 'segs': [{'end': 53.287, 'src': 'embed', 'start': 24.995, 'weight': 0, 'content': [{'end': 29.278, 'text': 'third one is back edge and fourth one is cross edge.', 'start': 24.995, 'duration': 4.283}, {'end': 32.5, 'text': 'okay, now, These are four types of edges.', 'start': 29.278, 'duration': 3.222}, {'end': 41.983, 'text': 'Tree edge is what? When you traverse that graph or you can say when you are applying that DFS traversal, depth first search traversal.', 'start': 33, 'duration': 8.983}, {'end': 50.146, 'text': 'Okay Then the edges which are member of the DFS traversal, those edges would be tree edges.', 'start': 42.223, 'duration': 7.923}, {'end': 53.287, 'text': 'Okay Next is forward edge.', 'start': 50.906, 'duration': 2.381}], 'summary': 'Four types of edges in dfs traversal, including tree edges and forward edges.', 'duration': 28.292, 'max_score': 24.995, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/wm6qRWGjvkA/pics/wm6qRWGjvkA24995.jpg'}, {'end': 198.071, 'src': 'heatmap', 'start': 137.58, 'weight': 1, 'content': [{'end': 143.863, 'text': 'y appears before x and there is a path from y to x.', 'start': 137.58, 'duration': 6.283}, {'end': 145.665, 'text': 'and what is the cross edge?', 'start': 143.863, 'duration': 1.802}, {'end': 149.108, 'text': 'any edge from x to y would be a cross edge.', 'start': 145.665, 'duration': 3.443}, {'end': 154.252, 'text': 'where there is no path from y to x, you cannot come from y to x.', 'start': 149.108, 'duration': 5.144}, {'end': 159.653, 'text': 'okay, so let us discuss these type of edges with the help of this example.', 'start': 154.992, 'duration': 4.661}, {'end': 161.714, 'text': 'then it will be laid out.', 'start': 159.653, 'duration': 2.061}, {'end': 166.635, 'text': 'see, suppose this one is our example and we are applying dfs traversal on this graph.', 'start': 161.714, 'duration': 4.921}, {'end': 174.138, 'text': 'first of all, okay, we will consider one variable, that is time variable.', 'start': 166.635, 'duration': 7.503}, {'end': 176.218, 'text': 'okay, we will start.', 'start': 174.138, 'duration': 2.08}, {'end': 178.359, 'text': 'you can start the dfs traversal from any node.', 'start': 176.218, 'duration': 2.141}, {'end': 182.9, 'text': 'fine, we are taking this node A as a starting node.', 'start': 179.138, 'duration': 3.762}, {'end': 186.441, 'text': 'we are starting our DFS traversal from this node.', 'start': 182.9, 'duration': 3.541}, {'end': 192.584, 'text': 'okay, now, first of all, go to this node A and note the time.', 'start': 186.441, 'duration': 6.143}, {'end': 195.95, 'text': 'time starting will be 1.', 'start': 192.584, 'duration': 3.366}, {'end': 198.071, 'text': 'you can say the starting time of this node.', 'start': 195.95, 'duration': 2.121}], 'summary': 'Dfs traversal example with time variable, starting at node a.', 'duration': 60.491, 'max_score': 137.58, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/wm6qRWGjvkA/pics/wm6qRWGjvkA137580.jpg'}], 'start': 0.816, 'title': 'Dfs traversal and edge types', 'summary': 'Discusses dfs traversal process, time stamp, and the four types of edges including tree edge, forward edge, back edge, and cross edge, as well as their characteristics and an example.', 'chapters': [{'end': 106.687, 'start': 0.816, 'title': 'Types of edges after dfs traversal', 'summary': 'Discusses the four types of edges after dfs traversal of a graph, including tree edge, forward edge, back edge, and cross edge, and explains their definitions and characteristics.', 'duration': 105.871, 'highlights': ['The four types of edges after DFS traversal are tree edge, forward edge, back edge, and cross edge.', 'Tree edge is defined as the edges which are part of the DFS traversal.', 'Forward edge is characterized by the edge from node x to node y where y appears after x in the graph.']}, {'end': 166.635, 'start': 106.687, 'title': 'Types of edges in graphs', 'summary': 'Explains the concept of forward, back, and cross edges in a directed graph, defining their characteristics and illustrating with an example.', 'duration': 59.948, 'highlights': ['A forward edge in a directed graph is from x to y where y appears after x and there is a path from x to y.', 'A back edge in a directed graph is from x to y where y appears before x and there is a path from y to x.', 'A cross edge in a directed graph is from x to y where there is no path from y to x, illustrating with an example graph and DFS traversal.']}, {'end': 249.986, 'start': 166.635, 'title': 'Dfs traversal explained', 'summary': 'Explains the process of dfs traversal, starting from node a with a time stamp of 1, discussing the concept of time variable and the multiple possible dfs traversals of the graph.', 'duration': 83.351, 'highlights': ['The starting time of the DFS traversal at node A is 1, and as the traversal progresses, the time increases by one.', 'The concept of time variable is introduced, and it is associated with different terms such as appearing time, discovering time, and time stamp.', 'The chapter emphasizes the possibility of multiple DFS traversals for the graph and directs viewers to a previous video discussing the DFS traversal method.']}], 'duration': 249.17, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/wm6qRWGjvkA/pics/wm6qRWGjvkA816.jpg', 'highlights': ['The four types of edges after DFS traversal are tree edge, forward edge, back edge, and cross edge.', 'The starting time of the DFS traversal at node A is 1, and as the traversal progresses, the time increases by one.', 'A cross edge in a directed graph is from x to y where there is no path from y to x, illustrating with an example graph and DFS traversal.']}, {'end': 610.163, 'segs': [{'end': 406.721, 'src': 'embed', 'start': 373.329, 'weight': 2, 'content': [{'end': 378.295, 'text': 'so you can say the finishing time of this e is what five.', 'start': 373.329, 'duration': 4.966}, {'end': 381.911, 'text': 'Time will increase by 1.', 'start': 379.67, 'duration': 2.241}, {'end': 392.297, 'text': 'Finishing time will increase when you are not able to move forward from that node and you have to backtrack from that node.', 'start': 381.911, 'duration': 10.386}, {'end': 394.118, 'text': 'The finishing time of this is what?', 'start': 392.297, 'duration': 1.821}, {'end': 395.458, 'text': '5. Now we have to backtrack.', 'start': 394.138, 'duration': 1.32}, {'end': 398.02, 'text': 'we have reached back to C.', 'start': 395.458, 'duration': 2.562}, {'end': 400.001, 'text': 'Now can you go anywhere from C?', 'start': 398.02, 'duration': 1.981}, {'end': 403.078, 'text': 'Yes, we can go to this way, Fine,', 'start': 400.301, 'duration': 2.777}, {'end': 406.721, 'text': 'So we can mark this agent.', 'start': 403.739, 'duration': 2.982}], 'summary': 'The finishing time of the task is 5, with 1 time increase and successful backtracking to node c.', 'duration': 33.392, 'max_score': 373.329, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/wm6qRWGjvkA/pics/wm6qRWGjvkA373329.jpg'}, {'end': 610.163, 'src': 'embed', 'start': 519.53, 'weight': 0, 'content': [{'end': 524.913, 'text': 'still we have some node that are yet to be traversed.', 'start': 519.53, 'duration': 5.383}, {'end': 528.033, 'text': 'okay, now we will go to this side b.', 'start': 524.913, 'duration': 3.12}, {'end': 530.414, 'text': 'we will mark this edge.', 'start': 528.033, 'duration': 2.381}, {'end': 533.805, 'text': 'right now we have reached to f.', 'start': 531.203, 'duration': 2.602}, {'end': 535.946, 'text': 'what is the starting time of this f?', 'start': 533.805, 'duration': 2.141}, {'end': 538.668, 'text': 'now, 9 to 10.', 'start': 535.946, 'duration': 2.722}, {'end': 539.128, 'text': 'it has.', 'start': 538.668, 'duration': 0.46}, {'end': 540.549, 'text': 'it is now 10.', 'start': 539.128, 'duration': 1.421}, {'end': 542.391, 'text': 'starting time of f.', 'start': 540.549, 'duration': 1.842}, {'end': 549.395, 'text': 'now. next, where we can go to, we can go to g, and we will mark this edge.', 'start': 542.391, 'duration': 7.004}, {'end': 551.997, 'text': 'we have reached to this g.', 'start': 549.395, 'duration': 2.602}, {'end': 555.119, 'text': 'starting time of g would be now 11.', 'start': 551.997, 'duration': 3.122}, {'end': 562.309, 'text': 'now, from g, where you can go, you can go either to l, to h or to M.', 'start': 555.119, 'duration': 7.19}, {'end': 563.37, 'text': 'you have three options.', 'start': 562.309, 'duration': 1.061}, {'end': 565.572, 'text': 'you can go to any node.', 'start': 563.37, 'duration': 2.202}, {'end': 567.674, 'text': 'suppose we are traversing this node.', 'start': 565.572, 'duration': 2.102}, {'end': 569.356, 'text': 'L. we are going to L now.', 'start': 567.674, 'duration': 1.682}, {'end': 571.177, 'text': 'what is the starting time of L?', 'start': 569.356, 'duration': 1.821}, {'end': 572.719, 'text': 'we have marked this edge.', 'start': 571.177, 'duration': 1.542}, {'end': 576.823, 'text': 'starting time of L would be 12 now because it was 11.', 'start': 572.719, 'duration': 4.104}, {'end': 578.404, 'text': 'now one increase will happen.', 'start': 576.823, 'duration': 1.581}, {'end': 580.406, 'text': 'that would be 12 now.', 'start': 578.404, 'duration': 2.002}, {'end': 581.967, 'text': 'now, from L where you can go.', 'start': 580.406, 'duration': 1.561}, {'end': 585.286, 'text': 'We cannot go anywhere because there is no outgoing edge.', 'start': 582.884, 'duration': 2.402}, {'end': 587.248, 'text': 'So, this has been finished.', 'start': 585.847, 'duration': 1.401}, {'end': 592.312, 'text': 'Traversing of or exploring of this node has been finished because we cannot go anywhere forward.', 'start': 587.508, 'duration': 4.804}, {'end': 597.096, 'text': 'So, we have to backtrack.', 'start': 593.353, 'duration': 3.743}, {'end': 600.679, 'text': 'And before backtracking, we will write down the finishing time of the cell.', 'start': 597.116, 'duration': 3.563}, {'end': 604.303, 'text': 'Finishing time would be what? 13.', 'start': 600.739, 'duration': 3.564}, {'end': 606.221, 'text': 'Now, backtrack to 13.', 'start': 604.303, 'duration': 1.918}, {'end': 607.742, 'text': 'g from g.', 'start': 606.221, 'duration': 1.521}, {'end': 610.163, 'text': 'where is there any node where you can go?', 'start': 607.742, 'duration': 2.421}], 'summary': 'Traversing nodes with timestamps, reaching node l at time 12, finishing at time 13.', 'duration': 90.633, 'max_score': 519.53, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/wm6qRWGjvkA/pics/wm6qRWGjvkA519530.jpg'}], 'start': 249.986, 'title': 'Graph traversal and exploration', 'summary': 'Details the traversal and exploration of a graph, involving 13 nodes and 12 edges, tracking starting and finishing times of each node, and the backtracking process.', 'chapters': [{'end': 406.721, 'start': 249.986, 'title': 'Depth first search traversal', 'summary': 'Discusses the depth first search traversal algorithm, tracking the starting and finishing times of nodes, with an example traversal from node b to node e, marking the edges and backtracking, resulting in the finishing time of node e being 5.', 'duration': 156.735, 'highlights': ['The finishing time of node E is 5, which is determined by the algorithm when the node cannot move forward and requires backtracking.', 'The starting time of node E is 4, which is incremented by 1 during the traversal.', 'The starting time of node C is 3, indicating the order in which the nodes are discovered during the traversal.', 'The starting time of node B is 2, marking the time at which the node is discovered in the traversal.']}, {'end': 610.163, 'start': 406.781, 'title': 'Graph traversal and exploration', 'summary': 'Details the traversal and exploration of a graph, with the starting and finishing times of each node, as well as the backtracking process, involving a total of 13 nodes and 12 edges.', 'duration': 203.382, 'highlights': ["The finishing time of the last node 'g' is 13, marking the conclusion of the traversal process.", "The starting time of node 'f' is 10, with the subsequent traversal to node 'g' starting at time 11.", "The starting time of node 'D' is 5, followed by the traversal to node 'B' with a finishing time of 9."]}], 'duration': 360.177, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/wm6qRWGjvkA/pics/wm6qRWGjvkA249986.jpg', 'highlights': ["The finishing time of the last node 'g' is 13, marking the conclusion of the traversal process.", "The starting time of node 'f' is 10, with the subsequent traversal to node 'g' starting at time 11.", 'The finishing time of node E is 5, which is determined by the algorithm when the node cannot move forward and requires backtracking.', 'The starting time of node E is 4, which is incremented by 1 during the traversal.']}, {'end': 957.821, 'segs': [{'end': 670.519, 'src': 'embed', 'start': 610.163, 'weight': 0, 'content': [{'end': 613.424, 'text': 'yes, we can go to h, or you can go to m.', 'start': 610.163, 'duration': 3.261}, {'end': 615.785, 'text': 'we have still two choices now.', 'start': 613.424, 'duration': 2.361}, {'end': 621.088, 'text': 'suppose we are going to this h and we will mark this edge.', 'start': 615.785, 'duration': 5.303}, {'end': 623.489, 'text': 'now we are going to this h.', 'start': 621.088, 'duration': 2.401}, {'end': 625.13, 'text': 'what is the starting time of h?', 'start': 623.489, 'duration': 1.641}, {'end': 631.057, 'text': 'that would be 14, because that time reached to 13.', 'start': 625.13, 'duration': 5.927}, {'end': 632.699, 'text': 'now. next is 14.', 'start': 631.057, 'duration': 1.642}, {'end': 636.702, 'text': 'now from H, where you can go, you can go either to K or either to I.', 'start': 632.699, 'duration': 4.003}, {'end': 637.663, 'text': 'you have two choices.', 'start': 636.702, 'duration': 0.961}, {'end': 639.985, 'text': 'suppose we are taking this route.', 'start': 637.663, 'duration': 2.322}, {'end': 641.726, 'text': 'we are traversing this I.', 'start': 639.985, 'duration': 1.741}, {'end': 643.188, 'text': 'what is the starting time of I?', 'start': 641.726, 'duration': 1.462}, {'end': 645.95, 'text': 'now? that would be 15.', 'start': 643.188, 'duration': 2.762}, {'end': 654.137, 'text': 'from I, where you can go, you can go to J only, or you can say you can traverse this J only.', 'start': 645.95, 'duration': 8.187}, {'end': 658.409, 'text': 'so Mark this edge and we are going to J.', 'start': 654.137, 'duration': 4.272}, {'end': 662.612, 'text': 'What is the starting time of this J now? That would be 16.', 'start': 658.409, 'duration': 4.203}, {'end': 666.996, 'text': 'Okay Now from J we are at this node J.', 'start': 662.612, 'duration': 4.384}, {'end': 667.797, 'text': 'You can go anywhere.', 'start': 666.996, 'duration': 0.801}, {'end': 670.519, 'text': "Can you go anywhere? No, we don't have any other choice.", 'start': 667.817, 'duration': 2.702}], 'summary': 'Traversing nodes h, i, j with starting times 14, 15, 16 respectively.', 'duration': 60.356, 'max_score': 610.163, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/wm6qRWGjvkA/pics/wm6qRWGjvkA610163.jpg'}, {'end': 957.821, 'src': 'embed', 'start': 883.693, 'weight': 3, 'content': [{'end': 886.555, 'text': 'See first of all what is tree edge?', 'start': 883.693, 'duration': 2.862}, {'end': 889.957, 'text': 'All the edges which you have marked.', 'start': 887.996, 'duration': 1.961}, {'end': 894.48, 'text': 'the edges which are member of DFS traversal during the DFS traversal.', 'start': 889.957, 'duration': 4.523}, {'end': 898.463, 'text': 'all the edges which you have visited.', 'start': 894.48, 'duration': 3.983}, {'end': 899.744, 'text': 'we have marked them here.', 'start': 898.463, 'duration': 1.281}, {'end': 902.586, 'text': 'Those edges would be tree edges.', 'start': 900.364, 'duration': 2.222}, {'end': 913.081, 'text': 'okay, and out of remaining edges, you have to find out which one is forward edge, which one is back edge and which one is cross edge.', 'start': 903.55, 'duration': 9.531}, {'end': 924.416, 'text': "okay, so I'm just writing the tree edges, tree edges, The edges which are member of DFS, traversal.", 'start': 913.081, 'duration': 11.335}, {'end': 940.904, 'text': 'how many edges are there? This one AB, BC, CE, CD, AF, FG, GL, GH, HI, IJ, HK and KM.', 'start': 924.416, 'duration': 16.488}, {'end': 944.412, 'text': 'these are 12 tree edges.', 'start': 941.61, 'duration': 2.802}, {'end': 947.234, 'text': 'now, what are remaining edges?', 'start': 944.412, 'duration': 2.822}, {'end': 952.657, 'text': 'and the edges which are, you know, in this red ink?', 'start': 947.234, 'duration': 5.423}, {'end': 955.76, 'text': 'those are not under the tree edges.', 'start': 952.657, 'duration': 3.103}, {'end': 957.821, 'text': 'those are still left.', 'start': 955.76, 'duration': 2.061}], 'summary': 'Identified 12 tree edges, categorized remaining edges', 'duration': 74.128, 'max_score': 883.693, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/wm6qRWGjvkA/pics/wm6qRWGjvkA883693.jpg'}], 'start': 610.163, 'title': 'Traversal path and dfs', 'summary': 'Discusses the traversal path and starting times of nodes in a network, along with specific starting times for each node and available traversal choices. it also covers dfs traversal of a graph with a total of 12 tree edges and explains the classification of different types of edges including forward, back, and cross edges.', 'chapters': [{'end': 670.519, 'start': 610.163, 'title': 'Traversal path and starting time', 'summary': 'Discusses the traversal path and starting times of nodes in a network, with specific starting times for each node and available traversal choices.', 'duration': 60.356, 'highlights': ['Starting time of J is 16, and there are no further traversal choices from J.', 'Starting time of I is 15, and the only available traversal choice from I is J.', 'Starting time of H is 14, with traversal choices to either K or I.']}, {'end': 957.821, 'start': 670.539, 'title': 'Dfs traversal and edge classification', 'summary': 'Discusses the dfs traversal of a graph with a total of 12 tree edges and explains the classification of different types of edges including forward, back, and cross edges.', 'duration': 287.282, 'highlights': ['The chapter discusses the DFS traversal of a graph with a total of 12 tree edges. 12 tree edges', 'Explains the classification of different types of edges including forward, back, and cross edges. ']}], 'duration': 347.658, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/wm6qRWGjvkA/pics/wm6qRWGjvkA610163.jpg', 'highlights': ['Starting time of J is 16, and there are no further traversal choices from J.', 'Starting time of I is 15, and the only available traversal choice from I is J.', 'Starting time of H is 14, with traversal choices to either K or I.', 'The chapter discusses the DFS traversal of a graph with a total of 12 tree edges.', 'Explains the classification of different types of edges including forward, back, and cross edges.']}, {'end': 1277.538, 'segs': [{'end': 991.524, 'src': 'embed', 'start': 957.821, 'weight': 1, 'content': [{'end': 964.065, 'text': 'and out of these edges, you have to find out which one is forward, which one is back edge and which one is cross edge.', 'start': 957.821, 'duration': 6.244}, {'end': 965.086, 'text': 'let us take example.', 'start': 964.065, 'duration': 1.021}, {'end': 968.751, 'text': 'Let us take we are just taking this edge.', 'start': 966.089, 'duration': 2.662}, {'end': 971.052, 'text': 'D to B.', 'start': 969.091, 'duration': 1.961}, {'end': 974.414, 'text': 'Now this one is backward edge or forward edge or cross edge.', 'start': 971.052, 'duration': 3.362}, {'end': 975.675, 'text': 'You have to find it out.', 'start': 974.674, 'duration': 1.001}, {'end': 978.176, 'text': 'D, E.', 'start': 976.815, 'duration': 1.361}, {'end': 979.277, 'text': 'See directed edge is there.', 'start': 978.176, 'duration': 1.101}, {'end': 982.259, 'text': 'So arrow is from D to E.', 'start': 979.297, 'duration': 2.962}, {'end': 984.22, 'text': 'Now here how you will find out.', 'start': 982.259, 'duration': 1.961}, {'end': 991.524, 'text': 'Edge is D, B.', 'start': 986.501, 'duration': 5.023}], 'summary': 'Identify forward, back, and cross edges in a graph', 'duration': 33.703, 'max_score': 957.821, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/wm6qRWGjvkA/pics/wm6qRWGjvkA957821.jpg'}, {'end': 1087.641, 'src': 'heatmap', 'start': 1038.935, 'weight': 2, 'content': [{'end': 1049.84, 'text': 'Fine It means y appears before x.', 'start': 1038.935, 'duration': 10.905}, {'end': 1054.002, 'text': 'And the second condition is what? There is a path from y to x.', 'start': 1049.84, 'duration': 4.162}, {'end': 1055.802, 'text': 'Now here y is what? B.', 'start': 1054.002, 'duration': 1.8}, {'end': 1058.824, 'text': 'Is there any path from this B to D? Yes.', 'start': 1055.802, 'duration': 3.022}, {'end': 1062.385, 'text': 'You can go from B to C then C to D.', 'start': 1058.904, 'duration': 3.481}, {'end': 1065.888, 'text': 'There is a path from here to here.', 'start': 1063.186, 'duration': 2.702}, {'end': 1068.129, 'text': 'From y to x.', 'start': 1066.548, 'duration': 1.581}, {'end': 1071.531, 'text': 'So this edge is what? Back edge.', 'start': 1068.129, 'duration': 3.402}, {'end': 1077.555, 'text': 'Fine This would be what? Back edge.', 'start': 1072.852, 'duration': 4.703}, {'end': 1087.641, 'text': 'This db.', 'start': 1086.92, 'duration': 0.721}], 'summary': 'Y appears before x with a path from b to d via c, forming back edges.', 'duration': 58.984, 'max_score': 1038.935, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/wm6qRWGjvkA/pics/wm6qRWGjvkA1038935.jpg'}, {'end': 1159.282, 'src': 'heatmap', 'start': 1133.277, 'weight': 4, 'content': [{'end': 1135.599, 'text': 'here y is what e.', 'start': 1133.277, 'duration': 2.322}, {'end': 1138.98, 'text': 'is there any path from e to b?', 'start': 1135.599, 'duration': 3.381}, {'end': 1140.441, 'text': 'sorry, e to d?', 'start': 1138.98, 'duration': 1.461}, {'end': 1143.042, 'text': 'no, we cannot go from e to d.', 'start': 1140.441, 'duration': 2.601}, {'end': 1144.363, 'text': 'there is no path.', 'start': 1143.042, 'duration': 1.321}, {'end': 1145.363, 'text': 'so you cannot say this.', 'start': 1144.363, 'duration': 1}, {'end': 1146.864, 'text': 'one is back edge.', 'start': 1145.363, 'duration': 1.501}, {'end': 1149.705, 'text': 'this one is what cross edge see.', 'start': 1146.864, 'duration': 2.841}, {'end': 1152.627, 'text': 'cross edge edge would be x to y.', 'start': 1149.705, 'duration': 2.922}, {'end': 1159.282, 'text': 'where there is no path from y to x, You cannot move from Y to X.', 'start': 1152.627, 'duration': 6.655}], 'summary': 'There is no path from e to d, including a cross edge from x to y.', 'duration': 31.227, 'max_score': 1133.277, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/wm6qRWGjvkA/pics/wm6qRWGjvkA1133277.jpg'}, {'end': 1243.426, 'src': 'embed', 'start': 1204.425, 'weight': 0, 'content': [{'end': 1206.686, 'text': 'there is a path from Y to X.', 'start': 1204.425, 'duration': 2.261}, {'end': 1209.939, 'text': 'Now, here, Y is what? F.', 'start': 1207.577, 'duration': 2.362}, {'end': 1211.9, 'text': 'Is there any path from F to H? Yes.', 'start': 1209.939, 'duration': 1.961}, {'end': 1215.442, 'text': 'You can go F to G then G to H.', 'start': 1211.96, 'duration': 3.482}, {'end': 1216.963, 'text': 'Both condition has been satisfied.', 'start': 1215.442, 'duration': 1.521}, {'end': 1222.367, 'text': 'So this one is what? Back edge.', 'start': 1217.444, 'duration': 4.923}, {'end': 1225.289, 'text': 'This one is also back edge.', 'start': 1222.727, 'duration': 2.562}, {'end': 1226.73, 'text': 'Okay Let us take this one.', 'start': 1225.709, 'duration': 1.021}, {'end': 1229.512, 'text': 'G to M.', 'start': 1227.451, 'duration': 2.061}, {'end': 1232.374, 'text': 'Okay G to M.', 'start': 1229.512, 'duration': 2.862}, {'end': 1243.426, 'text': 'edge is from G to M direct edge so X would be what G and Y would be here M Find out which appears first.', 'start': 1233.692, 'duration': 9.734}], 'summary': 'Multiple back edges found in the path from y to x, satisfying both conditions. g to m creates a direct edge.', 'duration': 39.001, 'max_score': 1204.425, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/wm6qRWGjvkA/pics/wm6qRWGjvkA1204425.jpg'}], 'start': 957.821, 'title': 'Edge classification in graph theory', 'summary': 'Explains the classification of edges in a graph based on direction and starting time of vertices, using examples to illustrate the process. it emphasizes back edges and cross edges, with examples demonstrating the conditions for each type of edge.', 'chapters': [{'end': 1126.073, 'start': 957.821, 'title': 'Edge classification in graph theory', 'summary': 'Explains how to classify edges in a graph as forward, back, or cross edges based on the direction and starting time of the vertices, using examples of edge db and de to illustrate the classification process.', 'duration': 168.252, 'highlights': ['The edge DB is classified as a back edge because the starting time of vertex B is less than that of vertex D, and there is a path from B to D, with starting times of 2 for B and 6 for D.', 'The edge DE is determined to be a forward edge as the starting time of vertex E is less than that of vertex D, indicating that E appears before D, meeting the conditions for a forward edge classification.']}, {'end': 1277.538, 'start': 1128.055, 'title': 'Edge classification in graph theory', 'summary': 'Explains the classification of edges in a graph, emphasizing back edges and cross edges, with examples demonstrating the conditions for each type of edge, such as the presence of a path between the vertices and the order of their appearance.', 'duration': 149.483, 'highlights': ['The edge from G to M is classified as a direct edge, with G as the starting vertex and M as the ending vertex, satisfying the condition where X appears before Y and there is a path from X to Y.', 'The edge from H to F is identified as a back edge, with the condition that Y appears before X and there is a path from Y to X being met, as demonstrated by the presence of a path from F to H.', 'The classification of the edge from Y to X as a cross edge is explained, highlighting the absence of a path from Y to X, leading to the conclusion that it is a cross edge, emphasizing the importance of checking the second condition as well.']}], 'duration': 319.717, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/wm6qRWGjvkA/pics/wm6qRWGjvkA957821.jpg', 'highlights': ['The edge from G to M is classified as a direct edge, with G as the starting vertex and M as the ending vertex, satisfying the condition where X appears before Y and there is a path from X to Y.', 'The edge DE is determined to be a forward edge as the starting time of vertex E is less than that of vertex D, indicating that E appears before D, meeting the conditions for a forward edge classification.', 'The edge DB is classified as a back edge because the starting time of vertex B is less than that of vertex D, and there is a path from B to D, with starting times of 2 for B and 6 for D.', 'The edge from H to F is identified as a back edge, with the condition that Y appears before X and there is a path from Y to X being met, as demonstrated by the presence of a path from F to H.', 'The classification of the edge from Y to X as a cross edge is explained, highlighting the absence of a path from Y to X, leading to the conclusion that it is a cross edge, emphasizing the importance of checking the second condition as well.']}, {'end': 1551.705, 'segs': [{'end': 1551.705, 'src': 'embed', 'start': 1479.73, 'weight': 0, 'content': [{'end': 1486.432, 'text': 'back edges would be db, hf and mh, and cross edge would be de, kl, mi and id.', 'start': 1479.73, 'duration': 6.702}, {'end': 1489.113, 'text': 'see this is also remaining k to l.', 'start': 1486.432, 'duration': 2.681}, {'end': 1490.153, 'text': 'this one is also remaining.', 'start': 1489.113, 'duration': 1.04}, {'end': 1493.654, 'text': 'this is not under the tree edge from k to l.', 'start': 1490.153, 'duration': 3.501}, {'end': 1494.294, 'text': 'x is k.', 'start': 1493.654, 'duration': 0.64}, {'end': 1497.935, 'text': 'this one is y and here what is appearing.', 'start': 1494.294, 'duration': 3.641}, {'end': 1499.056, 'text': 'time of x is 19.', 'start': 1497.935, 'duration': 1.121}, {'end': 1501.376, 'text': 'appearing time of y is what to l.', 'start': 1499.056, 'duration': 2.32}, {'end': 1505.779, 'text': 'it means y appears Before X.', 'start': 1501.376, 'duration': 4.403}, {'end': 1507.08, 'text': 'Y appears before X.', 'start': 1505.779, 'duration': 1.301}, {'end': 1508.24, 'text': 'You have to check second condition.', 'start': 1507.08, 'duration': 1.16}, {'end': 1510.762, 'text': 'Is there any path from Y to X? Means L to K.', 'start': 1508.3, 'duration': 2.462}, {'end': 1512.463, 'text': 'Can you go from L to K? No.', 'start': 1510.762, 'duration': 1.701}, {'end': 1513.944, 'text': 'We cannot go from L to K.', 'start': 1512.483, 'duration': 1.461}, {'end': 1516.366, 'text': 'That is why it is known as what? Cross edge.', 'start': 1513.944, 'duration': 2.422}, {'end': 1520.028, 'text': 'Fine So this is the list of edges.', 'start': 1517.046, 'duration': 2.982}, {'end': 1530.175, 'text': 'And the one more condition is what? Union of all the four type of edges would be what? All the edges in the graph.', 'start': 1520.368, 'duration': 9.807}, {'end': 1536.487, 'text': 'Okay If you do the union of tree edges, forward edge, back edge and cross edge.', 'start': 1530.195, 'duration': 6.292}, {'end': 1545.337, 'text': 'If you do the union of all these, then you will get the total number of edges which are there in this graph.', 'start': 1537.208, 'duration': 8.129}, {'end': 1547.78, 'text': 'Fine You can check out this.', 'start': 1546.138, 'duration': 1.642}, {'end': 1550.623, 'text': 'Okay So, I will see you in the next video.', 'start': 1548.321, 'duration': 2.302}, {'end': 1551.264, 'text': 'Till then bye bye.', 'start': 1550.663, 'duration': 0.601}, {'end': 1551.705, 'text': 'Take care.', 'start': 1551.344, 'duration': 0.361}], 'summary': 'Graph analysis: 3 back edges, 4 cross edges, and edge conditions explained.', 'duration': 71.975, 'max_score': 1479.73, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/wm6qRWGjvkA/pics/wm6qRWGjvkA1479730.jpg'}], 'start': 1277.538, 'title': 'Graph edges classification', 'summary': 'Delves into classifying graph edges as tree edges, forward edges, back edges, and cross edges, with specific examples and conditions for each type, including the union of all edges in the graph.', 'chapters': [{'end': 1551.705, 'start': 1277.538, 'title': 'Graph edges classification', 'summary': 'Explains the classification of graph edges into tree edges, forward edges, back edges, and cross edges, identifying specific examples and conditions for each type of edge, with a mention of the union of all edges in the graph.', 'duration': 274.167, 'highlights': ['The classification of graph edges includes tree edges, forward edges, back edges, and cross edges, with specific examples provided for each type of edge. The chapter explains the classification of graph edges into tree edges, forward edges, back edges, and cross edges, with specific examples and conditions for each type of edge.', 'Identification of specific examples and conditions for each type of edge, such as forward edge (G to M), back edges (DB, HF, MH), and cross edges (DE, KL, MI, ID). Specific examples and conditions for each type of edge are identified, such as forward edge (G to M), back edges (DB, HF, MH), and cross edges (DE, KL, MI, ID).', 'Emphasis on the union of all types of edges to obtain the total number of edges in the graph. The chapter emphasizes the union of tree edges, forward edges, back edges, and cross edges to obtain the total number of edges in the graph.']}], 'duration': 274.167, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/wm6qRWGjvkA/pics/wm6qRWGjvkA1277538.jpg', 'highlights': ['The classification of graph edges includes tree edges, forward edges, back edges, and cross edges, with specific examples provided for each type of edge.', 'Identification of specific examples and conditions for each type of edge, such as forward edge (G to M), back edges (DB, HF, MH), and cross edges (DE, KL, MI, ID).', 'Emphasis on the union of all types of edges to obtain the total number of edges in the graph.']}], 'highlights': ['The four types of edges after DFS traversal are tree edge, forward edge, back edge, and cross edge.', 'The starting time of the DFS traversal at node A is 1, and as the traversal progresses, the time increases by one.', 'A cross edge in a directed graph is from x to y where there is no path from y to x, illustrating with an example graph and DFS traversal.', "The finishing time of the last node 'g' is 13, marking the conclusion of the traversal process.", "The starting time of node 'f' is 10, with the subsequent traversal to node 'g' starting at time 11.", 'The finishing time of node E is 5, which is determined by the algorithm when the node cannot move forward and requires backtracking.', 'The starting time of node E is 4, which is incremented by 1 during the traversal.', 'Starting time of J is 16, and there are no further traversal choices from J.', 'Starting time of I is 15, and the only available traversal choice from I is J.', 'Starting time of H is 14, with traversal choices to either K or I.', 'The chapter discusses the DFS traversal of a graph with a total of 12 tree edges.', 'Explains the classification of different types of edges including forward, back, and cross edges.', 'The edge from G to M is classified as a direct edge, with G as the starting vertex and M as the ending vertex, satisfying the condition where X appears before Y and there is a path from X to Y.', 'The edge DE is determined to be a forward edge as the starting time of vertex E is less than that of vertex D, indicating that E appears before D, meeting the conditions for a forward edge classification.', 'The edge DB is classified as a back edge because the starting time of vertex B is less than that of vertex D, and there is a path from B to D, with starting times of 2 for B and 6 for D.', 'The edge from H to F is identified as a back edge, with the condition that Y appears before X and there is a path from Y to X being met, as demonstrated by the presence of a path from F to H.', 'The classification of the edge from Y to X as a cross edge is explained, highlighting the absence of a path from Y to X, leading to the conclusion that it is a cross edge, emphasizing the importance of checking the second condition as well.', 'The classification of graph edges includes tree edges, forward edges, back edges, and cross edges, with specific examples provided for each type of edge.', 'Identification of specific examples and conditions for each type of edge, such as forward edge (G to M), back edges (DB, HF, MH), and cross edges (DE, KL, MI, ID).', 'Emphasis on the union of all types of edges to obtain the total number of edges in the graph.']}