GRAPH TERMINOLOGY & TYPES OF GRAPHS - DATA STRUCTURES

[Music] hello friends welcome back to our channel so in the previous session we have a beauty of the trees concept and now from today's session we'll go with the another concept that is called graphs so graphs in a data structure is also similar to a trace but here we can have explosive slew right so whereas in a tree we can't go with a closed loop but here graph can have a closer look and here a graph is defined as a set of V comma E face where V is a set of vertices E is the set of inches so a graph can be defined as a set of vertices and a set of edges so every graph will be having a vertices and edges so vertices can be represented as circles and these are also known as moves edge is represented as lines and also sorry silence which are corrected connecting two vertices or groups to vertices all rows so a graph can be defined as vertices and edges so vertices are represented as circuits and the H is represented in the lines so let us take an example for this graph this is simple graph this can be called as a graph so here in B and C are vertices or nodes and the connectivity between the vertices a B and a C R so a B a comma B comma C these are called edges so it just means the connecting two roots so this can be considered as a graph and if you have a line between this B and C for be see you know also forms they pay the pitch is also an edge so this is also a graph but not a trick so in the absence of this one and the absence of this edge this can be either a graph or a thing right so if you have an edge between B and C it is a closed loop it is a closed surface right it's the forms a cycle so if if it forms a cycle it cannot be called as a tree it is a graph that's the only difference between the degree and a graph right so here the nodes and edges so let us see first let us see the terminology your graph and then we'll go with the types of graphs different kinds of graphs graphed our knowledge the first one is more first one is an old which is nothing but the vertices and present it as a circle and then edge which is a line it's a connection between two different nodes right the third one is it is a nose it just sent notes so if you consider any edge that means there will be so let us take an example yes B and similarly a C similarly B C so there are three edges right three edges so for this edge the node a and B are the starting and ending points for this edge the node be the starting point C is the ending point for this edge yeah and C are the end points for this particular age so that's why the it is in most means which connects an edge those modes we call it as adjacent nodes in this example a and B are adjacent nodes similarly and see an adjacent nodes similarly B and C are adjacent nodes so this is how we can have the edge so degree of a load so how to calculate the degree of a node so it represents the number of edges corresponding to that particular node can be considered as a degree of truth number of edges connected to that global for example let us take this one yay B and C know the key of e a big enough name what is the degree of a so yeah is having tools so degree n is 2 so degree of B B is also having to lose so degree of B is 2 similarly degree of C C is also having roots so in the houses of this one so between of a is 2 degree of B is 1 degree of C is 1 because b is having only one load towards the a C is also having one walk towards it so that's why we call this degree as the number of edges connected to the flow sizes of the graph size of a graph so size of your graph represents the total number of edges the total number of edges in graph can be considered as the size of a graph so let us take this example so there are three edges for in this graph so sizes of this graph is 3 so size is 3 for this example only 2 inches are there so the size for this graph is 2 so the total number of edges in the graph represents the size of the graph path path means the sequence of vertices so from starting node to any node so sequence of vertices from social to destination so slow - and the destination mode right so let us take an example here so if you take this one a b c d so if you want the path from A to C right you hate to see so this is the source this is the destination the path will be a - B - C or E - D - C so whatever the edges or the sequence of vertices from source in order to destination load so here the source is here and the destination is C so we can have that the path can be a to B B to C or a to D D to C right so this is for a path ok then so these are the basic terminologies we need to know before starting the Deaf's concept so hope you understood the definition of the graph so graph is a set of vertices and edges right now will go there are different kinds of graphs different types of graphs types of graphs so first one the first one dr. Graf and undirected graph directed and undirected see coming to this undirected so there will be no directions specified on the edges so let us take an example so a B C D and a now say one more thing so this is also again which contains vertices and edges right so in this example there is no directions specified all the edges so we can travel from A to B or B - yes so here J comma B is equal to B comma Y right similarly B comma C is equal to C comma Y so that means there is no direction specified in this graph so we can consider that a and B A to B is one traversal and B to a is another browser so in both the directions we can have right in the both the directions in the we can travel so come to the directed graph as the name indicates so every edge will be having a specific direction that means so this we can call as say bi-directional right this we can call it as a unidirectional so only in only one direction we can travel through the edges okay see let us take an example here a b c d so this is called a directed graph because so here every edge is specified some direction so we're in one direction we can turn so there is a lower between U and V so J and B is not equal to become again because here we have specified the direction from A to B naught from B to get so he'll be to C so there actually is only from B to C so B is a starting point and C is the ending point but not the vice versa right so this is the only difference between the directed graph and undirected graph right so hope you understood it's a bi-directional it's a UV direction it's a bi-directional let's say you need a directional so only one thing we can have so this is a difference between directed graph and undirected death now you go with the another another kind major death and unweighted graph weighted and unweighted so here we have to specify some weight or a cost for the Aged see let it be either it may be a directed graph on the undirected graph so there is no any cost specified for that so here we can specify some cost for every age so in order to tell from A to B the cost is 2 that means here we are specifying some weight age for every age so if you specify some braids age for every age that is called a weighted graph so here bed is specified for every inch no weight is specified so either it will be a directed or in undirected whatever it may be so in the director also we can have the weighted and in the undirected also we can have the unweighted right so whatever it may be if if the edge is having any weight or the cost then the graph is called as a weighted graph and if the graph doesn't have any cost or weight specified from the edge that is for an unweighted graph so this is a difference between weighted graph and unweighted there right now before the third one we loaded the thermal cycling graph and if I click graph cyclic and ascending so cyclic means it should perform the loops loot means so if you find the path from source to destination the starting point and the ending point should be the same vertices so if you can check this one find the part here so here you can find so A to B B to C C to B and again D to a so the starting weight is and end vertex motorcy so that means it forms a cycle it forms a cycle right so hope you understood this one so if the starting where it is and there any murders are same then that is that from the cycle and if our graph consists of the cycles then it is called a cyclic graph if our graph doesn't have a cycle then that is called a cyclic there C so here it doesn't form same cycle it doesn't forms any cycle so this is called a cycle so similarly we can say this one so if any there doesn't have the moves doesn't have the loop that we can call as an aside Li so in their psychic also this graph can be either directed or undirected it can be baited or omitted so whatever it may be if our graph consists of these cycles then we call it as a circuit if it doesn't have any cycles it is called as a cyclic graph right so hope you understood this one so when it did unweighted directed undirected cyclic and acyclic so these are the different kinds of graphs available in our data structure right and also we have seen a few terminologies so what is better than H what is meant by a graph and what is meant by a node what is that by pop and degree how to find the degree how to find the size and everything we have seen in this session so if you are having any doubts regarding this terminology and different kinds of graphs so feel free to post your notes and one section so that definitely I will try to clarify all your doubts and if you really understood position like my sessions share my sessions with your friends and don't forget to subscribe to our channel thanks for watching thank you very much

Channel: Sundeep Saradhi Kanthety

Views: 46,429

Rating: 4.9322033 out of 5

Keywords: sundeep, saradhi, kanthety, data structures, arrays, lists, stacks, queues, trees, graphs, primitive, non primitive, linear, non linear, linked lists, ds fundamentals, ds basics, nodes, interview, placements, cse, edge, connection, leaf node, internal, depth, height, level, path, degree, root node, GRAPH TERMINOLOGY, graps, weighted graph, cyclic graph, directed graph, vertices, edges, undirected, acyclic, unweighted, types of graps, kinds of graphs

Id: 20xf98xWD-0

Length: 19min 10sec (1150 seconds)

Published: Mon Aug 12 2019