Chapter 1 | The Beauty of Graph Theory

[Music] the first time I heard about graph Theory my initial assumption was that it might be related to things like graphs or functions as those were the only types of graphs I was familiar with at that point but the relatively new mathematical field of graph Theory turns out to be in fact something totally different [Music] what exactly is a graph a graph G is defined by a pair of a finite set capital V of nodes also called vertices and a set of edges capital E the edges of a graph represent relationships between the nodes in most cases the nodes are labeled with numbers or alphabetical letters to distinguish them from each other for the graph above the set of nodes capital V is capital V equal to the set containing the elements 1 2 3 4 and 5 and the set of edges capital E is defined by the following sets the graph G is then the pair of capital V and capital E regarding this Edge set the graph consists of edges connecting the nodes 1 and 2 1 and 3 1 and 4 2 and 3 3 and four 3 and five and four and five a graph like this is called an undirected unweighted graph before we proceed a quick remark about a notation used in this course an edge connecting two notes u and v in an undirected unweighted graph will be denoted Su UV or SVU both notations have the exact same meaning an incredible amount of problems in the real world can be modeled through a graph especially when the instances of the problem stay in some relationship to each other like in a network let's say a n in this network between two individuals represents a friendship between them by the selection of any person from this network we can explore all of their friends by tracing where the edges connected to them LED more formly the friends of the person in the yellow notes let's call this note you to find the neighborhoods of the note you in a general graph the neighborhood n of U consists of all nodes V in the set capital V that are reachable from the node U by using a single edge so an edge connecting u and v that is included in the edge set capital E of the underlying graph every front of the person in the yellow note is called an adjacent note of the yellow note or in math language every note contained in the neighborhood set and of youu is an adjacent note of U the last definition counts the amount of edges attached to the yellow no this number is called the degree of a note in this graph the degree of a person corresponds to the number of friends the person has but important the degree of a no doesn't always represent the number of neighbors of a Noe this is only the case if there isn't more than one Edge between two nodes the yellow Noe here has obviously a degree of five an interesting property of graphs becomes visible when adding all degrees of all nodes in a Gra together for this let us iterate through every note in the graph determine its degree and add all degrees together this node has a degree of six so our total degree becomes 11 the next node has a degree of nine so our total degree becomes 20 the next one has a degree of eight so our total degree becomes 28 and so [Music] on at the end we obtain the sum of the degrees of all nodes and what property does this number have it is even in fact this is not a coincidence here independent of the specific graph the sum of all degrees is always even further more knowing the sum of all degrees in the graph allows also for the calculation of the total number of edges in that graph what might sound surprising at first the summation of all degrees in the graph in the animation yields free ,1 192 in fact the graph in the animation is a complete graph meaning a graph in which every note is connected to all other notes excluding itself more details this graph has 57 noes and every note is connected to 56 equal to 57us one other nodes therefore the sum over all degrees here is equal to 57 * 56 and the total number of edges in this graph is given by half this number because by summing up all degrees one counts every single edge twice this lets us to suspect that the sum of all degrees in the graph is always equal to twice the number of edges in the graph and this is in fact exactly the case it holds the following formula the right hand side of this equation is equal to twice a number which is obviously even because it's divisible by two now since there's an equality sign in the middle the left hand side is even as well furthermore if you consider having n many notes V1 to VN in a graph this implies that's the sum of all degrees is even and the left hand side can only be even under certain circumstances for instance if all degrees are even or if exactly two nodes have a not degree but if the number of nodes with a not degree is for example one it follows immediately that the total sum cannot be even what I want to say is that the number of nodes with a not degree in the graph is always even because the sum of all degrees has to add up to an even number according to the above formula and the interesting application now is that this holds for every graph a coroller from this is the handshake lamma which tells you if there is a party of people who shake hands the number of people who shake an odd number of other people's hands is even observations like this that helps us to better understand the structure of graphs are very important in graph Theory and for some certain graphs there are indeed still many Unsolved Mysteries waiting to be solved very important in graph Theory are so-called graph traversal algorithms which aim to visit to explore or to process every note in a graph the range of application of such algorithms is very large and they are basically two commonly used different types of them the one algorithm starts at the note and systematically visits all of its neighbors then it proceeds by visiting the neighbors of the notes that have been visited first leading to a layer-by layer exploration of the graph this algorithm is known as the bread first search BFS algorithm the subgraph generated by this algorithm is known as a bfs3 which offers valuable information about the underlying graph for instance shortest paths from the starting noes to all other nodes if the length of a path is characterized by the number of its edges in contrast to this the other algorithm follows the approach to explore the graph in depth first it selects in every iteration a neighor node possibly a random neor as the next Noe and continues in this way until it gets stuck then the natural way out think about a maze is to backtrack to the last note with unvisited notes in its neighborhoods this algorithm is known as the depth first search DFS [Music] algorithm [Music] the resulting subgraph the DFS Tre looks a bit familiar to a maze and indeed with the right modifications this simple algorithm can also be used to generate a maze as seen in the animation the white rectangles are the nodes and the dark gray rectangles are the edges of this graph I will put now a white rectangle behind this graph to make things easier to see the only thing to do now to create a maze is to run the DFS algorithm on this [Music] graph [Music] note that through the application of DFS this maze has a solution since DFS calculates a path from the starting notes to All notes in the graph in other words there is a path from the starting notes to any other note here [Music] in a city it is important that every village has access to electricity the distribution of the electricity wires can be visualized using a graph furthermore one can search for subgraphs in this graph such that every village in the city has exactly one access to electricity such subgraphs of a graph have to contain obviously every village and are called spanning trees in the real world each Edge would be assigned a label representing the costs associated with Distributing wires along the corresponding Edge which represents a street the general goal then should be to minimize the costs for the distribution of wires such that every town gets access to electricity therefore one would search for a minimum spending tree in the given graph which is a spanning tree with the least possible total cost very important in graph Theory especially in the era of navigation systems like Google Map maps are short as path algorithms think about a map of a country where each note represents a city and the edges are labeled with costs such as the kilometer distances between two nodes or the duration to travel between two adjacent nodes now imagine that you are a pizza delivery guy task with delivering a pizza to a client located far away in this scenario choosing the shortest route with respect to the edge labels is crucial to ensure that the clients doesn't have to wait too long to receive [Music] order these were just a few examples of graph Theory problems that we will analyze throughout this course which hopefully gave you a glimpse of a feeling of what graph Theory problems are about in fact we've seen that graph theory is a very strong and Broad field in mathematics with various practical applications but despite its current significance this field is relatively new to understand the origin of graph Theory we have to go back in time to [Music] 1736 in the center there's nobody else than Leonard Oiler who probably doesn't need any further introduction due to his significant contributions to some of the most famous mathematical formulas oer lived nearly in the same time span as the two outstanding mathematicians gotfried lipnet and Isaac Newton these three mathematicians are probably among the most famous and influential mathematicians to have ever lived on this planet in the time around the year 1735 the citizens of a Prussian city named kbur which was not far from St Petersburg the home of Leonard oer used to spend Sunday afternoons walking around their beautiful city while walking the citizens decided to create a game for themselves their goal being to devise a way which they could walk around the city Crossing each of the Seven Bridges in kyburg exactly once even though none of the citizens of kbur could create a route that would allow them to cross each of the Seven Bridges exactly once the question whether this is even possible remained unanswered but luckily for them it didn't last long before Leonard oer was confronted with this question oer worked on complicated and complex problems so one could have assumed that he wouldn't invest time in a problem seemingly so unrelated to the field of mathematics but there's a certain property about this problem that picked O's curiosity O's letters to other mathematicians revealed his Fascination for this problem the aspect was the problem's underlying structure and oer noticed that solving it didn't require specific details about the bridges or land masses instead he realized that the problem could be abstracted leading him to set the foundation for a concept that is known today as graph Theory furthermore he refers to this problem as being in a field mentioned by gotri lipnet called geometri citus the geometry of position a way to abstract such a problem as the Seven Bridges of kbur problem can be Illustrated using a simplified model with four islands and Seven Bridges every island represents obviously a n and every bridge an edge a walk of a citizen in kyburg has also a name in graph Theory it is a walk in the underlying graph translating to a sequence of adjacent notes in the [Music] graph while we try to walk through this graph and to cross every Edge exactly once we will always face the problem that at some point we will get stuck at the notes because we won't won't have any unused edges left to take anymore however this will always be necessary since we will still have other edges left that we have to visit in fact it doesn't even matter which work you take here because you will never succeed but why in very simple terms this has something to do with the degrees of the notes in this graph is it guaranteed in this graph that if one Edge Leeds to a note another Edge will let out of that note again very soon we will see an explanation for this but before we start dealing with the analysis of such works we should give them a name fundamental definitions in graph Theory are definitions of a path a cycle a trail a circuit an oer Trail and an Oiler circuit many people get confused here therefore it is very important to consider these definitions very clear starting with a path a path is a walk in a graph such that all visited notes in the walk are distinct so in the general definition of a path it is not allowed to use notes more than once a cycle is a path that is closed meaning it starts and stops at the same note furthermore the length of a cycle is given by the number of used edges in the cycle a trail is a work such that all used edges are distinct furthermore it can visit notes more than once a circuit not to confuse with a cycle important is a closed [Music] tra it's now the point where many people get confused an Oiler Trail is a trail that visits each Edge in the corresponding graph exactly once while such a trail is often referred to as an Oiler path it basically isn't a path because it can visit nodes more than [Music] once these definitions are unfortunately not always consistent if you hear people talking about an Oiler path it's very likely that they mean an Oiler Trail as the term Oiler path has become established and now the last definition the definition of an Oiler circuit an Oiler circuit is a circuit that visits each Edge in the graph exactly once what we are searching in kbur is either an Oiler circuit or an Oiler Trail what one can observe immediately is that the graph in the bottom right corner here which contains an Oiler circuit has only nodes with an even degree and in fact a graph that contains at least one note with an O degree cannot have an Oiler circuit the explanation for this is also not very deep if you try to start your Oiler circuit with a note that has an odd degree for example a note with a degree of three then you will leave the note at the beginning Traverse somehow through the graph come back to the starting note at some point and if you leave it then once again you won't be able to return to this note anymore as required for an a circuit otherwise if you start your Oiler circuit with a note with an even degree and encounter a note with an odd degree during your traversal you will be forced to use all of its adjacent edges during your route and then you will get stuck furthermore oiless results in this context can be found in literature by searching for oiless path and SEC theorems or just by searching for Oilers theorems Oiler shouts the three following assertions assertion one a graph in which all nodes have an even degree has an Oiler circuit assertion two a graph with exactly two notes of odds degree contains an Oiler Trail but not an Oiler circuit and a surgon free a graph with any number of odd nodes other than zero or two will not have any Oiler Trail we've already discussed the first part of the proof for assertion one of the sporum if you're interested in more I encourage you to try to prove or to argue why the other assertions must hold considering the last statement and our previous graph from the Seven Bridges of Kix back problem we can observe immediately that all nodes have an odd degree implying that this graph has neither an Oiler circuits nor an Oiler trail from 1736 to now graph theory has undergone significant development various types of graphs have been born and and graph theory has found application Beyond mathematics especially in computer science in the following we will explore some important types of graphs and especially their roles in data structures basically graphs in graph Theory can be classified into four classes undirected unweighted graphs graphs where edges have no direction and no Associated weights directed unweighted graphs graphs where edges have a specific Direction but still no weights undirected weighted graphs graphs where edges have no Direction but have Associated weights and directed weighted graphs graphs where edges have a specific Direction and also have Associated weights while dealing with graph Theory one will come across many types of graphs a very important type that we've already seen at the beginning of this video is the so-called complete graph where every note is connected to all other possible notes in the graph furthermore this graph is complete and consists of five notes which is why this graph is often referred to as K5 this graph is also in the class of the four vertex connected graphs because every Noe has exactly for Neighbors more precisely a graph G is set to be K vertex connected if it contains at least K plus one vertices but does not contain a set of K minus one vertices whose removal disconnects the graph while talking about complete graphs there are also many other important complete graphs like k6 K7 K8 and so on what's fascinating is that adding more notes to a complete graph intensifies its beauty and complexity it's captivating to see how such a simple concept can evolve into a captivating piece of of mathematical art where every new connection adds depth to the overall structure but don't worry there are still many other important and beautiful graphs that we will [Music] explore another important graph is for example the oiler graph which is a graph where every node has an even degree ensuring the existence of an Oiler circuit also an important kind of a graph is the Hamilton graph which is a graph that contains a hamiltonian cycle a cycle that visits each note exactly once finding such a cycle is a challenging problem as we will see in the next video If you deal with graph Theory you won't be able to avoid bipartite graphs a bipartite graph is defined as a graph whose notes can be divided into two disjoint sets in such a way that no two notes within the same set are adjacent in this graph we have a partition into red and blue nodes and none of the red or blue nodes are connected to nodes of the same color the only Connections in this graph are between the red and the Blue Notes this is a bipartite graph without Cycles important to note is that a graph with Cycles can also be bti furthermore a graph is in general bti if and only if every cycle is even this means that every cycle in the corresponding graph has to consist an even number of edges of course the concept of partitioning the notes of a graph into such sets can be generalized for example consider a freeti graph note that it is not necessary for a graph to be connected meaning that not every note in a graph has to be reachable from an arbitrary note a graph can be made up of many connected components a forest describes a collection of trees trees are graphs that have always the minimum number of edges necessary for connectivity a tree will be typically Illustrated with a structure like this specifically this here is a binary tree visualized in this way a binary tree can be divided into layers on each layer or depth there are nodes and the number of layers minus one represents the height of the binary tree The crucial characteristic of a b tree is that each note has at most two children in addition each note belongs to a specific class of notes the top note of a binary tree known as the root note has no parent note a note in the tree that has at least one child is called an inner node a half Leaf is a no that has only one child and a leaf node is a notes that has no children another important type of a tree that is similar to the binary tree is the Turner Tree in which each note can have at most three children but let us Focus here on binary trees binary trees are used in various applications for instance to visualize the execution of many recursive algorithms here for example the execution of a recursive function that calculates the eight Fibonacci number [Music] the famous sorting algorithm quick sort selects a pivot element in every iteration then it rearranges the array such that all elements to the left of the pivot element are smaller and all elements to the right of the pivot element are larger than the pivot element this process continues recursive ly on the left and right sub arrays the entire process can be visualized with a recursion Tree in most cases one will be interested in the height of this binary tree as it provides information about the algorithm's execution time in general there are many types of binary trees with different names over which I will give you a small overview to mention here is for instance the complete binary tree the this tree is characterized by the property that it must be completely filled on every layer of the graph except for the bottom layer and all nodes must be as far left as possible if we add a new Noe to this graph it has to be inserted as a left child of the Noe five but adding a new Noe as for example a left child of the Note 8 or as a right child of the Note 5 would violate the property of the tree to be complete as it needs to be filled layer by layer from left to right another important type of a binary tree is the so-called full binary tree in a full binary tree every node has either zero or two children but never just one child but if a binary tree has only one child per parent either a left or a right child and this through the entire tree then it is called a degenerated binary tree another important type is the so-called perfect binary tree characterized by the property that every layer is completely filled with all Leaf nodes on the same layer a general goal is to ensure that binary trees are balanced meaning that each noes to sub trees have Heights that differ by at most one but more about this later maybe you are asking yourself why binary trees are so important to understand this we have to consider a few basic data structures starting with the array an array is a simple data structure that stores a collection of elements each element identified by an index very important for us especially in the context of the graph traversal algorithm DFS is the so-called stack a stack is a data structure that follows the philosophy that elements are added and removed from the top of the stack the two main operations for a stack are the push operation which adds a new elements to the top of the stack and the pop operation which removes the most recently added element from the stack this principle is known as the last in first out lifeo principle which is similar to stacking coins another important data structure that we will see in the context of the BFS algorithm is the Q a q is a data structure that follows the principle of adding elements to one end and removing them from the other the two main operations for a q are the enq operation which adds a new elements to the back of the que and the DQ operation which removes the oldest element from the front this ensures that the elements are processed in the order they were added following the first in first out 54 principle similar to cars waiting in the line in front of a traffic light as mentioned before we will see both data structures and action in the video about graph traval algorithms a very frequently used data structure is the linked list orever the so-called doubly linked list a dou link list enables immediate access to the first and last element via the head and tail pointer each element so each cell consists of a so-called key value here the number stored in the rectangles and also a pointer to the previous element in the list and another one to the next element in the list binary trees come now into play when it comes to the time complexity of basic operations such as inserting deleting and searching for elements in the list time complexity refers to a measure of the amount of arithmetic operations an algorithm takes to run as a function of the input size it helps to understand how the algorithm's performance scales with increasing input size here the so-called Big O notation has become established in very simple terms o of one refers to a runtime that is at most constant o of l n to a runtime that is at most logarithmic o of n to a runtime that is at most linear o of n squ to a runtime that is at most quadratic and so on for those of you who want to be very precise there exists also a formal definition that clearly indicates whether a function belongs to a specific class like o of n additionally there are even other notations however understanding these Concepts is unnecessary at this moment if you want me to cover them in a separate video please write it in the comments in a dou link list inserting at the end requires constant time while deleting and searching operations require linear time and the explanation for this is also very straightforward to insert an element at the end of a doubly linked list we simply need to adjust the corresponding pointers when searching for an element we may need to Traverse through the entire list where we have to check whether each element is the one being searched for resulting in linear time complexity in the input size and to delete a specific element in a w link list we first need to locate the element which requires searching through the entire list in the worst case and results therefore in linear time complexity after locating the elements deletion involves only adjusting of pointers a task that can be completed in constant time therefore the overall time complexity for deletion is linear dominated by the search process the issue here lies obviously in the linear time complexity for both deleting and searching operations what naturally LEDs to the immediate question can we do better the answer is yes and the first step toward constructing such a data structure with a better delete and search time complexity is the binary search tree note that when considering three data structures the numbers in the nodes represent the key of the elements stored in those nodes and not the labels of the notes themselves like before a binary search tree is a binary tree with the additional property that the key of a parent note is always larger than the key of its left child and smaller or equal to the key of its right child in this case 17 is smaller than 23 and is therefore a left child of the notes 23 the 34 is larger than 23 and is therefore a right child of the noes 23 this property holds for all noes in the tree furthermore we can imply when considering the root noes that every note in the right sub tree must have a key value larger than or equal to 23 and every node in the left sub tree must have a key value smaller than that now the time complexity for the three basic operations depends obviously linearly on the height of the tree why that well let us consider some examples let's say we want to insert a note with a key value of eight where do we have to insert it to not violate the binary search tree property well 8 is smaller than the key value of the root node which is 23 therefore we know already that this element has to be placed somewhere in the left sub tree it is also smaller than 17 so that we can imply that 8 has to be placed somewhere in the left sub tree of the note with the key value 17 finally 8 is also smaller than nine so that the element will be inserted as a left child node of the node with the key elements nine now once again with a note with a key element of 29 29 is larger than 23 smaller than 34 and larger than 27 what implies that we have to insert this note as a right child note of the note with the key elements 27 so in both shown cases we had to process a note on every layer which is why the time complexity of the insertion depends linearly on the height of the tree also for the search operation we have to Traverse in the worst case as many nodes as there are layers in the tree when searching for example for the Noe with the key elements 29 we have to check first whether 29 is smaller larger or equal to 2 23 since 29 is larger than 23 we have to check in the right sub tree whether 29 is smaller larger or equal to 34 since 29 is smaller than 34 we have to explore the left sub tree attached to the Noe with the key element 34 and since 29 is larger than 27 we have to go to the right sub tree of 27 where we finally find the note with the key elements 29 the deletion of a note is a bit more complicated and Depends obviously on the notes that should be deleted to delete a leave it's clear that we can simply remove it from the tree without any further adjustments in the case that we want to delete an inner node or even the root Noe we have to replace the corresponding note with an appropriate note such that the binary search tree property won't be violated this is also possible in O ofh so so in comparison to the doubly linked list the time complexity for the insert operation in a binary search tree may have worsened while the time complexities for deleting and searching have potentially improved this Improvement is potential because these two operations in the binary search tree can have the same time complexity as in a doubly linked list because a significant problem with binary search trees is that they can become degenerated and then the height age of the tree C coincides with the number of elements in the tree so where is our progress progress is achieved when we can guarantee that the height of the tree is bounded by a term that is smaller than n so smaller than the number of elements in the tree and for this reason people invented binary search trees with additional properties like the red black tree a red black tree guarantees a height that is smaller or equal to 2 * the logarithm to the base of 2 of n + 1 where n denotes the number of notes in the tree such a tree satisfies the following properties property one every note is either red or black property two the root note is black property three if a note is red its children must be black I call this one the not red red Rule and property four for each note any path from this notes to a leaf or half Leaf has the same number of black notes we will not analyze such a tree or the corresponding insertion and deletion processes in detail here but I think it's not difficult to see that inserting or deleting nodes in this tree can easily Leed to a violation of the red black tree property which is in general not easy to restore including the assertion that the height of such a tree is never larger than the mentioned logarithmic term it can be concluded that the time complexity for for all fre basic operations is always logarithmic note that we have improved the time complexity for deleting and searching from linear in a doubly link list to logarithmic in a red black tree but this Improvement has also its price because we have no longer constant time complexity for insertion in a red black Tree close related to red black trees are AVL trees AVL trees are binary search trees where the heights of the two child sub trees of any parent nodes differ by at most one the small indices over the notes in an AVL tree represent the balance Factor indicating the height difference between the left and right sub tree of each node this balancing prevents the tree from a degeneration to maintain efficient search insert and delete operations therefore the time complexities for the three basic operations in an AVL tree coincide with those for the red black tree in summary we can say that binary search trees are important data structures that are particularly useful for search processes the last type of trees that we will discuss in this video are heaps basically there are two kinds of heaps Max heaps and mini heaps a Max Heap is a binary tree but not a binary search tree important with the property that each not key is greater than or equal to the key of its children analogously A Min Heap is a binary tree where each not key is less than or equal to the keys of its children we can observe in the animation that nine is larger than 8 and five8 is larger than seven and two five is larger than 3 and one and seven is larger than 4 and six furthermore we can observe that the note with the maximal key in the whole tree is always the root note heaps have many applications in practice for instance in Heap Sort a popular sorting algorithm the algorithm Begins by constructing a complete binary tree from the elements in the array filling the tree from left to right until all elements have been inserted the resulting complete binary tree is obviously not a heap but it is very easy to transform it into a heap or here specifically into a Max Heap the transformation can be achieved with a helper function which I call here built Max Heap and which uses the so-called heapify [Music] algorithm once the max Heap is constructed the root element can be swapped with the last element in the array at this point the last element in the array is in its correct position and can be removed from the Heap since the Heap property is violated due to the last swap we must transform the tree back into a Max he and this is possible with the heapify procedure this may sound complicated but the only thing that really happens here is that the root node will be swapped recursively with its larger child note and that's basically the key idea of Heap Sort reconstruct the Heap swap the last element with the root element reconstruct the Heap again and so on this process continues until all elements are properly sorted [Music] in the last segment of this video we will explore efficient ways of representing graphs on a computer of course a graph cannot be passed to a computer in its visual form it must be described in a more abstract way using numbers or letters and the first obvious and also KNE approach in doing so is by defining the graph over a sinite set of nodes capital V and the set of edges capital E according to its definition unfortunately this approach is very inefficient just consider the task of finding all neighbors of the note labeled with 18 in this graph you'd need to search through the entire set of edges for all edges containing the number 18 resulting in a timec consuming operation especially for large graphs [Music] but don't worry there are more efficient ways to represent a graph to mention here is for example the representation of a graph through an adjacency Matrix this Matrix is a square Matrix where the rows and columns correspond to the nodes in the graph the existence of an edge between two nodes will be indicated by a one in the corresponding cell of the Matrix while a non-existence of an edge between two two notes will be denoted by the number zero the note one is connected to the notes 2 3 5 and six therefore we insert the number one into the second third fifth and sixth column in the first row of the adjacency Matrix similarly Notes 2 is connected to the notes one and six what implies that we insert the number one into the first and sixth column in the second row of the adjacency Matrix analogously for the other rows another way of representing a graph maybe the most popular one is through an adjacency list an adjacency list represents a graph as an array of lists where each list contains the notes adjacent to a particular note this representation is often more memory efficient than the adjacency Matrix remember here that even if a Matrix contains only zeros these zeros have to be stored on your computer so if you choose to use an adjacency Matrix anyway it can be more efficient to use SP matrices because SP matrices store only the non-zero entries of a matrix significantly reducing the memory usage especially for graphs with few edges so these were two approaches to represent an undirected unweighted graph in a more efficient way of course these approaches work also for a directed unweighted graph nevertheless it is important to observe that for an undirected unweighted graph the adjacency Matrix is always symmetric which may not be the case for a directed unweighted graph maybe you're asking yourself now what is with weighted edges well weighted edges aren't a problem either in an adjacency Matrix the weight of an edge between two nodes will be inserted into the corresponding cell of the Matrix in contrast to that in an adjacency list the weight of an edge can be stored along with an adjacent Noe this can be accomplished by representing each element in a list as an object or topple containing the adjacent Noe and the weight of the corresponding edge with this being said we've reached now the end of this video thank you for watching and don't forget to subscribe for more videos

Channel: CC ACADEMY

Views: 82,206

Keywords:

Id: oXcCAAEDte0

Length: 45min 31sec (2731 seconds)

Published: Wed Feb 21 2024