Comparison Of Graph Representations

Loony Corn
A free video tutorial from Loony Corn
An ex-Google, Stanford and Flipkart team
4.2 instructor rating • 73 courses • 129,047 students

Lecture description

Compare the adjacency matrix, adjacency list and the adjacency set in terms of space and time complexity of common operations

Learn more from the full course

From 0 to 1: Data Structures & Algorithms in Java

Learn so you can see it with your eyes closed

14:58:54 of on-demand video • Updated April 2019

  • Visualise - really vividly imagine - the common data structures, and the algorithms applied to them
  • Pick the correct tool for the job - correctly identify which data structure or algorithm makes sense in a particular situation
  • Calculate the time and space complexity of code - really understand the nuances of the performance aspects of code
English [Auto] Give feeling great. AP How the adjacency matrix adjacency list and the adjacencies set implementations of a graph look. Now we come to the point when do we use one representation over another. What are the advantages of using an indecency matrix C against using an adjacency set. And the other way around that's what. Now there are specific instances vessels and representations would matter. And let's take a quick look at a comparison between the adjacency matrix and the adjacency list of the adjacency set representation. He'll be Plup get the bodies and see the list and the adjacency set because over all the representations are very similar. It's only a small difference. The adjacency matrix representation of a graph looks extremely even when a graph is very connected and by very connected I mean when there are many nodes in the graph which are connected to many other nodes in the graph directory if there isn't a if there are a huge number of edges in that graph there a single note can be connected to many other then and adjacency matrix representation is the most efficient and they are best at. If you think about it and adjacency matrix then the number of work to see in your graph is v requires the square space to represent all those to cease and all the interconnections between the vortex. This extra space is only justified when the number of connections are very very large. So you would typically use an adjacency matrix representation when your graph is very connected and has a huge number of connections. The converse is also obvious if you have a boss graph that is which has few connection between the nodes. Then this is most efficiently represented using an adjacency list or an adjacency set a sparse graph is one which has very few connections between the work to cease the number of connections are small and of course this is subjective What do you mean by large number of connections or small number of connections. That's the decision which you have to implement in Bloomington a sparse glasses have ever more efficiently represented using an decency list or energies and the SEC this does not have the overhead of square Squarespace being allocated upfront to represent the connections between vertices. You'll only add one note to the adjacency set or list of another node if a connection actually exists. This is what makes this representation efficient. Let's now see a quick comparison of common operations across the adjacency matrix adjacency list and the adjacency set. Now let's show you that even if the number of edges that are present in a graph. So we in the same graph across all three of the implementations is the number of edges and v is the number of vertices. The efficiency of all the operations we performed will be measured in terms of the number of edges or B the number of seats. So let's see let's see the operations and the efficiency metrics we are using to compare these three. The very first thing is how much space do these representations occupy. So we'll be measuring them along the axis of space. You'll also measure how long it takes to perform that is edge present operation say we are given one more X and we want to see if there is an edge present from that vortex saving one to another would be. How long does that operation take. And lastly you want to compare how long it takes to iterate over the edges on a particular box. So we know about vexedly that we are interested in. How long does it take us to read or we're all just incident on that vortex. Let's start with the adjacency tricks. It's very clear based on the representation is that if you have viveur to seize the space required to store the adjacency matrix is we squish V rules and we call them we Squarespace is required now to check that an edge is present is very very fast. It takes constant pain or that of one to check whether an edge is present from vortex Leeman what takes me. It's a simple look up into the decency matrix. Again very straightforward. Now if you had to read all all ages on about X the it would AQ V. This is because you'd read all what all the cells in that particular table and check that no one was present in any of those sets. So you'd have to look at all the cells in a row. And that's why it takes you v. That is the complexity. Let's see how an adjacency list performs the space requirements for a decent C list representation is eat less. This is because if the vertex is a node so that accounts for the V space and every edge is represented by another vertex in the adjacency list of the vertex that it's connected to. This means the space requirements for an adjacency list is either plus the if we have to check for that an edge is present between vertices Beaven and B to the complexity of this operation is order of degree of V that degree of me is the number of edges incident on B. Or the number of edges that reconnects to. This is because we'd have to iterate through all the work to cease on the adjacency list. We'd have to go through it one by one and check whether V-2 is present in the adjacency list of Lieben. That is why the complexities order of a degree of the and lastly the time complexity to iterate over all the adjacent vertices of any vertex is degree of D. So that means the time complexity to iterate over a just what X is again a degree of v v is the vortex and degree is the number of edges that that incident on that what makes Let's see these metrics for a decency set the space occupied by an adjacency of set representation is exactly the same as an adjacent de-listed representation. It is. Eat less eat eat is the number of it just in the graph and B is the number of the seas in the Gulf. The difference between an adjacency list and an adjacency set comes in the time complexity to check whether an edge is present between vertex lieben and B. If you notice and adjacency set representation is much faster. In performing this check the complexity is order of log of the degree of the vortex v the order of log of the number of edges incident on B is the time it takes to check whether an edge is present. What's the reason for this difference. A list is simply a list. We have to iterate through all elements to find whether it contains a particular element in the case of a set. We can have a much better implementation maybe it's a binary search tree. For example a set can be implemented as a binary search tree. And in that case to look up a particular element in a binary search tree the time taken is a log of an event and if the number of elements in the binary search tree. So a set representation of adjacent purposes is much more performant when we are trying to find whether there's an edge linking one vertex to another. And lastly the time taken to read over the edges on what X is the degree of V that that degree represents the number of edges incident on the vertex be exactly the same as in the case of an adjacency list this table can be a quick look up for you to figure out what the what representation is the best for you under all the circumstances which operation is it that you want to be fast. Can you read off speeds with the efficiency in looking up a particular edge. These are the factors which go into your decision of whether to choose an adjacency list adjacency set or an adjacency matrix representation of a graph.