6.1 Graph Representation in Data Structure(Graph Theory)|Adjacency Matrix and Adjacency List

hi guys welcome back today I am going to discuss with here with you how to represent a graph in computer I'm going to discuss with you the most popular two methods for representing a graph in computer ok the two methods are first one is at the sensing matrix and second one is at the sensei list first one yields this matrix and second one is at this NC list these are the most popular two methods okay although we have more method that is I guess multi list is also there but I am going to discuss with you these two methods adjacency matrix and Addison C list now how to represent a graph in computer see this is the pictorial view you can easily draw a graph on this whiteboard like this but when you are going to represent a graph in computer then you have to use something okay you have to use some methods to represent this graph in computer so these are two methods then one is matrix and one is list first one is I am going to discuss with you this this method Edison C matrix so matrix is simply in mathematics you know matrix is what M cross n where m is the number of rows and n is number of column something like this number of rows and number of columns so in this case let us take this example this one is our graph and you are supposed to represent this graph using this adjacency matrix then how you will represent it this adjacency matrix would be n cross n matrix and where n is what number of vertices in the graph okay now how you will represent it this one is our matrix there should be n cross n matrix where n is what number of vertices how many number of vertices 1 2 3 4 5 then 1 2 3 4 5 number of rows would be there and five number of columns would be there this one should be 5 cross 5 matrix now we are supposed to fill out these entries now see 1 2 1 is there any loop is there any loop in this graph loop means the edge would start from the same node and would add end on the same node like this this would be a loop if you have say check out you have any loop in this graph no you don't have any loop that's why the diagonal elements would be 0 3 2 2 3 4 2 4 there is no edge and 5 2 5 no edge okay now check out 1 2 2 1 2 2 obviously it is undirected graph ok so this edge would be considered as 1 to 2 also and 2 to 1 also okay one two - yes we have edge between 1 to 2 then you can write down 1 1 2 3 no we don't have any edge direct edges between 1 2 3 that way that's why it is 0 1 2 4 yes we have 1 2 4 we have an edge 1 2 5 no we don't have now 2 2 1 2 2 and yes we have because this edge is what undirected edge so this is also considered from 1 to 2 and 2 to 1 by 2 2 3 2 2 3 yes we have 2 to 4 yes we have 2 to 5 no we don't have any direct or any edge between 2 to 5 3 2 1 you have 3 2 1 no we don't ow 3 to 2 yes we have 3 2 to see this one three to three no three to four yes we have three to five yes now four to one yes for two - yes this one for two three yes four to five yes five to one no five to two no five to three yes we have and five to four yes we have fine so you can simply write down like this okay now you simply write down the definition of this addition C matrix is what it is a matrix you can say a n cross n we are representing the matrix with a and n where n is the number of vertices n would be the number of rows and n will be the number of columns and how you will fill these entries a of I J this one is J is equal to 1 if I and J are at this end ok see suppose this one is I and this one is J let us take this one is I we are taking and this one is J so you write down a of IJ 1 if I and J are at the st. 1 and 2 are adjacent to each other that is why we are taking 1 2 2 is 1 a of IJ that is a of I 1 and J is suppose to this one is 1 and I 2 and J is equal to 1 this one is also 1 okay otherwise you we would write here 0 all right now next we'll discuss what is adjacent see list see now this would be as the name suggests we will have we are going to have linked lists fine and how many linked list would be there for each what takes one linked list would be maintained like this in this case we are having how many vertices five I guess 1 2 3 4 5 1 2 3 4 5 number of vertices are there fine for each what takes one linked list would be there in that linked list will have will contain the adjacent node to this node fine like this see now suppose will be a first one is what is number of node is one how many at the center node are there two one one is two and one is four then one linked list would be maintained containing two and four now come to the second note this one second how many addition node are there one three and four this would be one three and four now for three also one linked list would be there and it would contain how many number of adjacent to node are there two three one is to one is four and one is five one is to one is four and one is five four four also we have one now we have what two we have what three and five see one two three and five and four five we have what three and four only three and this one is for how many linked lists would we maintain one two three and four and five how many number of vertices 1 2 3 and or four and five the number of vertices total number of vertices in the graph with Linea po maintain Kenyan number of linked list for each node fine now this is the adjacency list using this list you can a present this graph and this is how you can represent this graph using addition C matrix now when you're supposed to calculate the time complexity now when you represent a graph using this method adjacency matrix then what would be the time complexity order you're sorry you can say the space complexity space complexity would be theta n square in this case right because mat this is matrix n number of rows and n number of columns the space complexity is what n square here it is there C five into five matrix v square five is what number of vertices that is and where n is what number of vertices and for representing a graph using this a distance a list the space complexity would be theta n plus 2 e C and 1 2 3 4 5 these are number of what what s is why we have written this plus 2 e because the one you happy there Co see this one is one edge from one to two fine but you have written this edge two times in this list two times went from 1 2 to one edge you have written and from two to one also from two to one also so two times we have written this edge in this list same you can say with you can say take one to four this one is one edge but you have written this two times one to four fine because 4 is adjacent to one so we have written in this linked list also plus 4 to 1 also four to one like this so every Edge has been written two times that's why we have written here n plus 2 we the space complex that is this one for Addison see a nest and this one is theta n square for Addison when you represent this graph any graph using a distance e matrix so see it would be better to use this adjacency matrix to represent a graph when the graph is dense graph sometimes they can ask you this type of question in case of dense graph it's better to use adjacency matrix to represent that graph and when the graph is sparse sparse graph then it would be better to use this what adjacency list because see when a dense graph means almost or you can say each node is connected with each other node you can say you can take example of a complete graph like this suppose we have four nodes and every node is connected with every node and five nodes every node is connected with every other node like this then in that case it is better to use this matrix okay and when something like this one a very few number of edges are there between these vertices then better to use this adjacency list and this is the space complexity for representing these graph ok so that's all about you know some you can say the basics of how to represent a graph in computer these are the most popular methods I am NOT saying that these are the only two methods to represent a graph but I am just I have just discussed the most popular methods to represent this graph okay so I'll see you in the next video till then bye-bye take care

Channel: Jenny's Lectures CS IT

Views: 876,682

Keywords: what is graph, graph data structure, adjacency matrix, graph representation, adjacency matrix in data structure, graph implementation in c, adjacency list representation of graph in c, tree and graph, introduction to graphs, graph terminology in data structure, types of graph in data structure, ugc net computer science preparation, GATE computer science classes, engineering, algorithms, data structure, jennys lectures, study material, best youtube channels

Id: 5hPfm_uqXmw

Length: 12min 11sec (731 seconds)

Published: Tue Feb 19 2019