Graph representation using linked list & matrix

Question

I know how to implement graph using linked list or Matrix. But i want to know when to use Linked List & when to use matrix for graph representation?

Answer 1

V = number of vertices in graph

Points favouring Matrix:
1. You can access an edge (find out whether an edge exists between two vertices) given its end vertices in constant time whereas it takes O(degree(vertex)) time while using adjacency list.
2. Matrix is good if your graph is dense. Otherwise it wastes space because it uses O(V*V) space.

Points favouring adjacency list:
1. You need O(V) time to iterate get the neighbours of a vertex whereas it takes O(degree(Vertex)) if you use adjacency list.
2. Adjacency list does not take a lot of space.

Answer 2

Usually, when your graph is dense. It is a good idea to use matrix , since the 'loss' of unused memory and not needed reads is neglected.
You usually also use a matrix when you want to know fast if an edge exist, or you want to preform matrix ops on the graph [such as Page Rank] (*)

A linked list is usually prefered if you are going to use all edges for each vertex, when reading it [for example: on BFS].

(*)Note that page rank behind the scenes is usually using a linked list since the graph is very sparsed, but we regard it as a "sparsed matrix"...

Answer 3

There is two fundamental differences between those two implementations in terms of memory consumption and complexity.

1. The matrix representation allow random access to elements, constant time insertion and removal of elements but (in general) it consume more space.
2. The linked list in the other hand is more memory friendly but access to element and neighbours can take linear time.