Main content

## Computer science

### Unit 1: Lesson 10

Graph representation# Representing graphs

There are several ways to represent graphs, each with its advantages and disadvantages. Some situations, or algorithms that we want to run with graphs as input, call for one representation, and others call for a different representation. Here, we'll see three ways to represent graphs.

We'll look at three criteria. One is how much memory, or space, we need in each representation. We'll use asymptotic notation for that. Yes, we can use asymptotic notation for purposes other than expressing running times! It's really a way to characterize

*functions*, and a function can describe a running time, an amount of space required, or some other resource. The other two criteria we'll use relate to time. One is how long it takes to determine whether a given edge is in the graph. The other is how long it takes to find the neighbors of a given vertex.It is common to identify vertices not by name (such as "Audrey," "Boston," or "sweater") but instead by a number. That is, we typically number the vertical bar, V, vertical bar vertices from 0 to vertical bar, V, vertical bar, minus, 1. Here's the social network graph with its 10 vertices identified by numbers rather than names:

### Edge lists

One simple way to represent a graph is just a list, or array, of vertical bar, E, vertical bar edges, which we call an

**edge list**. To represent an edge, we just have an array of two vertex numbers, or an array of objects containing the vertex numbers of the vertices that the edges are incident on. If edges have weights, add either a third element to the array or more information to the object, giving the edge's weight. Since each edge contains just two or three numbers, the total space for an edge list is \Theta, left parenthesis, E, right parenthesis. For example, here's how we represent an edge list in JavaScript for the social network graph:```
[ [0,1], [0,6], [0,8], [1,4], [1,6], [1,9], [2,4], [2,6], [3,4], [3,5],
[3,8], [4,5], [4,9], [7,8], [7,9] ]
```

Edge lists are simple, but if we want to find whether the graph contains a particular edge, we have to search through the edge list. If the edges appear in the edge list in no particular order, that's a linear search through vertical bar, E, vertical bar edges. Question to think about: How can you organize an edge list to make searching for a particular edge take O, left parenthesis, \lg, E, right parenthesis time? The answer is a little tricky.

### Adjacency matrices

For a graph with vertical bar, V, vertical bar vertices, an

**adjacency matrix**is a vertical bar, V, vertical bar, times, vertical bar, V, vertical bar matrix of 0s and 1s, where the entry in row i and column j is 1 if and only if the edge left parenthesis, i, comma, j, right parenthesis is in the graph. If you want to indicate an edge weight, put it in the row i, column j entry, and reserve a special value (perhaps`null`

) to indicate an absent edge. Here's the adjacency matrix for the social network graph:In JavaScript, we represent this matrix by:

```
[ [0, 1, 0, 0, 0, 0, 1, 0, 1, 0],
[1, 0, 0, 0, 1, 0, 1, 0, 0, 1],
[0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 1, 1, 0, 0, 1, 0],
[0, 1, 1, 1, 0, 1, 0, 0, 0, 1],
[0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
[1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
[1, 0, 0, 1, 0, 0, 0, 1, 0, 0],
[0, 1, 0, 0, 1, 0, 0, 1, 0, 0] ]
```

With an adjacency matrix, we can find out whether an edge is present in constant time, by just looking up the corresponding entry in the matrix. For example, if the adjacency matrix is named

`graph`

, then we can query whether edge left parenthesis, i, comma, j, right parenthesis is in the graph by looking at `graph[i][j]`

. So what's the disadvantage of an adjacency matrix? Two things, actually. First, it takes \Theta, left parenthesis, V, squared, right parenthesis space, even if the graph is **sparse**: relatively few edges. In other words, for a sparse graph, the adjacency matrix is mostly 0s, and we use lots of space to represent only a few edges. Second, if you want to find out which vertices are adjacent to a given vertex i, you have to look at all vertical bar, V, vertical bar entries in row i, even if only a small number of vertices are adjacent to vertex i.For an undirected graph, the adjacency matrix is

**symmetric**: the row i, column j entry is 1 if and only if the row j, column i entry is 1. For a directed graph, the adjacency matrix need not be symmetric.### Adjacency lists

Representing a graph with

**adjacency lists**combines adjacency matrices with edge lists. For each vertex i, store an array of the vertices adjacent to it. We typically have an array of vertical bar, V, vertical bar adjacency lists, one adjacency list per vertex. Here's an adjacency-list representation of the social network graph:In JavaScript, we represent these adjacency lists by:

```
[ [1, 6, 8],
[0, 4, 6, 9],
[4, 6],
[4, 5, 8],
[1, 2, 3, 5, 9],
[3, 4],
[0, 1, 2],
[8, 9],
[0, 3, 7],
[1, 4, 7] ]
```

Vertex numbers in an adjacency list are not required to appear in any particular order, though it is often convenient to list them in increasing order, as in this example.

We can get to each vertex's adjacency list in constant time, because we just have to index into an array. To find out whether an edge left parenthesis, i, comma, j, right parenthesis is present in the graph, we go to i's adjacency list in constant time and then look for j in i's adjacency list. How long does that take in the worst case? The answer is \Theta, left parenthesis, d, right parenthesis, where d is the degree of vertex i, because that's how long i's adjacency list is. The degree of vertex i could be as high as vertical bar, V, vertical bar, minus, 1 (if i is adjacent to all the other vertical bar, V, vertical bar, minus, 1 vertices) or as low as 0 (if i is isolated, with no incident edges). In an undirected graph, vertex j is in vertex i's adjacency list if and only if i is in j's adjacency list. If the graph is weighted, then each item in each adjacency list is either a two-item array or an object, giving the vertex number and the edge weight.

You can use a for-loop to iterate through the vertices in an adjacency list. For example, suppose that you have an adjacency-list representation of a graph in the variable

`graph`

, so that `graph[i]`

is an array containing the neighbors of vertex i. Then, to call a function `doStuff`

on each vertex adjacent to vertex i, you could use the following JavaScript code:```
for (var j = 0; j < graph[i].length; j++) {
doStuff(graph[i][j]);
}
```

If the double-subscript notation confuses you, you can think of it this way:

```
var vertex = graph[i];
for (var j = 0; j < vertex.length; j++) {
doStuff(vertex[j]);
}
```

How much space do adjacency lists take? We have vertical bar, V, vertical bar lists, and although each list could have as many as vertical bar, V, vertical bar, minus, 1 vertices, in total the adjacency lists for an undirected graph contain 2, vertical bar, E, vertical bar elements. Why 2, vertical bar, E, vertical bar? Each edge left parenthesis, i, comma, j, right parenthesis appears exactly twice in the adjacency lists, once in i's list and once in j's list, and there are vertical bar, E, vertical bar edges. For a directed graph, the adjacency lists contain a total of vertical bar, E, vertical bar elements, one element per directed edge.

This content is a collaboration of Dartmouth Computer Science professors Thomas Cormen and Devin Balkcom, plus the Khan Academy computing curriculum team. The content is licensed CC-BY-NC-SA.

## Want to join the conversation?

- "How long does that [checking for membership in the adjacency list] take? The answer is $\Theta(d)$." If you store the adjacency lists in sorted order, though, then wouldn't it be $\Theta(\lg d)$, using binary search?(12 votes)
- Agreed, if the list of neighbors is implemented as an array, and that array is sorted then determining membership is Θ(log(d)), using binary search.

However, if the array is unsorted, or if the list of neighbors is implemented as a linked list (both are typical implementations) then determining membership is Θ(d), as we need to look at every item in the list before deciding that something is not in the list.

In the article they mention "Vertex numbers in an adjacency list are not required to appear in any particular order", which implies the analysis is with regards to unsorted implementations.

Whether you would want to use a sorted version or not would depend on your application. You might get the sorting for free (i.e. if your method of constructing your graph leads to naturally sorted adjacency lists), or you might have to pay an additional cost in sorting the adjacency lists. Whether the cost outweighs the benefits depends on your application.(17 votes)

- Hi,

I was reading this page, but not everything is totally answered.

You said that you compare all different representations with the 3 cases:

1) memory or space requriements to store edges

2) determination time whether a given edge is in the graph

3) finding the neighbors of a given vertex.

The 3 point is not really answered for any representation or I am missing something?

Thank you very much.(8 votes)- For finding the neighbours of vertex v:

Edge List: O(|E|)

If the list is unsorted you need to check every edge to see if it comes from v

For a complete graph (where every vertex is connected to all other vertices) this would be O(|V|^2)

Adjacency Matrix: O(|V|)

You need to check the the row for v, (which has |V| columns) to find which ones are neighbours

Adjacency List: O(|N|)

where N is the number of neighbours of v

You need to iterate through the list for the vertex v, which has N neighbours

v could have up to V-1 neighbours, so we could also say it is O(|V|)

Hope this makes sense(14 votes)

- Can anyone explain the following

For an undirected graph, the adjacency matrix is symmetric: the row ii, column jj entry is 1 if and only if the row jj, column ii entry is 1. For a directed graph, the adjacency matrix need not be symmetric.

I dont understand the "For a directed graph, the adjacency matrix need not be symmetric"(4 votes)- Consider this matrix:
`0 1 2`

1 0 5

2 5 0

Notice the diagonal of 0s from the top left corner to the bottom right corner. The half of the matrix above and to the right of the diagonal is a mirror image of the the half below and to the left of the diagonal. We can say that this matrix is symmetric about the top left to bottom right diagonal.

In general, if it is true that every element at row i and column j is equal to the element at row j and column i, then the matrix will be symmetric about the top left to bottom right diagonal.

In an adjacency matrix the element at row i column j is 1 if there is an edge from vertex i to vertex j, otherwise it is 0. An undirected edge between i and j lets you travel from i to j and from j to i. So we can represent an undirected edge as two directed edges: one from i to j, and another from j to i. So, for an adjacency matrix, an undirected edge between i and j would have a 1 at (i,j) and a 1 at (j,i). If all the edges were undirected then every element at row i and column j would be equal to the element at row j and column i. Thus a matrix with only undirected edges would be symmetric about the top left to bottom right diagonal.

On the other hand, for a graph with directed edges, just because you can travel from i to j, doesn't mean you can travel from j to i. So, for a directed graph, it won't always be the case that the values at (i,j) and (j,i) are equal. Thus it won't always be symmetric about the top left to bottom right diagonal.

Hope this makes sense(12 votes)

- how is adjacency list space Θ(V + E)?(6 votes)
- The adjacency list contains:

-1 array per vertex, for a total of V arrays (we are only considering the space for the array pointer, not the contents of the array).

-Each directed edge is contained once somewhere in the adjacency list, for a total of E edges (a bidirectional edge is just 2 directed edges, so if we are using bidirectional edges it would just be 2E ).

V+E is Θ(V + E)(4 votes)

- What's the answer to the "Question to think about: How can you organize an edge list to make searching for a particular edge take O(lgE) time? The answer is a little tricky." ?(5 votes)
- Sort the list by the 1st vertex in each edge, and then by 2nd vertex in each edge.

The list is sorted, so we can now use a binary search on it.

Our comparison is a little bit more complicated now.

[v1,v2] < [v3,v4] if (v1 < v3) OR ( (v1 === v3) AND v2 < v4 )

If we have an edge [v1,v2] we do a binary search for [v1,v2] on the list. Time O(log E)

If your edges are not directed i.e. [v1,v2] is equivalent to [v2,v1] then perform a second search on the equivalent edge [v2,v1] if your first search wasn't successful. Double O(log E) is still O(log E).

Hope this makes sense(4 votes)

- Can anyone give a real life example of when to use particular graph representation? For example, adjacent matrix is good with running time but isn't efficient for space. How do you know where we can use edge list, or adjacent matrix or adjacent list?(3 votes)
- Adjacency matrices are very good for dense graphs, and adjacency lists are good for sparse graphs. So it depends on what your graph looks like, but it also depends on whether you care more about running time or memory. If you represent your adjacency matrix as a hash table, you can get very good lookup times without using n^2 memory.

For a site like Facebook, you might want to represent the social network as a graph, but Facebook has ~1.23 BILLION users, so if we were to use an adjacency matrix it would take far far too much memory. In practice people will each have maybe a few thousand friends at most, so we don't have to worry about the lookup time being too bad, especially if we keep the adjacency lists sorted and use binary search.(8 votes)

*Yay, I'm a part of the fam now :) x)….Will the computer science and computer programming sections on Khan Academy help me start my back end developer career?! Are there any full stack developers here that started the same why I am? D; This site doesn't appear to be too active anymore in these sections, Cameron still help answer questions? Maybe I will learn to be the next computing genius to help others here :D, anyone else browsing these sections besides me? =0*(6 votes)- how can i give adjacency list representation of an undirected graph ?(3 votes)
- The adjacency list representation for an undirected graph is just an adjacency list for a directed graph, where every undirected edge connecting A to B is represented as two directed edges:

-one from A->B

-one from B->A

e.g. if you have a graph with undirected edges connecting 0 to 1 and 1 to 2 your adjacency list would be:`[`

[1] //edge 0->1

[0,2] //edges 1->0, and 1->2

[1] //edge 2->1

](2 votes)

- How do you do the first step of the Challenge: Store a graph? I've figured out the second step but I can't figure out the first.(3 votes)
- To make the adjacency matrix, you're going to need to use what's called
*nested arrays*. This is basically arrays within arrays. Here is what your array is going to look like.`[`

[0, 0, 0, 0, 0, 0],

[0, 0, 0, 0, 0, 0],

[0, 0, 0, 0, 0, 0],

[0, 0, 0, 0, 0, 0],

[0, 0, 0, 0, 0, 0],

[0, 0, 0, 0, 0, 0]

]

You're then going to stick 1s in wherever there is an edge that leaves the row number vertex enters the column number vertex. So the spot (3, 2) on this matrix tells us if there is an edge that leaves vertex 3 enters vertex 2.(1 vote)

- (Note)

How can you organize an edge list to make searching for a particular edge take O(\lg E) O(lgE) time?(2 votes)- Hint: Is there some way we could organize the data to make use of binary search ?(2 votes)