Hello. Time flies, and in my second lesson, you will be dealing with different ways to represent graphs. Each has its own advantages and disadvantages. It's common to identify vertices not by names such as Natasha or Moscow, but instead by number. Knowing just two things about me, like Natasha and Moscow, you will still need my number. So let it go. That is, if you have a graph with v vertices, then you typically number them from 1 through v. Here is a graph with its seven vertices identified by numbers rather than names. The first way to represent a graph is an edge list, which is an array of ith edges. To represent an edge, you just use a pair of Frederick's numbers. If the edges have weights, you can add the further element to the array, given the edge's weight. For example, here is how you represent an edge list in pattern for our graph. Edge lists are simple. But if you want to find whether the graph contains a particular edge, you have to search through the edge list. If the edges appear in an edge list in no particular order, that's a linear storage for e edges. Another way to represent the graph is adjacency matrices, where a graph is v vertices, and adjacency matrix is a v times v matrix of 0s and 1s. Where the entry in row e and column g is 1, if and only if the edge from vertex e to vertex g is in the graph. If you want to indicate an edge weight, put it in the row e, column g entry and refer to a special value, perhaps null, to indicate an absent edge. Here is the adjacency matrix for our graph. With an adjacency matrix, you can find out whether an edge is present in constant time by just looking up in the corresponding entry in the matrix. For example, you can query whether edge from vertex 3 to vertex 6 is in the graph, by looking at the element in the third row and in the sixth column. So if there is a disadvantage of an adjacency matrix? Yep, more than that, there are two. First, it uses a v by v matrix even if graph is sparse and has relatively few edges. In other words, for a sparse graph, the adjacency matrix is mostly 0s and use lots of space to represent only a few edges. So this is inefficient. Second, if you want to find out which vertices are adjacent to a given vertex, for example vertex e, you have to look all v entries in row e, even if only a small number of vertices are adjacent to vertex e. Which is also inefficient. For an undirected graph, the adjacency matrix is symmetric. The row e, column g entry is 1, if and only if the row g and column e entry is 1. For a directed graph, the adjacency matrix need not be symmetric. The final way to represent graphs is adjacency lists. Representing a graph, these adjacency lists combines adjacency matrices with edge lists. For each vertex e, you store an array of vertices adjacent to it. You typically have an array of v adjacency lists, one adjacency list per vertex. Here is an adjacency lists representation of our graph. Vertex numbers in an adjacency list are not required to be in any particular order, though it's often convenient to list them in incremental order, as in this example. You can get to each vertex adjacency list just by its index in an array. To find out whether an edge from vertex e to vertex g is present in the graph, you go to the e's adjacency list and then look for g. How long does that take in the worst case scenario? Any ideas? Don't be shy, nobody is going to be mad. The answer is the number of vertices connected to vertex e. Because that's how long e's adjacency list is. This number is the number of connections, and could be as high as v minus 1, if e is adjacent to all other v minus 1 vertices. Or as low as 0, if e is isolated with no edges. In an undirected graph, vertex g is in vertex e's adjacency list, if and only if e in g's adjacency list. How much space do adjacency lists take? This much? You have v lists, and also each list could have as many as v minus 1 vertices. In total, the adjacency lists for an undirected graphs contain 2 times e elements. Why 2 times e? Each edge from vertex e to vertex g appears exactly twice in the adjacency lists, once in e's list and once in g's list. And the second reason is there are e edges. That's why adjacency lists have 2 times e elements in total. For a directed graph, the adjacency lists contain a total of e elements, one element per directed edge. To sum up, now you know there are different ways to represent graphs, an edge list, an adjacency matrix, and adjacency lists. Also, you know there are advantages and disadvantages connected to each of them.