CODEWITHSUNDEEP
algorithmdata-structuresgraph
Desire
Desire

Reputation: 593

Graph representation using linked list & matrix

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?

Upvotes: 6

Views: 3528

Answers (5)

Pete Kirkham
Pete Kirkham

Reputation: 49331

You always use a matrix.

There are various techniques for representation of matrices in memory, including various ways of using linked lists to represent sparse matrices. Any good book on matrix computation will have many representations and guidelines for when it is good to use them; depending on your graph it may be that one of the less common representations is appropriate.

Upvotes: 0

Divya
Divya

Reputation: 2622

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.

Upvotes: 5

amit
amit

Reputation: 178521

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

Upvotes: 4

Ghassen Hamrouni
Ghassen Hamrouni

Reputation: 3168

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.

Upvotes: 1

LeleDumbo
LeleDumbo

Reputation: 9340

It depends on your problem and needs. Use matrix when you need speed and have big storage (in case your matrix is big), use linked list if you need to save space with the trade off having a little slow down.

Upvotes: 0

Related Questions