hey everyone welcome to simply learn's youtube channel in this session we will be learning about graphs in data structures but before we begin make sure that you have subscribed to our youtube channel and don't forget to hit that bell icon to never miss an update from simply learn now without further ado let's get started with the agenda for today's discussion so we will be discussing a brief introduction to graphs first followed by that we will understand the graph terminologies up next we will see the types of graphs available in data structures after that we will understand the representation of graphs then we will look into the graph traversal and finally we will understand the application of graphs i hope i made myself clear with the agenda now let's begin with the first topic that is a brief introduction to graphs so what exactly is a graph so a graph is a data structure like any other data structure example linked list arrays etc so graph is a little different from the other types of data structures such as linked lists and arrays they are linear data structures whereas graph is a non-linear data structure that consists of finite sets of vertices and a bunch of edges connecting with them so what are these vertices and edges so let us understand that a graph is usually represented by a set of vertices and edges so a vertice is the node present in a graph imagine that you are a group of five friends so each one of you is considered as a vertex and the network connecting you guys is known as an edge so the overall graph of your people can be considered as g and it is represented by vertices and edges set where vertices is you and the network connecting you guys is called as an edge so here you can see it clearly each one of the friend is called as a vertex and the network connecting them is called as an edge and the entire graph is represented using a set of vertices and edges now moving ahead we will understand the graph terminologies now at first we have the adjacency vertices and adjacency edges so what are adjacent vertices if there is an edge between two vertices that is one vertex or one node is connected to another node directly using just one single edge then those vertices are called as adjacent vertices now what are adjacent edges if there is one common vertex between two edges then those two edges are called as adjacent edges let's imagine this way let us imagine that we have three vertexes and these three vertexes are connected using two edges so here we have one vertex which is common between these two edges so such type of edges are called as adjacent edges next we have the degree in an undirected graph number of vertices adjacent to the vertex is called as a degree next is the path the path is considered as a sequence of distinct vertices such that two consecutive vertices are adjacent to each other up next we have the cycle a path that has only one repeated vertices are called as first and last vertices followed by that we have the work the term block is self-explanatory a work is the sequence of vertices and edges in the graph which is used to traverse through one vertex to another vertex now we have entered the next segment of this particular tutorial where we will be discussing the different types of graphs available so at first we have the finite graph so what exactly is a finite graph a graph is said to be finite when the number of vertices and the number of edges are in a finite number or in a countable number now the next type of graph is the infinite graph so what exactly is the infinite graph so the infinite graph is a typical opposite of the finite graph so this particular graph will not have countable number of edges and countable number of vertices the image here is an example for a typical infinite graph now followed by the infinite graph we have the trivial graph so what is a trivial graph a graph is said to be trivial if there is only one single vertex without any edges so this particular type of graph will only have vertex that is only one single vertex not more than one and there will be no edge if you have just one vertex then there is no possibility of having an edge unless if you have one single loop type of edge which is connecting to itself but in a trivial graph we don't even have that we just have one single vertex so followed by trivial graph we have a simple graph so what exactly is a simple graph a graph is said to be simple if there is only one and one edge between each vertex so this particular example can be considered as a simple graph so here each and every set of vertices have one single edge between them now followed by the simple graph we have the multi graph so if there are multiple edges between the pair of vertices then this particular type of graph is known as a multi graph so here you can see that we have two vertices a and b and we have two edges connecting them not one but two but in a simple graph we were supposed to have just one edge connecting the vertices so this is the difference between simple graph and a multi graph so followed by multi graph we have a null graph so what is a null graph a graph is said to be null if there are only vertices and no edges between them so remember the trivial graph right we just had one single vertex but no edges but here we do have multiple vertices but no edges connecting them so this type of a graph is considered as null graph so followed by null graph we have the complete graph so what is a complete graph a graph is called as a complete graph where each vertex must be connected with the other vertices using the edges so the meaning of this particular type of graph is all the edges are connected to all the other edges using at least one single edge so here you can see a is connected to b d and c all together with at least one edge and similarly all other vertices are connected to each other with at least one single edge now followed by the complete graph we have the pseudograph so what is a pseudograph a pseudograph is a graph where at least one vertex will have self-looping type of edge so remember the self-loop or self edge we have discussed in the trivial graph type so this particular type of an edge where it connects to itself is called as a loop or kind of self-connecting edge so any graph that has this kind of a edge is called as a pseudograph so followed by the pseudograph we have the directed graph so what is a directed graph any graph is called as a directed graph where each edge has a direction associated with it so so far we have just discussed the edges which are connecting to one or the other vertex but there was no direction but here you can see that this particular edge has a direction that is from b to a not from a to b it is from b to a this type of edges which are directing the traversal of the graph are known as the directed graphs now followed by the directed graphs we have the regular graph so a graph is a regular graph where each vertex of the graph has the same degree now here you can see all the vertices have the same amount of degree that is the connection between all the other vertices so the degree of a is 3 so the degree of b is also 3 and the degree of d is c and similarly the degree of c is also 3 so what i mean to say is all of these vertices have the same degree that is 3. now we have the weighted graph so what is a weighted graph a weighted graph is where each edge holds some weight that denotes the traversal cost through those edges now here you can see that all the edges have a different weight the edge from a to b has the weight 5 and the edge from a to c has the weight 9 and the h from c to b has 2 and the edge a 2 d as 8 and finally c 2 d as 7 so all these values are the weight or the cost to traverse from a to another vertex flow so from a to b we have the cost five and a to c we have the cost nine and similarly c to d we have seven and so on now followed by the weighted graph we have the connected graph so what exactly is a connected graph a graph is said to be connected where each pair in the graph is connected followed by a connected graph we have the disconnected graph so it is a typical opposite of the connected graph a graph is said to be disconnected where each pair in the graph is not connected to each other now next we have the cyclic graph so a graph is said to be cyclic if it contains at least one cycle in a graph that is one complete traversal connection so a can be traversed again from traveling a to c c to d d to b and b to a again so this type of a graph is called as a cyclic graph now next we have the acyclic graph so it is the typical opposite of the cyclograph so here you cannot traverse to a again by traversing from a to c c to d and there is no connection between d to b so the complete cycle is not available here this type of graphs are called as acyclic graphs so moving ahead we have the graph representation so generally there are two different ways to represent the graph data structure they are using adjacency matrix and adjacency list so what is adjacency matrix so adjacency matrix is a sequential representation adjacency matrix is used to represent which nodes are connected to which node if there is an edge between two vertices then the value of the corresponding element of the graph is 1 otherwise 0. if there is any weighted graph besides then 0s and 1s we can store the weight of the h as that particular number suppose that there is a connection between a and b and it is represented as a weight of 5 then there is a connection so we will use the connection as true but we will not represent it as 1. instead we will use the weight that is 5 to represent it as 5 not as 1. if there is no weight then we will represent it as 1 and if there is no connection then we will represent it as 0. now undirected graph representation so here you can see how we have represented a graph so there is no connection between eight to a that is there is no loop so the value will be zero if there was a loop and if it was represented with a bit then we could have written a weight here since we do not have weight then the no connection is represented as 0 and a connection is represented as 1. we have a connection from a to b so we have represented as 1 and similarly to a to c so and so on now directed graph representation so the simple difference between the directed and undirected graph representation is we did not have a direction in the previous segment but here we do have directions so b is connected to a but a is not connected to b so we will write it as 0 because the control is traversing from b to a but not from a to b so we need to take care of the traversal of control so we are representing 0 and you can see from d to b we have one connection and the traversal is in the direction of d 2 b so we will have 1 there so here we have d and b so we have 1. so in that way we represent the directed graphs next undirected weight graphs so this was what we discussed before instead of zeros and ones we will represent the weight here so we do not have a connection between a to a so that is zero as usual but we do have a connection from a to b so we have represented it with a number that happens to be the weight of the edge and remember we do not have the direction here this is undirected weighted graph now if it were the directed weighted graph then we could have seen the direction and represented the number with the weight now after this let us look into the adjacency list so what is adjacency list adjacency list is a linked representation in this representation we maintain the list of its neighbors for each vertex in the graph every vertex of the graph contains the list of adjacency vertices area of vertices which have vertices indexed by each vertex number for every vertex the array element points to the linked list of the neighbors of the vertex so this might be a little complicated to understand so let us understand this using an example so directed graph representation implemented using linked list so this is the directed graph we are using so you can see that a is not connected to anything so we have ended the address of next location as x but b is connected to a and c is connected to a similarly d is also connected to a so that is how we represent the directed graphs using linked lists next we have directed graph representation using array so a is not connected to anything so we have represented as 0 and b is connected to b as well as a so we have 1 there and c is connected to b so c is also connected to a so we have 2 there d is connected to a c and b so we have 3 there now we have the graph traversal so graph traversal refers to the process of examining each edge and vertex in a graph graph traversing can be performed in two ways the first one is breadth first search or bfs algorithm bfs starts traversing the graph from root node and expose all the neighboring nodes then it selects the nearest node and explores all the new nodes queue data structure can be used in bfs algorithm so the following image depicts the epfs algorithm working it shows us the nearest node first then it traverses to all the other nodes so followed by bfs algorithm we have the dfs algorithm that is the depth first search algorithm dfs starts traversing a graph from the initial node of the graph and then it goes deeper and deeper until it finds the node has no child then backtrack from the dead end towards the recently explored nodes stack is used for bfs algorithms so this particular gif image can be considered as the graph traversal which is performed using dfs algorithms so if you don't know much about dfs and vfs algorithms don't worry about that those particular tutorial videos are added in the description box below you can go through it and understand bfs and dfs algorithms in a much better way now we will go through some of the applications of graphs so some of the major applications of graphs are used in the websites google maps and social media websites like facebook and some security systems and also software programming so with that we have come to an end of this tutorial if you have any queries regarding the topics discussed in this particular tutorial then please feel free to let us know in the comment section below and our experts will be happy to solve all your queries until next time thank you stay safe and keep learning hi there if you like this video subscribe to the simply learn youtube channel and click here to watch similar videos turn it up and get certified click here