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 

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

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


 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 

The following are some ways to represent graphs: 

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

Boston University

A graph is a data structure that is made up of nodes (vertices) and are connected by arcs (edges). Graphs are most commonly used to represent a network of information. An example of a graph structure is a map of a city. The blocks or buildings represent nodes. These nodes are connected by roads that represent edges. 

Graphs may be weighted or unweighted. Weighted graphs have a numerical value attached to each individual edge. This means that different edges may have different magnitudes. Unweighted graphs do not have weights related to each edge.

Graphs may also be directed or undirected. Directed graphs mean that each edge has a certain direction. As a result, these edges represent a one-way relationship since edges can only be traverse in one direction. On the other hand, undirected graphs mean that each edge has no direction. Therefore, these edges represent a two-way relationship since edges can be traversed in both directions.

Graph

Representations of Graphs

- BFS (Breadth-First Search)
- DFS (Depth First Search)

Learn Before

Related

Learn After