As we begin to implement a graph, we first need to talk about the abstract data type of a graph and understand what functionality we need to be building against, so we can actually make useful class. Let's look at this. So, inside of our graph, we're going to have a sequence of vectors that we're going to store, a sequence of edges, and some data structure that maintains the relationship between these vertices and these edges. In doing that, we're going to define at least eight different functions on our graph. The first one is we need to be able to insert a vertex given some key. The second thing is we need to insert an edge between two vertices, and given some data that we might associate with that edge. We, of course, need to remove the vertex we inserted earlier, and we need to remove the edge. We also need to be able to ask our graph, what are the incident edges given a vertex? We need to see if two vertices are adjacent. So, whether or not, there's an edge between these two vertices, and then if our graph has directional edges, where a may point to b, but b doesn't point to a. We need to know the origin and the destination of an edge, if the edge is directional. This is the basic ADT that we're going to be looking at as we look at different implementations of the graph. The first implementation we're going to look at is, what is referred to as the edge list implementation. This is the naive implementation that allows us to just get a graph going very quickly. We'll discuss improvements on this implementation after understanding how it works. In the edge's implementation, we're simply going to have a list of vertices and a list of edges maintained in a vector or a hash table like data structure. So, here, we have on this simple graph u, v, w, and z. You can see in our vertex list, we have that edge u, or that vertex u, v, w, and z. In our edge list, we're simply going to maintain a list of edges and have the vertices that they connect as elements as part of the edge list. So, u and v are connected through edge a. Edge b connects v and w, edge c connects u and w, and edge d connects w and z. Now, we understand what it means to be an edge list. Now, we can look at operations that we might perform on this edge list. The first thing we might want to look at is how to insert a vertex. To insert a vertex is really quite simple. If I want to add a new vertex called k, that vertex k can simply be added to the end of my array or hash table here. So, this is an "O of one" operation: O(1) because simply, I'm adding it to the hash table or adding into vector. Because we might need to expand the vector, we can say this is actually O(1) amortized time. The remove vector [vertex] operation is going to remove a vector [vertex] from this list. Again, thinking about this in terms of a hash table we can make a hash table implementation of this in O(1) time. Checking if two nodes are adjacent gets a little trickier. So, if we have vertex one and vertex two, checking if they're adjacent requires us to go through the entire edge list. So, we need to look at every single element in our list and say, "Are these two vertices adjacent?" To do that, we say is w and z adjacent? Well, they're not adjacent edge a, or edge b, or edge d. Only edge d is it done that way. So, here we have an O of n algorithm. Because we have to go through and look at every single edge before we can find out whether two vertices are adjacent. So, this is going to run in order of how many edges there are on the graph. Likewise, when we do calculate the number of incident edges, we also need to go through the entire edge list. So, this is also going to be an O of m operation to check whether or not, or to get the collection of all of the edges that are incident to a given vertex. We don't know where that might exist inside the edge list. So, these are the four key operations that you're going to see on a graph. Here, the inserted removal runs in constant time, but you actually find things about the property of the graph and how connected they are. It's going to run in orders of the entirety number of edges in the graph. So, this can become very, very large in very large graphs and may not be a desirable outcome. In some cases, that edge source is the right implementation to use, and we're going to evaluate this implementation with other implementations as we dive into more implementations of the graph, and we'll do that next. So, I'll see you there.
