Graph display using linked list and matrix

Question

I know how to implement a graph using a linked list or matrix. But I want to know when to use the Linked List and when to use the matrix to represent the graph?

Answer 1

V = number of vertices in the graph

Matrix Favors:
1. You can access the edge (find out if there is an edge between two vertices), given its end vertices in constant time, while using the adjacency list takes time O (degree (vertex)).
2. The matrix is ​​good if your schedule is tight. Otherwise, it spends space because it uses O (V * V) space.

Points for adjacency list:
1. You need O (V) time to iterate to get neighboring vertices, while an adjacency list requires O (degree (vertex)).
2. The adjacency list does not take up much space.

Answer 2

Usually when your schedule is dense . It is recommended to use a matrix, since the "loss" of unused memory and unnecessary reads are ignored.
Usually you also use a matrix if you want to know if an edge exists, or you want to pre-form matrix operators on a chart [for example, Page Rank ] (*)

A linked list is usually preferable if you intend to use all the edges for each vertex when reading [for example: on BFS].

(*) Note that page ranking behind the scenes usually uses a linked list, as the graph is very sparse, but we see it as a "sparse matrix" ...

Answer 3

There are two main differences between these two implementations in terms of consumption and memory complexity.

• The matrix representation allows random access to elements, the constant is the time of inserting and deleting elements, but (in general) they consume more space.
• A linked list, on the other hand, is more memory friendly , but access to an element and neighbors can take linear time .

Answer 4

It depends on your problems and needs. Use a matrix when you need speed and you have a lot of storage (in case your matrix is ​​big), use a linked list if you need to save space when trading slows down a bit.

Answer 5

You always use a matrix.

There are various methods for representing matrices in memory, including various ways of using linked lists to represent sparse matrices. Any good book on matrix computation will have many ideas and recommendations when it is useful to use them; depending on your schedule, one of the less common views may be appropriate.