title
Coding Challenge #68: Breadth-First Search Part 1

description
In this two part challenge, I implement the Breadth-First Search algorithm in JavaScript. My demo application is "6 Degrees of Kevin Bacon" (finding the closest relationship between Kevin Bacon and another actor). Code: https://thecodingtrain.com/challenges/68-breadth-first-search 🕹️ p5.js Web Editor Sketch: https://editor.p5js.org/codingtrain/sketches/0_6EV76Qy Other Parts of this Challenge: 📺 Breadth-First Search Part 2: https://youtu.be/-he67EEM6z0 🎥 Previous video: https://youtu.be/IIrC5Qcb2G4?list=PLRqwX-V7Uu6ZiZxtDDRCi6uhfTH4FilpH 🎥 Next video: https://youtu.be/flxOkx0yLrY?list=PLRqwX-V7Uu6ZiZxtDDRCi6uhfTH4FilpH 🎥 All videos: https://www.youtube.com/playlist?list=PLRqwX-V7Uu6ZiZxtDDRCi6uhfTH4FilpH References: 📕 The Nature of Code Part 2 (Spring 2017) - Intelligence and Learning: https://github.com/shiffman/NOC-S17-2-Intelligence-Learning 📕 Nature of Code: https://github.com/nature-of-code/noc-book-2 🥓 The Oracle of Bacon: http://oracleofbacon.org/ 🗄 Breadth-First Search on Wikipedia: https://en.wikipedia.org/wiki/Breadth-first_search 📘 Grokking Algorithms: https://www.manning.com/books/grokking-algorithms Videos: 🚂 My Video on Associative Arrays: https://youtu.be/_5jdE6RKxVk 🚂 My Video on Prototypes: https://www.youtube.com/watch?v=hS_WqkyUah8 🔴 Coding Train Live 88: https://youtu.be/YUlJAu1j_UM?t=4054s Related Coding Challenges: 🚂 #65 Binary Tree: https://youtu.be/ZNH0MuQ51m4 🚂 #98 Quadtree: https://youtu.be/OJxEcs0w_kE Timestamps: 0:00 Introducing today's topic: Breadth First Search 2:42 6 Degrees of Bacon 4:45 Node object 6:40 Let's Code! 8:02 Graph Object 9:44 Read the data 12:28 Attach a method to the graph object using prototype 16:52 Add an edges function 17:38 Determine whether actor node already exists Editing by Mathieu Blanchette Animations by Jason Heglund Music from Epidemic Sound 🚂 Website: http://thecodingtrain.com/ 👾 Share Your Creation! https://thecodingtrain.com/guides/passenger-showcase-guide 🚩 Suggest Topics: https://github.com/CodingTrain/Suggestion-Box 💡 GitHub: https://github.com/CodingTrain 💬 Discord: https://thecodingtrain.com/discord 💖 Membership: http://youtube.com/thecodingtrain/join 🛒 Store: https://standard.tv/codingtrain 🖋️ Twitter: https://twitter.com/thecodingtrain 📸 Instagram: https://www.instagram.com/the.coding.train/ 🎥 Coding Challenges: https://www.youtube.com/playlist?list=PLRqwX-V7Uu6ZiZxtDDRCi6uhfTH4FilpH 🎥 Intro to Programming: https://www.youtube.com/playlist?list=PLRqwX-V7Uu6Zy51Q-x9tMWIv9cueOFTFA 🔗 p5.js: https://p5js.org 🔗 p5.js Web Editor: https://editor.p5js.org/ 🔗 Processing: https://processing.org 📄 Code of Conduct: https://github.com/CodingTrain/Code-of-Conduct This description was auto-generated. If you see a problem, please open an issue: https://github.com/CodingTrain/thecodingtrain.com/issues/new #breadthfirstsearchalgorithm #sixdegreesofkevinbacon #javascript #p5js

detail
{'title': 'Coding Challenge #68: Breadth-First Search Part 1', 'heatmap': [{'end': 580.879, 'start': 556.178, 'weight': 0.719}, {'end': 633.151, 'start': 600.899, 'weight': 0.901}], 'summary': 'Covers breadth-first search algorithm, graph algorithms, kevin bacon experiment, and graph data structure, emphasizing practical applications like finding shortest paths, visualizing relationships, and creating mazes. it also details the implementation of a graph data structure using a hash table, node object functionalities, and setting up a graph with 74 nodes and actor nodes.', 'chapters': [{'end': 146.441, 'segs': [{'end': 76.065, 'src': 'embed', 'start': 46.26, 'weight': 2, 'content': [{'end': 49.664, 'text': "But you can also just be here right now, because I'm going to do everything from scratch with no knowledge.", 'start': 46.26, 'duration': 3.404}, {'end': 52.927, 'text': 'But a graph system is a system of nodes and edges.', 'start': 49.684, 'duration': 3.243}, {'end': 54.569, 'text': 'And you can see here are the nodes.', 'start': 53.227, 'duration': 1.342}, {'end': 56.311, 'text': 'Now, the nodes all have a name.', 'start': 54.669, 'duration': 1.642}, {'end': 59.234, 'text': 'These names are exactly the names in the Grokking Algorithms book.', 'start': 56.351, 'duration': 2.883}, {'end': 61.997, 'text': 'And they have edges, so they have connections.', 'start': 60.315, 'duration': 1.682}, {'end': 66.902, 'text': 'You can think of this as maybe a map of friends and their relationships.', 'start': 62.037, 'duration': 4.865}, {'end': 72.024, 'text': 'You could also turn this into more like a maze type thing.', 'start': 67.702, 'duration': 4.322}, {'end': 76.065, 'text': "There's so many different ways you could sort of visualize this idea of a graph system.", 'start': 72.044, 'duration': 4.021}], 'summary': 'Introduction to graph systems with nodes, edges, and relationships.', 'duration': 29.805, 'max_score': 46.26, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/piBq7VD0ZSo/pics/piBq7VD0ZSo46260.jpg'}, {'end': 105.424, 'src': 'embed', 'start': 82.767, 'weight': 0, 'content': [{'end': 90.69, 'text': 'But that aside, what breadth-first search is designed to do is find the shortest path between two nodes.', 'start': 82.767, 'duration': 7.923}, {'end': 95.512, 'text': "And in something like this, it's quite a simple problem.", 'start': 91.13, 'duration': 4.382}, {'end': 97.053, 'text': 'to eyeball it.', 'start': 96.352, 'duration': 0.701}, {'end': 105.424, 'text': 'We can see if I want to get from you or me or whoever this person is to Tom, I can see through Claire there are just two steps.', 'start': 97.374, 'duration': 8.05}], 'summary': 'Breadth-first search finds the shortest path between two nodes, with just two steps from one person to another via claire.', 'duration': 22.657, 'max_score': 82.767, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/piBq7VD0ZSo/pics/piBq7VD0ZSo82767.jpg'}, {'end': 157.109, 'src': 'embed', 'start': 127.395, 'weight': 1, 'content': [{'end': 129.377, 'text': 'looks at all the nearest nodes first.', 'start': 127.395, 'duration': 1.982}, {'end': 135.811, 'text': "sees. if it finds what it's looking for, then looks at all the nearest ones to those first and sees what it looks to find first,", 'start': 130.606, 'duration': 5.205}, {'end': 137.813, 'text': 'as opposed to going all the way through.', 'start': 135.811, 'duration': 2.002}, {'end': 141.076, 'text': 'I recently made a video about binary trees and search trees.', 'start': 138.133, 'duration': 2.943}, {'end': 146.441, 'text': "That's more like depth first search, because in the binary tree, you just keep going to the left all the way to the bottom.", 'start': 141.376, 'duration': 5.065}, {'end': 150.444, 'text': "But here, breadth first, we're looking at the nearest neighbors to start.", 'start': 146.661, 'duration': 3.783}, {'end': 153.888, 'text': "OK, so what's the problem that I'm going to work with today?", 'start': 150.765, 'duration': 3.123}, {'end': 157.109, 'text': "You may or may not be familiar with, I don't know what.", 'start': 155.188, 'duration': 1.921}], 'summary': 'Discusses depth-first and breadth-first search in binary trees and search trees.', 'duration': 29.714, 'max_score': 127.395, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/piBq7VD0ZSo/pics/piBq7VD0ZSo127395.jpg'}], 'start': 0.998, 'title': 'Breadth-first search algorithm', 'summary': 'Explains the concept of breadth-first search algorithm with a practical example of finding the shortest path between nodes in a graph system, emphasizing its application in visualizing relationships and creating mazes.', 'chapters': [{'end': 146.441, 'start': 0.998, 'title': 'Breadth-first search algorithm', 'summary': 'Explains the concept of breadth-first search algorithm with a practical example of finding the shortest path between nodes in a graph system, emphasizing its application in visualizing relationships and creating mazes.', 'duration': 145.443, 'highlights': ['Breadth-first search algorithm is designed to find the shortest path between two nodes in a graph system. The algorithm is demonstrated using an example of finding the shortest path between nodes in a graph system, illustrating its application in visualizing relationships and creating mazes.', 'The algorithm prioritizes looking at all the nearest nodes first to find the desired path. Breadth-first search algorithm focuses on examining the nearest nodes first to locate the desired path, contrasting it with depth-first search algorithm that descends all the way through a tree structure.', 'The video is part of a series on graph systems and search algorithms, which are also covered in the Grokking Algorithms book by Aditya Y. Bhargava. The video is a part of a series on graph systems and search algorithms, with a reference to the Grokking Algorithms book by Aditya Y. Bhargava as a valuable resource for learning about these concepts.']}], 'duration': 145.443, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/piBq7VD0ZSo/pics/piBq7VD0ZSo998.jpg', 'highlights': ['Breadth-first search algorithm is designed to find the shortest path between two nodes in a graph system.', 'The algorithm prioritizes looking at all the nearest nodes first to find the desired path.', 'The video is part of a series on graph systems and search algorithms, which are also covered in the Grokking Algorithms book by Aditya Y. Bhargava.']}, {'end': 486.137, 'segs': [{'end': 230.471, 'src': 'embed', 'start': 198.996, 'weight': 0, 'content': [{'end': 204.118, 'text': 'casts and uses breadth-first search to find the shortest path between two actors.', 'start': 198.996, 'duration': 5.122}, {'end': 211.501, 'text': 'And the thought experiment here is that Kevin Bacon has just been in so many movies that anyone could be within six degrees of Kevin Bacon.', 'start': 204.138, 'duration': 7.363}, {'end': 212.862, 'text': "I don't think I have an IMDB.", 'start': 211.541, 'duration': 1.321}, {'end': 217.364, 'text': "What's the chance that Kevin Bacon to Daniel Shiffman? Nah.", 'start': 213.822, 'duration': 3.542}, {'end': 219.065, 'text': 'Infinity Infinity.', 'start': 218.004, 'duration': 1.061}, {'end': 219.825, 'text': "We've got to work on that.", 'start': 219.085, 'duration': 0.74}, {'end': 220.185, 'text': 'Come on.', 'start': 219.905, 'duration': 0.28}, {'end': 221.386, 'text': 'Help me out with this here.', 'start': 220.526, 'duration': 0.86}, {'end': 223.627, 'text': 'I want my Kevin Bacon number to come on down.', 'start': 221.406, 'duration': 2.221}, {'end': 230.471, 'text': 'OK So how are we going to do this? So this is an experiment.', 'start': 224.048, 'duration': 6.423}], 'summary': "Using breadth-first search to find shortest path between actors, like kevin bacon's 6 degrees of separation.", 'duration': 31.475, 'max_score': 198.996, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/piBq7VD0ZSo/pics/piBq7VD0ZSo198996.jpg'}, {'end': 266.913, 'src': 'embed', 'start': 240.777, 'weight': 1, 'content': [{'end': 244.9, 'text': 'I manually created, before coming here right now, this data set.', 'start': 240.777, 'duration': 4.123}, {'end': 253.085, 'text': "So this data set has a few movies in it, some of which have Kevin Bacon in it, and some of which don't have Kevin Bacon in it.", 'start': 245.18, 'duration': 7.905}, {'end': 257.547, 'text': "It's organized in JSON format, which is JavaScript Object Notation.", 'start': 253.225, 'duration': 4.322}, {'end': 262.85, 'text': "I do have some video tutorials about that if that's unfamiliar to you, but I'll try to talk about that a little bit as I go through.", 'start': 257.767, 'duration': 5.083}, {'end': 266.913, 'text': "So let me move over to the whiteboard to figure out how we're going to work this out.", 'start': 263.351, 'duration': 3.562}], 'summary': 'Created a data set with movies, some featuring kevin bacon, organized in json format.', 'duration': 26.136, 'max_score': 240.777, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/piBq7VD0ZSo/pics/piBq7VD0ZSo240777.jpg'}, {'end': 435.034, 'src': 'embed', 'start': 387.877, 'weight': 2, 'content': [{'end': 388.838, 'text': "And I'm just going to put that.", 'start': 387.877, 'duration': 0.961}, {'end': 391.48, 'text': 'So I have a JavaScript project set up.', 'start': 388.958, 'duration': 2.522}, {'end': 396.084, 'text': "If I go to the browser and refresh the page, there's nothing on the page.", 'start': 391.86, 'duration': 4.224}, {'end': 398.025, 'text': "But I'm going to start adding some code.", 'start': 396.784, 'duration': 1.241}, {'end': 404.07, 'text': "So first thing I'm going to do is I'm going to write a constructor function for a node object.", 'start': 398.405, 'duration': 5.665}, {'end': 407.893, 'text': "And I'm going to say this.value equals something.", 'start': 404.95, 'duration': 2.943}, {'end': 409.194, 'text': 'We needed that.', 'start': 408.633, 'duration': 0.561}, {'end': 421.409, 'text': "This.edges is an array, this.searched is false, it hasn't been searched, and this.parent, I'm going to just set it equal to null.", 'start': 411.815, 'duration': 9.594}, {'end': 423.77, 'text': 'So I want to be able to.', 'start': 421.809, 'duration': 1.961}, {'end': 432.353, 'text': 'whenever I make a node with this constructor function, even though this, by definition, its parent would be undefined.', 'start': 423.77, 'duration': 8.583}, {'end': 435.034, 'text': "I'm going to explicitly set it to null, just so I'm kind of keeping track of that.", 'start': 432.353, 'duration': 2.681}], 'summary': 'Setting up a javascript project with constructor function for a node object and initializing its properties.', 'duration': 47.157, 'max_score': 387.877, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/piBq7VD0ZSo/pics/piBq7VD0ZSo387877.jpg'}], 'start': 146.661, 'title': 'Graph algorithm and kevin bacon experiment', 'summary': "Explores 'six degrees of kevin bacon' using breadth-first search, amy schumer's bacon number being two, and creating a toy dataset in json. it also details implementing a node object for a graph algorithm with attributes and functionalities like value, edges, searched status, and parent tracking.", 'chapters': [{'end': 262.85, 'start': 146.661, 'title': 'Kevin bacon experiment', 'summary': "Explores the concept of 'six degrees of kevin bacon' using breadth-first search to find the shortest path between actors, with an example of amy schumer's bacon number being two, and the creation of a toy dataset in json format for the experiment.", 'duration': 116.189, 'highlights': ["The chapter discusses the 'Six Degrees of Kevin Bacon' concept using breadth-first search to find the shortest path between actors, exemplifying Amy Schumer's Bacon number as two. This demonstrates the application of the concept to determine the shortest path between actors, with Amy Schumer's Bacon number being two, showcasing the efficiency of the algorithm in navigating a massive database of movies and casts.", 'The creation of a toy dataset in JSON format is mentioned, organized with some movies containing Kevin Bacon and some without. The chapter outlines the manual creation of a toy dataset in JSON format, containing movies with and without Kevin Bacon, potentially serving as a foundation for further experimentation and learning.']}, {'end': 486.137, 'start': 263.351, 'title': 'Implementing node object for graph algorithm', 'summary': 'Details the process of implementing a node object for a graph algorithm, including the attributes and functionalities required, such as value, edges, searched status, and parent tracking.', 'duration': 222.786, 'highlights': ['The process involves creating a node object that contains a value, an array for edges, a boolean to track if it has been searched, and a reference to its parent.', 'The node object also includes a constructor function to initialize its attributes, with the parent attribute explicitly set to null for tracking purposes.', 'The implementation involves setting up a JavaScript project, writing a constructor function for the node object, and organizing the code in a separate file.', 'The chapter explores the development process, including considerations such as setting up the code in a separate file and making necessary adjustments for the p5 library.']}], 'duration': 339.476, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/piBq7VD0ZSo/pics/piBq7VD0ZSo146661.jpg', 'highlights': ["The chapter discusses the 'Six Degrees of Kevin Bacon' concept using breadth-first search to find the shortest path between actors, exemplifying Amy Schumer's Bacon number as two.", 'The creation of a toy dataset in JSON format is mentioned, organized with some movies containing Kevin Bacon and some without.', 'The process involves creating a node object that contains a value, an array for edges, a boolean to track if it has been searched, and a reference to its parent.', 'The implementation involves setting up a JavaScript project, writing a constructor function for the node object, and organizing the code in a separate file.']}, {'end': 817.227, 'segs': [{'end': 538.088, 'src': 'embed', 'start': 486.557, 'weight': 0, 'content': [{'end': 494.939, 'text': 'But what I would like to do with the graph object is I would like to store an array of all the nodes.', 'start': 486.557, 'duration': 8.382}, {'end': 502.608, 'text': 'and then of all the nodes, and I probably need you know what the graph really should be as a data structure?', 'start': 496.704, 'duration': 5.904}, {'end': 512.395, 'text': "It would be something like I could look up each node by its I'll call this a graph by its label, by its value.", 'start': 502.628, 'duration': 9.767}, {'end': 526.542, 'text': 'So this would typically be something like a hash table where the key might be Kevin Bacon, And then I could,', 'start': 513.035, 'duration': 13.507}, {'end': 531.265, 'text': 'with that key I would find out all of its edges, its parent, all that other stuff.', 'start': 526.542, 'duration': 4.723}, {'end': 532.585, 'text': 'So I want to be able to have.', 'start': 531.525, 'duration': 1.06}, {'end': 538.088, 'text': "I might not need this array because I couldn't always the whole point of the algorithm is to traverse the graph to find what I'm looking for.", 'start': 532.585, 'duration': 5.503}], 'summary': 'The graph object should store nodes in an array, with a data structure like a hash table for efficient lookup.', 'duration': 51.531, 'max_score': 486.557, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/piBq7VD0ZSo/pics/piBq7VD0ZSo486557.jpg'}, {'end': 580.879, 'src': 'heatmap', 'start': 556.178, 'weight': 0.719, 'content': [{'end': 565.224, 'text': "I'm going to say function graph, this.nodes is an array, and this.graph is an object, an empty object.", 'start': 556.178, 'duration': 9.046}, {'end': 570.267, 'text': "So I'm going to use this object essentially as an associative array or a hash table, and I have a video about that if you're interested.", 'start': 565.264, 'duration': 5.003}, {'end': 572.649, 'text': 'OK, now I need to read the data.', 'start': 570.607, 'duration': 2.042}, {'end': 574.13, 'text': "That's the first thing I need to do.", 'start': 573.129, 'duration': 1.001}, {'end': 578.453, 'text': "So I'm going to use p5 as a function called preload.", 'start': 576.051, 'duration': 2.402}, {'end': 580.879, 'text': 'which I can use to.', 'start': 579.758, 'duration': 1.121}], 'summary': 'Using p5, preload function to read data for function graph.', 'duration': 24.701, 'max_score': 556.178, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/piBq7VD0ZSo/pics/piBq7VD0ZSo556178.jpg'}, {'end': 654.5, 'src': 'heatmap', 'start': 600.899, 'weight': 2, 'content': [{'end': 603.821, 'text': "I'm pretty sure from the comments that it's gif, though, and not jif.", 'start': 600.899, 'duration': 2.922}, {'end': 605.762, 'text': "I've been told that many a time.", 'start': 604.281, 'duration': 1.481}, {'end': 608.524, 'text': "OK, so now I'm just going to, in setup, I'm going to say no canvas.", 'start': 605.903, 'duration': 2.621}, {'end': 610.786, 'text': "P5 makes a canvas by default, but I don't need it.", 'start': 608.765, 'duration': 2.021}, {'end': 613.088, 'text': "And then I'm going to console.log the data.", 'start': 611.146, 'duration': 1.942}, {'end': 614.749, 'text': "So let's just make sure the data is there.", 'start': 613.448, 'duration': 1.301}, {'end': 616.959, 'text': 'And we can see there it is.', 'start': 616.118, 'duration': 0.841}, {'end': 618.2, 'text': 'So the data came in.', 'start': 617.299, 'duration': 0.901}, {'end': 620.721, 'text': 'I have an object which has an array called movies.', 'start': 618.22, 'duration': 2.501}, {'end': 625.465, 'text': 'And each movie has a property called cast, which is an array of all the actors.', 'start': 620.982, 'duration': 4.483}, {'end': 626.446, 'text': "So that's great.", 'start': 625.825, 'duration': 0.621}, {'end': 633.151, 'text': 'So now what I need to do is I need to make a node for every movie and every actor.', 'start': 626.906, 'duration': 6.245}, {'end': 637.494, 'text': 'So I want to be able to parse through and read this list.', 'start': 634.792, 'duration': 2.702}, {'end': 639.936, 'text': 'So the object has movies.', 'start': 638.034, 'duration': 1.902}, {'end': 642.277, 'text': "So I'm going to say var movies.", 'start': 639.956, 'duration': 2.321}, {'end': 644.74, 'text': 'equals data.movies.', 'start': 643.197, 'duration': 1.543}, {'end': 648.928, 'text': "Then I'm going to loop over all the movies in that JSON file.", 'start': 645.301, 'duration': 3.627}, {'end': 653.079, 'text': "Well, I'm really not on to breadth-first search yet.", 'start': 651.118, 'duration': 1.961}, {'end': 654.5, 'text': "I'm just kind of gathering the data.", 'start': 653.099, 'duration': 1.401}], 'summary': 'Parsing json data to create nodes for movies and actors.', 'duration': 28.675, 'max_score': 600.899, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/piBq7VD0ZSo/pics/piBq7VD0ZSo600899.jpg'}], 'start': 486.557, 'title': 'Graph data structure', 'summary': 'Discusses the implementation of a graph data structure using a hash table to store nodes and their relationships, aiming to enable efficient traversal and visualization. it also covers creating nodes for movies and actors, adding them to a graph, and resolving errors while implementing the graph in javascript using p5 and json data.', 'chapters': [{'end': 554.997, 'start': 486.557, 'title': 'Graph data structure', 'summary': 'Discusses the implementation of a graph data structure using a hash table to store nodes and their relationships, with the aim of enabling efficient traversal and visualization.', 'duration': 68.44, 'highlights': ['The graph object aims to store an array of nodes and implement a data structure using a hash table for efficient lookup and traversal.', "The use of a hash table allows looking up nodes by label, such as 'Kevin Bacon', and retrieving their related information, facilitating efficient data retrieval and manipulation.", 'While the primary purpose is efficient traversal, having an array of nodes could be useful for visualization or quick iteration over all nodes.']}, {'end': 817.227, 'start': 556.178, 'title': 'Creating graph nodes and adding to graph', 'summary': 'Discusses creating nodes for movies and actors, adding them to a graph, and resolving errors while implementing the graph in javascript using p5 and json data.', 'duration': 261.049, 'highlights': ['The chapter discusses creating nodes for movies and actors, adding them to a graph, and resolving errors while implementing the graph in JavaScript using p5 and JSON data.', "The data consists of an object with an array of movies, each having a 'cast' property containing an array of actors, and the goal is to create a node for each movie and actor.", "The process involves using JavaScript's prototype to attach a method to the graph object and resolving errors related to adding a reference to node and graph object JavaScript files and defining the addNode function."]}], 'duration': 330.67, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/piBq7VD0ZSo/pics/piBq7VD0ZSo486557.jpg', 'highlights': ["The use of a hash table allows looking up nodes by label, such as 'Kevin Bacon', and retrieving their related information, facilitating efficient data retrieval and manipulation.", 'The graph object aims to store an array of nodes and implement a data structure using a hash table for efficient lookup and traversal.', 'The chapter discusses creating nodes for movies and actors, adding them to a graph, and resolving errors while implementing the graph in JavaScript using p5 and JSON data.']}, {'end': 1277.345, 'segs': [{'end': 982.034, 'src': 'embed', 'start': 928.609, 'weight': 0, 'content': [{'end': 933.872, 'text': "And it's also got a whole bunch of objects, which all have the actor name or the movie name as the lookup.", 'start': 928.609, 'duration': 5.263}, {'end': 934.752, 'text': 'So this is good.', 'start': 934.072, 'duration': 0.68}, {'end': 936.013, 'text': "I'm kind of almost there.", 'start': 934.892, 'duration': 1.121}, {'end': 939.695, 'text': 'What do I have so far? I have a graph object.', 'start': 936.773, 'duration': 2.922}, {'end': 943.936, 'text': 'which stores all of these nodes, only it looks like this.', 'start': 940.535, 'duration': 3.401}, {'end': 946.337, 'text': "I haven't done any of the edges.", 'start': 944.636, 'duration': 1.701}, {'end': 953.318, 'text': "So what do I need to do? Every movie needs to be connected to every actor that's in that movie.", 'start': 946.837, 'duration': 6.481}, {'end': 956.599, 'text': 'So I need some way of setting edges.', 'start': 953.539, 'duration': 3.06}, {'end': 961.281, 'text': "So the edges for each node should be a list of other nodes that it's connected to.", 'start': 956.799, 'duration': 4.482}, {'end': 962.601, 'text': 'So let me see if I can do this.', 'start': 961.581, 'duration': 1.02}, {'end': 970.327, 'text': "So if I'm thinking about this code-wise, what I want to do here is for every actor, let me call this MovieNode.", 'start': 964.298, 'duration': 6.029}, {'end': 979.24, 'text': 'I want to say something like MovieNode.connect ActorNode.', 'start': 973.692, 'duration': 5.548}, {'end': 982.034, 'text': 'So I want to connect the movie to the actor.', 'start': 980.253, 'duration': 1.781}], 'summary': 'Developing a graph object to connect movies and actors.', 'duration': 53.425, 'max_score': 928.609, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/piBq7VD0ZSo/pics/piBq7VD0ZSo928609.jpg'}, {'end': 1124.149, 'src': 'embed', 'start': 1092.647, 'weight': 2, 'content': [{'end': 1098.87, 'text': "So I could just have a function that says get node, and that function will return null if the actor's not in there.", 'start': 1092.647, 'duration': 6.223}, {'end': 1108.794, 'text': 'So then I could say if actor node equals null, then I make a new actor node.', 'start': 1099.77, 'duration': 9.024}, {'end': 1116.301, 'text': 'So what do I need to add here? I need to add a getNode function into the graph.', 'start': 1111.516, 'duration': 4.785}, {'end': 1117.462, 'text': 'So let me add that.', 'start': 1116.601, 'duration': 0.861}, {'end': 1124.149, 'text': 'So I want to say graph.prototype.getNode equals function.', 'start': 1117.902, 'duration': 6.247}], 'summary': 'Creating a function to get a node in the graph.', 'duration': 31.502, 'max_score': 1092.647, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/piBq7VD0ZSo/pics/piBq7VD0ZSo1092647.jpg'}, {'end': 1277.345, 'src': 'embed', 'start': 1265.273, 'weight': 4, 'content': [{'end': 1267.095, 'text': 'I would love to see your solution.', 'start': 1265.273, 'duration': 1.822}, {'end': 1273.681, 'text': "But I'm going to stop and what I'm going to do in the next video is I'm going to implement the breadth-first search algorithm.", 'start': 1268.256, 'duration': 5.425}, {'end': 1277.345, 'text': "And when I come back at the beginning of it, if I found any mistakes, I'll let you know.", 'start': 1273.881, 'duration': 3.464}], 'summary': 'Implementing breadth-first search algorithm in next video.', 'duration': 12.072, 'max_score': 1265.273, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/piBq7VD0ZSo/pics/piBq7VD0ZSo1265273.jpg'}], 'start': 817.547, 'title': 'Graph data setup and actor node creation', 'summary': 'Covers setting up a graph object with 74 nodes, adding actors to the graph, and defining edge connections between movies and actors. it also discusses creating actor nodes, debugging for bidirectional edges, and planning to implement the breadth-first search algorithm in the next video.', 'chapters': [{'end': 1028.76, 'start': 817.547, 'title': 'Graph data setup and edge connection', 'summary': 'Covers setting up a graph object with 74 nodes and discusses the process of adding actors to the graph, iterating over movies and actors, and defining edge connections between movies and actors.', 'duration': 211.213, 'highlights': ['Iterating over all the movies and the actors to add them to the graph, resulting in 74 nodes being stored in the graph object.', 'Discusses the need for setting edges connecting each movie to every actor in that movie and introduces the concept of bidirectional connections in the graph.', "Introducing the 'add edge' function to connect nodes in the graph and encountering a problem that needs to be addressed."]}, {'end': 1277.345, 'start': 1029.8, 'title': 'Creating actor nodes in graph', 'summary': 'Discusses the process of creating actor nodes in a graph data structure, including checking for existing nodes, defining the getnode function, and debugging the code to ensure bidirectional edges, with a plan to implement the breadth-first search algorithm in the next video.', 'duration': 247.545, 'highlights': ['Implementing getNode function in the graph The speaker emphasizes the need to add a getNode function into the graph to check for existing nodes, ensuring efficiency and preventing duplicate actor nodes in the data set.', 'Debugging bidirectional edges in the graph The speaker identifies the need to establish bidirectional edges in the graph, highlighting the importance of this process in accurately representing connections between actors and movies.', 'Plan to implement breadth-first search algorithm in the next video The speaker outlines the plan to implement the breadth-first search algorithm in the next video, indicating the progression to the next stage of the project and demonstrating a structured approach to the development process.']}], 'duration': 459.798, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/piBq7VD0ZSo/pics/piBq7VD0ZSo817547.jpg', 'highlights': ['Iterating over all the movies and actors to add them to the graph, resulting in 74 nodes being stored.', 'Discussing the need for setting edges connecting each movie to every actor and introducing bidirectional connections.', 'Implementing getNode function in the graph to check for existing nodes, ensuring efficiency and preventing duplicates.', 'Debugging bidirectional edges in the graph to accurately represent connections between actors and movies.', 'Planning to implement the breadth-first search algorithm in the next video, indicating the progression to the next stage of the project.']}], 'highlights': ['The algorithm prioritizes looking at all the nearest nodes first to find the desired path.', 'The video is part of a series on graph systems and search algorithms, which are also covered in the Grokking Algorithms book by Aditya Y. Bhargava.', "The chapter discusses the 'Six Degrees of Kevin Bacon' concept using breadth-first search to find the shortest path between actors, exemplifying Amy Schumer's Bacon number as two.", 'The creation of a toy dataset in JSON format is mentioned, organized with some movies containing Kevin Bacon and some without.', "The use of a hash table allows looking up nodes by label, such as 'Kevin Bacon', and retrieving their related information, facilitating efficient data retrieval and manipulation.", 'Iterating over all the movies and actors to add them to the graph, resulting in 74 nodes being stored.', 'Discussing the need for setting edges connecting each movie to every actor and introducing bidirectional connections.', 'Planning to implement the breadth-first search algorithm in the next video, indicating the progression to the next stage of the project.']}