Q: 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"

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

Q: 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?

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.

Q: how can i give adjacency list representation of an undirected graph ?

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 ] ```

Question 1

"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?

Accepted Answer

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.

Question 2

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.

Accepted Answer

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

Question 3

how is adjacency list space Θ(V + E)?

Accepted Answer

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)

Question 4

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." ?

Accepted Answer

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

Question 5

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"

Accepted Answer

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

Question 6

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?

Accepted Answer

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.

Question 7

how can i give  adjacency list representation of an undirected  graph ?

Accepted Answer

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
] 
```

Question 8

In the -2 paragraph, what is the function of the doStuff function?

Accepted Answer

"doStuff" is just a made up name for an imaginary function that takes a vertex from your graph an does something with it.

Many programmers just use the name "foo" for an imaginary function that is  used in examples where we don't really care what the function "foo" is doing.

Course: Computer science theory > Unit 1

Representing graphs

Edge lists

Adjacency matrices

Adjacency lists

Want to join the conversation?