so with this video we will be starting off with the graph series and the first video in the series will be introduction to graph where we will be learning about what different kinds of graphs we have and all the conventions that revolve around the graph that will be used going forward in the next set of videos so you see the structure okay now this structure is generally known as a graph now let's talk about the types of graph now this structure is known as an undirected graph why i will tell you whereas this structure is known as a directed graph you would have guessed why because you see arrows over here that is why directed you don't see arrows over here that's undirected but what are these things we need to know that as well right so let's understand so in graphs you will see these circular things okay and those are generically known as nodes remember this nodes or vertex we typically call them as nodes or vertex now these nodes are represented by a number like for an example i said this is the node 1 this is node 2 this can be node 3 this can be 4 this can be 5 there is no specific order in which you number the nodes the numbering of the nodes can be in any order remember this so over here how many nodes we have we have exactly five nodes so we write the number of nodes as five remember this the number of nodes as five we can also call this as v which is the number of vertex now every node like if you see this two nodes are connected right these two nodes are connected by a horizontal line now what is this horizontal line referred as this horizontal line is referred as an edge so if i be specific this edge can also be known as or called as undirected edge why undirected edge if you see the edge can also go from one to four right or the edge can also go from four to one so it can be a bi-directional edge the edge can be in both the directions so thereby whenever you see an undirected graph and there is a mention that there is an edge between u and v it resembles that there is an edge between u and v as well as there is an edge between v and u so an undirected graph means there can be an edge in both the directions so as of now we just need to know about these terminologies node vertex undirected edge and this is known as an undirected graph okay now is it compulsory that the graph has to be something like a circle or something like that we will be uh talking about that but before that let's understand what is a directed graph now the only different only difference in a directed graph is this thing that you see over here this will be a directed edge remember this this thing will be a directed edge rest everything will stay the same imagine if i number this one and four then i can only say that there is an edge between 1 and 4 which means if i'm standing at 1 i can go to 4 but if i'm standing at 4 i cannot come back to 1. so this is what we call as directed graph a directed graph is a graph where all the edges please room please mind this word where all the edges are directed where all the edges are directed can there be multiple directed edges yes you can also have something like this where you say there is an edge between 1 to 4 there is an edge between 4 to 1 so you can also have bi-directional edges as well so that is the two kind of graphs that we generally have one is the undirected graph while the other one is the directed graph so that was about the types of graph now let's understand the other type of graph now there are something known as cycles in a graph remember this cycles in a graph now you might be thinking what does graph mean is it always a circular structure or what it is now i can say if i just draw some graphs this is also a graph we don't see a circle yes we don't see a circle getting completed we can say this is also a graph now you might have read in the binary trees if you have not read binary trees you can definitely read them from my playlist so this is a binary tree but this can also be called as a graph why because it follows all the rules we have nodes we have edges and they perfect and that is what is the minimal condition for anything to be called a graph so this guy can also be called a graph so a graph does not necessarily means that it has to be an enclosed enclosed structure it can be a open structure as well okay so this is where something as cycle comes in okay now what is a cycle cycle definitely means if you're starting from an node you reach back to that node remember this start from a node and end at that node that is the definition of a cycle now if you carefully observe over here can i say this has a cycle yes why because if you start from one you can go to two you can go to five you can go to four you can come back so there is a cycle in this graph there are multiple cycles you can also say this is a cycle you can also say this is a cycle so there can be multiple cycles so if there is a single cycle in a graph you generally call that as an undirected cyclic graph undirected cyclic graph the definition graph does not assumes that it is an enclosed structure but the moment you attach this term cyclic to it we can always call it as an undirected cyclic graph i hope that is sure now let's come back to this example and let's omit this now this is a directed graph do we see a cycle over here now this no do we see a cycle here no do we see a cycle here no so this directed graph does not have a cycle because we are starting at 1 but we are not ending at 1 or we are starting at this particular node but we are not ending over here so unless and until we start from a node and we end at there vice or via some path i'll tell you what path is we don't call that as a cyclic graph so we can call this as directed like as i click graph so it's generally known as as i click graph as i click means no cycle so directed a cyclic graph is what we call this okay but over here if i just attach a edge if i just include another edge we can say that this graph has a cycle y because yeah this is a cycle so it will now become directed cyclic graph but without this edge without this edge it is known as directed a cyclic graph which is commonly known as dag which will be which you will be hearing in the next set of the lectures fine so let's come to the next term which is path now what is the definition of a path can contain a lot of vertices contain a lot of nodes or vertices and each of them are reachable very important each of them are reachable okay so what does this mean so assume i write something like 1 2 3 4 5 so we know that this is a graph again satisfies all the definition you have nodes you have edges so this is definitely a graph right so over here what we see is if i write 1 two three five it is a path because one two three five this is a path because you go from one to two to three to five this is a path but if i write something like one two three two one this is not a path why because you're saying one two three and again you're saying two you cannot have a node appearing twice in a path a node cannot appear twice in a path remember this a node cannot appear twice in a path it can only appear once is this a path no why because you say one you say three you say five but how do you reach from one to three there is no connectivity from one to three there is no edge from one to three so you cannot so a path that you are writing the adjacent nodes must have an edge between them like one two has an edge two and three has an edge three and five as an edge so that you can travel in that path so that is what is the definition of a path so the next term that we will be learning is the degrees in a graph so assume if i name them as one two three four five and i say can you tell me the degree of the node 3 so remember the definition of a degree is the number of edges that go inside that or go outside that total so i can say there is 1 2 3 which is attached to 3 so the degree of 3 is 3 similarly the degree of 4 is 2 y because there are two edges which are attached to it the degree of 5 will be 3 the degree of 2 will be 2 and the degree of 1 will be 2 so the definition of a degree for an undirected graph very important for an undirected graph is the number of edges that are attached to it is known as the degree of the graph and there is a property as well please take care of this property the property states that the total degree yes the total degree of a graph is equal to twice of the number of edges is equal to twice of the number of edges why because every edge is associated to two nodes that is the reason why because every edge is associated with two nodes so let's compute the degree so the degree of this is two again two three two and three so if i compute the total we will be getting six three nine twelve so the total degree of this graph is twelve and if i compute the number of edges one two three four five six six number of edges and the property gets satisfied intuition is very simple every edge is connected to two nodes thereby this particular property stands so this was for undirected graph now let's talk about something which is directed graph remember this in directed graph we have two different things one is the in degree of a particular node while the other one is the out degree of this particular node now what do you mean by in degree or out degree so imagine this is the graph okay so let's quickly draw a graph and perfect so if i ask you for this particular note okay if i ask you for this particular node what is the in degree for this node what will be the answer assume this node is node number three in degree of free the number of incoming edges the number of incoming edges the edges that go inside it is the in degree so that's two so if i ask you what is the out degree of that particular node the number of outgoing edges that is only one so you can say the out degree is one so the in degree and out degree will be in this way so that will be in terms of directed graph now the last term that we will be learning about is the edge weights that's very important to understand what is an edge weight now we talked that okay these are notes and this is an edge now every no every edge rather every edge will be having a weight now in problems that you'll be facing they might say that this edge hasn't weighed three this edge might have a weight two this might have one this might have five this might have six this might have two this might have one this might have five this might have seven they can assign any weights to any edges and this is what we call as edge weight what if weights are not assigned like they don't tell you what are the weights in that case we will always assume unit weights which is one if the weights are not not assigned we assume unit weights that is one so guys that will be it for this particular video i hope you understood everything that i taught in this particular video just in case you did please hit that like button and if you're new to our channel what are you waiting for kill that subscribe button right away and if you haven't checked out our dp series and all the other series the links are in the description please make sure you check them out with this i'll be wrapping up this video let's meet in the next lecture till then bye take it whenever your heart is [Music]