https://www.sciencedirect.com/science/article/pii/B9780124095205500163

** information on Incidence Matrix on pages 158 - 160 in Chapter I


Boston University

The following are some ways to represent graphs: 

- Adjacency Matrix
- Adjacency List
- Incidence Matrix 
- Incidence List

Representations of Graphs

An adjacency matrix helps show which particular vertices of a graph are adjacent to another vertex. It is a 2D array that has a height and width of size V where V is number of vertices in the graph. It is thus a V x V binary matrix ( a matrix where each cell can only have one of two values like 1 or 0). To show that there is an edge from vertex a to b, the space M[a][b] for matrix M would have a value of 1. If the graph being represented is weighted, the space M[a][b] would still have a value of 1 to show the relation between vertex a and b. However, the matrix could be modified to instead have the space M[a][b] show the weight value. 

Adjacency Matrix 

An adjacency list represents all of the edges in a graph as a list. It is an array of lists where the size of the array is the number of vertices in the graph. For a vertex i and an array a, the entry a[i] would represent the list of vertices that are adjacent to the vertex i (which is typically unordered).

Adjacency List 

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.301.180&rep=rep1&type=pdf

Adjacency Matrix and List 


Adjacency Matrix : 
- Time complexity for adding / removing an edge in an adjacency matrix is in O(1) time 
- Easy to implement  
- Take lots of memory in order to store big graphs regardless of whether the graph is sparse or dense ** 
- Time complexity for adding/ removing a vertex is O(V ^2) where V is a vertex

Adjacency List :
- Time complexity for adding / removing an edge in an adjacency matrix is in O( E / V) time where E is an edge and V is a vertex
- Takes less memory to store the graph 
- Time complexity for adding a vertex is O(V) where V is a vertex and removing a vertex is O(E) where E is an edge 
- A list of adjacent vertices can be obtained in O(1) time 


** Sparse graphs have a number of edges that is much less than the square of the number of vertices while dense graphs have a number of edges that is comparable to the square of the number of vertices.


Pros / Cons of Adjacency Matrix and List

An incidence matrix has a row for every vertex of the graph and a column for each edge of the graph. In an undirected graph, the element M [x,y] of a matrix M is 1 if the vertex x is a vertex of the y edge and is 0 in all other cases. In a directed graph, the element M [x,y] of a matrix M is 1 if vertex x is an initial vertex to the edge y, -1 if vertex x is a terminal vertex to edge y, and 0 for all other cases.

Incidence Matrix 

An incidence list contains a list for the edges incident to a vertex for each vertex in the graph. Thus, the incidence list contains a row for each vertex. For each edge that is stored in the incidence list, there needs to be extra information stored about what the endpoint of that edge is. For example, there could be three vertexes A, B , and C with edges A1 ( that starts at A and ends at B ) and A2 ( that starts at A and ends at C ). The incidence list contains edges A1 and A2 for vertex A and nothing for B and C. The edge A1 would need to store both A1 and B and A2 would need to store both A2 and C.

Incidence List 

https://www.youtube.com/watch?v=bP-8P8f8mAY

Incidence List starts at 7:31 min 

Learn Before

Related