Transcript:

Hi, I’m Joe. And in this video, I’m going to walk you through two different ways to implement a graph. Then I’ll walk you through some of the pros and cons of each and I’ll show you how to implement these two methods in Python. The first way to implement a graph is using an adjacency list. Let’s look at this undirected graph. It has five vertices and a few ridges connecting them. An adjacency list is actually a set of adjacency lists because each list is stored in its own vertex. Therefore, Vertex A maintains a list of directly connected neighbors, Thus node. A has neighbors, B C and E Node B and C have neighbors. A as can be seen here. This will be stored in each node. Each vertex stores, its own adjacency list. The other way is to use an adjacency matrix. The adjacency matrix is A 2-dimensional array and it stores a 0 where there is no edge or 1 where there is an edge. For example, we can see that there is an edge from A to B and from A to C As expected since it is an undirected graph. The table is symmetrical in the diagonal. So from A to B is 1 and from B to A is also a 1 So there is an adjacency matrix per graph and it is in the object graph. What if you have a weighted edge graph on an undirected graph? Well, it is very easy to implement weighted edges with an adjacency matrix. Instead of putting a 1 for each edge, you put the weight of the edge. So it’s easy since you can use the same table, just fill in with the weight or cost of each edge. Also, you can implement in weighted edges with adjacency lists, but it’s a bit trickier. So if you have a directed graph, it is very easy to implement using adjacency lists. Here Vertex A has an edge exiting at C So in the adjacency list of A we present only one neighbor C Because it is the only neighbor that can be reached directly from A. So for each vertex, we list all of its outgoing edges in its adjacency list. In an adjacency matrix, it is the same thing. We put 1 wherever we have an edge coming out of a vertex. Which is better. Before answering this question, let’s look at some other characteristics of graphs. In a dense graph, the number of edges is more or less equal to the number of vertices squared. In other words, every vertex in the graph is connected to almost every other vertex. So you have a very large number of edges compared to the number of vertices. A sparse graph is a graph where E is roughly equal to V Or the number of edges is approximately equal to the number of vertices like in this image. There are a lot of possible edges that aren’t actually there Well. Look at something else before. We answer this question. An adjacency matrix takes up the V-grid space. This is an important fact. The amount of memory space required for this adjacency matrix will be V-grid, regardless of the density of the graph. For a very sparse graph, it will still take the same amount of space. Who cares about space in our tiny 5-vertex sample? But if you have a large graph with 10,000 or more vertices, the matrix takes up a huge amount of space. The adjacency lists are therefore better when you have a sparse graph because it will be faster and less space. But the downside for adjacency lists is that they are slower for very dense graphs. And the adjacency matrix is better for a dense graph. It will be faster and the complexity of the space is the same as for a sparse graph. Another advantage is that it is easier to implement for weighted edges. The downside of the adjacency matrix is that it uses more space, especially for large sparse graphs. For graphs with a lot of vertices, but relatively few edges, the adjacency matrix may be a bad choice. Depending on the nature of your graph, you need to decide Which one is the bestchoice?